Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Straight Skeleton original code

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Straight Skeleton original code


Chronological Thread 
  • From: "Fernando Cacciola" <>
  • To: <>
  • Subject: Re: [cgal-discuss] Straight Skeleton original code
  • Date: Fri, 23 Nov 2007 09:20:56 -0300
  • Organization: Geometry Factory

Dear Xiangzhi,

I am sorry, I did not save it,

OK, that's what I imagined.
In that case you just drawn the polygon right there in the demo program, but then, the edges V1V2 and V5V6 *are not exactly* along the same line, just almost so.
Thus, the generated straight skeleton is correct for the given input.
That is, what you are seeing is not a bug in the program, not even an undesired effect of the choosen algorithm, is the way a straight skeleton is, by definition, and any correct implementation of any algorithm will produce the same output.

If you use a polygon where the edges are truly aligned you'll see the vertex event that you expected. For that you need to define the polygons in a text file so you can define the coordinates exactly. Then you can load the polygon in the demo (via File->Load Polygon)

I'm attaching here some examples from my internal test-suite so you can see vertex events:

pseudo_split_0.poly
is the classic "eppstein" example

pseudo_split_11.poly
is the essentially equivalent to your test case (but upwards)

pseudo_split_6.poly
pseudo_split_8.poly
pseudo_split_13.poly
are just some additional examples for you to see


but you can also do some experiment on
"Straight_Skeleton_2" with some polygons alike. If you want to further
discuss those degeneration cases, please refer to the attached file. In
fact, I hope some one can explain them in a mathematical way.

The fact that a vertex event radically changes the resulting straight skeleton is simply an avoidable consequence of the topological changes that ocurr when edges collide.
The vertex event is like a singularity in the sense that two split events are ocurring simultaneously and corresponding topological change is not the same as one split after the other (that's why the algorithm *must* handle this explicitely)

And how to avoid those cases.

What exactly do you want to avoid? if you want the structure of the skeleton not to be so sensitive to the exact coordinates of the input vertices then I you are just out of luck... it is like wanting water not to boil when it reaches 100º becasue it doesn't when it is at 99.99º

HTH

Fernando Cacciola
GeometryFactory

Attachment: pseudo_split_0.poly
Description: Binary data

Attachment: pseudo_split_6.poly
Description: Binary data

Attachment: pseudo_split_8.poly
Description: Binary data

Attachment: pseudo_split_11.poly
Description: Binary data

Attachment: pseudo_split_13.poly
Description: Binary data




Archive powered by MHonArc 2.6.16.

Top of Page