The selection of distance

[ProtossSine]

Hi, Botffy Thanks for your great job, it helps me a lot. I have a question about the selection of distance when compare the priority of events. I saw you chose the distance between two points rather than the distance between the intersect point and the edge, which is described in the paper. Here is the change you made in one of your commit:

• ev = min(events, key=lambda event: event.distance)

• ev = min(events, key=lambda event: self.point.distance(event.intersection_point))

  I'm a bit of confused, Can you explain why you made this change? Thank you so much~

[Botffy]

Hi, and sorry about the late reply.

Well! It was five years ago, and all I remember I was panicking and going by trial and error :D.

Anyhow, let's reverse engineer this. This is about the f) point of the algorithm (nonconvex case, p8). As usual with the paper, the wording is extremely vague: "store the nearest intersection into the priority queue", nearest to what. Originally I thought "the event that would happen the earliest" (distance to the edge), but that gives incorrect results (run the demo on south_africa with the earlier version and you'll see the problem in the lower right corner. Also, if it were the earliest event, we could just dump all events to the priority queue, and the selection would take care of it, so "nearest to the vertex" sounds better. Why is it better, though?

I can't formulate it, but I think it's got something to do with locality. The three possible events generated have no regard to the other vertices, other events. The likeliest of these to occur is the one that's closest to the current vertex, the one that implies the least slope, the one the current vertex affects the most. At least that's how I imagine it.

I wish I could be of more help.

[ProtossSine]

Hi, Botffy Very for sorry for the late reply. And very thanks for you reply. Well, to a certain extent, have to say that you opinion makes sense. However, I don't think this is the root cause of this issue, cause as you say, we can't formulate it. I don't know if you have read the paper "A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes" written by Fernando Cacciola who is the author of CGAL straight skeleton part. It seems that he gave a new definition of events' distance which I'm not well understood :D. And actually, I have send a email to him for asking help long ago, but didn't receive the reply yet. If you also have read his paper, don't know if you could share some opinion. On the other hand, even change the distance type as you say, it still failed in some cases, like this: . The left one if the CGAL's result which is correct, while the right one is yours. So I thinks there must be some other root cause for this issue.

Thanks for your last reply again. ^_^

[Botffy]

Ahhhh, I knew we fail horribly for highly symmetrical polygons with vertex edges, but I didn't realize it's THIS horrible :D. I should mention this in the readme. At least it's consistent, though!

Originally I made this as a part of a map labeling system which used country shapes as inputs. The issue doesn't surface there, as countries are rarely if ever symmetrical.

No, I didn't read the paper, but I know about the CGAL implementation of course. Cacciola introduced "multi-events" for when there are multiple events happening at the same point. Polyskel merrily ignores these (the first event happens, then it invalidates the further events). And that causes this behavior, at least I always assumed so. Now I'm not so certain. I may look into it this weekend (pull requests are welcome, though!)

[ProtossSine]

Good Morning, Botffy. Don't know where you live, greeting from UTC+8.
Thanks for your reply. Well, you are right. Since the symmetrical polygons will generate simultaneously events which are handled by "multi-events" in Cacciola's implementation. While Felkel's algorithm didn't consider this issue correctly. I'll do some more research about this issue, maybe read the source code of CGAL if I have time. Also look forward your solution if you have time. ^_^