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: "xiangzhi wei" <>
  • To: , ,
  • Subject: Re: [cgal-discuss] Straight Skeleton original code
  • Date: Thu, 22 Nov 2007 23:29:56 +0800
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references; b=nD+3LhCiEx5WykTNNfJUCPx1xEG//vZfSzg2VFT7C5iV1AUavx8GtW7Y8mAeCEklso2HY4sm+q+v8HtG1oQPZU8XCnY6QfGTn1ObjkgGrahXMuljKFEf6jVbAUjiLUNrbcjaS8ko3X5s8uGQZXZQ3OcXmXV9DEnpK8/HLh0Vbeg=

Hi! Dear Dr.Vaxman,

Thanks very much for your concern. I assume that you are very intersted in this topic.

Yes!! I mentioned split event in my materials because I want to discuss something else. Please consider that case a little further, and perturb it a little, then you will be able to find that straight skeleton is very different...you can find some comment on page 62 of your recommended paper...and if you want to find some more related, please refer to the following Ref.

[1] Oswin Aichholzer, Franz Aurenhammer, David Alberts, and Bernd Gärtner, "A Novel Type of Skeleton for Polygons", Journal of Universal Computer Science 1(12), pp. 752-761, 1995.

[2]  Mirela Tanase, Remco C. Veltkamp. Polygon Decomposition based on the Straight Line Skeleton. SoCG'03, June 8-10, 2002, San Diego, USA.

By the way, this is something related to double number round-off in current computer system. In this sense, you can never guarantee the straight skeleton pieces are always perpendicular to the "collinear", as a result, straight skeleton pieces can be various a lot, you can have a try. Besides, for engineering application purpose, more often than not, this kind of degeneration (there are others) can be harmful.

If you have any new findings, please let me know.



Thanks,

xiangzhi

2007/11/22, Amir Vaxman <>:

The case you discuss is not a "split event" , it is what Eppstein & Erickson called a "vertex event" in his article:

 

@article{EppsteinErickson,

 author = {D. Eppstein and J. Erickson},

 title = {Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions},

 journal = {Proc. 14th Ann.\ Symp.\ on Computational Geometry, \upshape{58--67}},

 year = {1998},

 address = {Minneapolis, MN},

 }

 

It occurs on the degeneracy where two reflex vertices meet, and should be handled accordingly. What happens after this event, is that the newly-created vertex is a vertex between two collinear edges. It is not one edge.

 

From: xiangzhi wei [mailto:]
Sent: Thursday, November 22, 2007 4:02 PM
To:
Subject: Re: [cgal-discuss] Straight Skeleton original code

 

Hi Fernando Cacciola !

Thanks very much for your help!

Two degeneration cases are listed in the attachment. if there are at least two becoming edges collinear during the shrinking process. As a result, the shape of straight skeleton seems incorrect !!

If you have some good idea, please let us know.

Best regards,

Xiangzhi

2007/11/22, Fernando Cacciola <>:

Hello Xiangzhi

> Hi all !
>
> I wanna if there is any original code for straight skeleton on CGAL. There
> is something wrong with the software titled "Straight_Skeleton_2" when it
> comes to those cases when at least two disjoined edges came into collinear
> during the shrinking process of the original polygon.
>
There is a bug fix for the Straight Skeleton package which unfortunately
couldn't be incorporated into CGAL 3.3.1.
I'm attaching the patch in this message.
Can you please try again after installing the patch and report on the list if
you still find a problem?

Just unzip the attached file right there into the top level folder of a CGAL
installation.

> And I wanna do some experiments to test it further, but I cannot find its
> original C++ code.
>
What you mean by original C++ code?

TIA

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

 





Archive powered by MHonArc 2.6.16.

Top of Page