Calculating the infinity points/edges of the Delaunay Triangulation

0
votes

I'm trying to calculate the infinity edges of a Delaunay triangulation. I have the main points that can help me collect the vertices for the voronoi diagram. The issue is that I'm not sure how or where to start to calculate the lines that go towards infinity

Example Delaunay Diagram

The ones marked in blue and their connecting line is what i'm trying to calculate The ones marked in Yellow are the ones i already know the points to based on triangulation process.

I'm not sure what kind of calculations i should be making in order to get them. Can anyone suggest a formula or method to calculate them? I can't seem to find information about this anywhere.

2
voronoidelaunay
@Gary Lucas The diagram above is just a demo picture i pulled off of google to show what i'm trying to do. The real issue is that i need to get the points of Voronoi edges to create a polygon. The Delaunay seemed the best because the circumcircle gives me the points that i need to generate polygons. The Only issue is that I am missing infinity points(the outermost edges blue points) which i need to create the Convex Polygon itself. Which is why i'm trying to figure out a way to get those points along the edge of the rectangle container. I am currently using the Bowyer-Watson algorithm. – DaRagingDemon

2 Answers

1
votes

I don’t know if this might an issue for your calculations but, just in case, I will point out that the figure you've included isn’t quite a correct Delaunay triangulation. The bounding polygon for a Delaunay is a convex polygon. You are missing a couple of triangles where the concavities appear in your drawing. Could this be part of the problem?

I have an open source project for Delaunay Triangulations that might be useful to you. It does implement a class for creating “bounded” Voronoi Diagrams from the Delaunay… But it’s really more of a demonstration piece rather than one of the core functions of the library. Since you are really interested in the Voronoi rather than the Delaunay, I think you might be better served by one of the classic algorithms that produce the Voronoi directly rather than creating one from its dual-form (the dual of a Voronoi is a Delaunay). Even so, you can view the project at https://github.com/gwlucastrig/Tinfour

Anyway, as you point out, the bordering edges of a Voronoi cell pass through the centers of the circumcircles of the triangles that form the Delaunay. The rays that go to infinity are related to the triangles that include one of the outer edges. If the circumcircle center lies in the interior of the triangle, the ray extends from the triangle's circumcircle center and through the midpoint of the outer edge. If the circumcircle center lies outside the triangle (as when you have a “skinny” triangle on the outer edge), it will also lie outside the Delaunay bounds. The ray starts from the circumcircle center and extends outward, but it lies on the line that would pass through the cirumcircle center and the midpoint of the outer edge (the midpoint will be behind the start of the ray). So in both cases, you have two significant points, the circumcircle center and the midpoint of the associated outer edge.

I take it that you have a calculation for the position and radius of the circumcircle. If not, you can find one at https://github.com/gwlucastrig/Tinfour/blob/master/core/src/main/java/org/tinfour/common/Circumcircle.java

Hope some of this is helpful.

Gary

0
votes

If you are dealing with a square bounding domain, here is a trick to avoid needed to write code to deal with these special cases of determing these Voronoi edges and intersecting them with the bounding domain. If you reflect the input generators across the domain boundaries and add those to the set of generators, it will ensure that the bounding domain shows up exactly in the Voronoi cells.

To make this concrete, suppose your domain is the square from -1 to 1 in both x and y directions. If one of the points generating your Voronoi diagram is (0.4, -0.3), then you can add points (1.6,-0.3), (-2.4,-0.3), (0.4, 2.3), (0.4, -1.7) reflecting the point across the lines x=1, x=-1, y=1, and y=-1, respectively.

This is kind if expensive: your Voronoi diagram involves 5 times as many input point and four-fifths of them are thrown away. To be more careful, you can create an inital Voronoi diagram with the origninal points (but not worrying about resolving the infinite cells) and then only reflect the points with infinite cells or cells that go outside the bounding domain and build a second Voronoi diagram with this augmented set.

Here is an augmented version of the Voronoi diagram posted showing the key additional vertices in purple.