nodename / as3delaunay

Delaunay triangulation and Voronoi diagram for Flash (Flash Builder 4 project)
http://nodename.github.com/as3delaunay/
MIT License
157 stars 104 forks source link

`getNeighborSitesForSite` bug - How to get a graph only spanning between voronoi neighbor sites? #8

Closed Domiii closed 9 years ago

Domiii commented 9 years ago

When looking at the Delaunay graph, Voronoi sites on the region boundary are connected to other sites that are not immediate Voronoi neighbors, but also happen to touch on the same boundary line (probably to ensure convexity of the triangulation).

When playing around with the demo, you can easily see the problem. I highlighted one such edge on the right-hand side with a long white box.The edge connects two Voronoi sites are not immediate neighbors:

image

If this is intended, then the getNeighborSitesForSite method should be renamed to getDelaunayNeighborSitesForSite or so, to make sure that this is not a neighbor in the sense of the Voronoi diagram?

Also, do you have a quick fix for getting such a Voronoi graph that only connects Voronoi neighbor sites?

nodename commented 9 years ago

This result is indeed intended, because the Delaunay triangulation by definition includes the convex hull. A graph that omits the hull edges would not be the Delaunay triangulation.