CGAL users discussion list

["xiangzhi wei" <>]

Hi Fernando Cacciola!

thank you very much! in fact, we are designing a faster algorithm for straight skeleton generation, after we finish it, I will certainly feel happy to show it to you, and for other fellows in our group. The prerequisite is that every step of our approach is correct and feasible.

But we did not know how to input a polygon through a text file, could you please let me know via E-mail...?

Thanks again!

xiangzhi

2007/11/23, Fernando Cacciola < >:

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
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss