freenode/#clim - IRC Chatlog
Search
9:54:23
ck_
you must have more than that, an edge list maybe? I mean the ordering is given, right, it's not a set of vertices
9:55:56
jackdaniel
a few months back I've improved 10x time of deciding whenever point belongs to a polygon
9:57:52
loke
jackdaniel: what algorithm did you use? (there is an obvious one, which is to draw a line from the point to some other point that is guaranteed to be outside the polygon, and then count how many times that line crosses any of the edges.
10:07:08
ck_
loke: that's a pretty nice looking convex polygon. for those, just pick a vertex (maybe the lowest-leftmost one) and connect the edges to it.
10:07:36
ck_
if you want a general, always-applicable implementation though, you'll have to either use a library or go paper reading
10:18:28
ck_
The first one I pasted earlier is a good start I think, we could go through the who-cites list and see what the current state of the art is
10:18:53
ck_
judging from your second example, though, I think a partitioning into convex parts seems like a possible choice
10:19:47
ck_
well, then again, it depends. Is the self-intersection near x=100 intentional or an artifact?
10:20:54
loke
There shouldn't be any self intersections in that one. But, it's what is output from cl-vectors, and if we can't use that output we have a bigger problem (and a lot more work on our hands)
10:22:01
jackdaniel
loke: regions may have self-intersections (and draw-design works with that faiirly well)
10:22:49
loke
ck_: This is the input, with the #+nil removed: https://gist.github.com/lokedhs/4afe548554083ee2c39684b1387858a0
10:23:25
jackdaniel
but for sake of drawing I don't think cl-vectors will output anything like that for you
10:24:24
loke
jackdaniel: Yeah, I was just wondering if we need to deal with that once we move draw-design to Xrender
10:25:06
ck_
I don't think I have the full picture yet, but if what i right now suspect is true, there's probably a much better way of obtaining the triangulation of such objects
10:25:08
jackdaniel
I would expect that to work, there is no limitation about points in polygon in the spec
10:29:00
loke
So at least initiaqlly I'd like to use the most correct of algorithms (even if it's slower)
10:35:13
ck_
I understand the motivation, but the part where you create polygons with self-intersections throws a wrench in that plan in my opinion
10:39:00
ck_
loke: what I mean is, you're using cl-vectors for the boundary line segments, and that's what you want to use for the triangulation -- have I got that right?
10:39:43
loke
ck_: right now, yes. The reason I need to do triangualtion is because cl-vectors gives me concave polygons (without intersections, as far as I know)
10:40:20
loke
ck_: later, we need to deal with self-intersections, because DRAW-DESIGN supports it (this use-case probably does not involve cl-vectors)
10:42:02
loke
anyway, if we have an algorithm that can hadle intersectins, then it can be used everywhere.
10:42:25
loke
Are you saying we don't havwe such algorithm? Or that such algorithms are not something we want to use (slow?)
10:44:21
ck_
I'm saying that I'm uncomfortable doing both in the same piece of code. Triangulations of intersection-free polygons are a nicely solved problem.
10:45:22
ck_
If you give me a sequence of boundary line segments that intersect, who's to say what the inside really is? I'd really like to avoid it
12:29:00
scymtym
i tried incrementally changing the old inspector first, but there was no clear path from the old implementation to the new one
12:30:18
scymtym
jackdaniel: which version of the documentation is the canonical one? html or texinfo?
12:35:46
beach
I don't think that has been decided, but if jackdaniel thinks the Texinfo one is better, then go for that.
13:22:06
ck_
right now, you have [path as mathematical line] -> [cl-vector] -> [boundary of path as sequence of line segments] -> [ here be dragons ] -> triangle soup
13:22:38
ck_
and the cl-vector part you want because of the way the paths can be joined and beveled and whatever the names for the frills are
13:24:08
loke
ck_: Yes. Splines will be needed too. Remmeber the end goal is to support all CLIM operations. We know cl-vectos is capable of this, since it's already used for the render backend.
13:25:14
loke
I mean, I can write an algorithm that does it the "hard way" but it'll be crappy and slow.
13:27:29
ck_
you'll find that is often the case, but if you look at the earlier papers, they're often a little simpler and don't hold back so much
13:27:48
ck_
it's a shame that the kind of technical report they had in the 70s or 80s are no longer the standard
13:28:47
ck_
I can put in an evening at the library for this, that should give us plenty of references to read through next weekend or something
13:28:58
loke
The paper I was reading had code for the general outline of the algorithm, but that function called a magic function that did the actual computation described in the paper, and there was no source code for that one(!)
13:30:03
loke
I wonder if I should take alook at the source for something like Cairo. Perhaps there are refences in the code for the algorithms used
13:30:11
ck_
how about "we can triangulate the two examples from earlier and have a visualization for the triangles" as a first milestone
13:30:39
ck_
you could, but I wonder whether they do a triangulation. Isn't cairo mostly rasterization?
13:34:27
scymtym
and no, i'm neither procrastinating nor distracting myself from finalizing the branch: https://techfak.de/~jmoringe/debugger-inspector.png
13:35:47
jackdaniel
I think we need to remove Latex documentation (if someone changes mind about the canonical one they could review it from git history)
14:08:19
ck_
okay let me see if the canonical book, which is Marc de Berg et al.: Computational Geometry, is available somewhere
17:25:48
pouar
ping jackdaniel I kinda missed the live stream, but if you do implement theming, can you make sure it is not limited to just Material Design, as I kinda find flat themes ugly
17:39:18
jackdaniel
pouar: thanks. theming is a matter of implementing a frame manager which /does the thing/, so adding material design won't limit other possibilities (it won't make them easier neither, maybe except that there will be an example of how to do that)
18:23:18
ck_
jackdaniel: could you link me to your winding number test please? We will probably want that for polygon simplification
19:28:43
ck_
the url in the comment to region-c-p-p mentions a speedup figure I just read in that book it referenced ;)
19:36:55
jackdaniel
I saw this photo and I've found it very funny, there is nothing deep in this remark really https://proxy.duckduckgo.com/iu/?u=https%3A%2F%2Ftse3.mm.bing.net%2Fth%3Fid%3DOIP.fM_mB_WnSYBssfbec_ZCcQHaIw%26pid%3DApi&f=1