Geek Answers Handbook

Infinite initial bounding triangle in iterative Delaunay triangulators

Most iterative algorithms require an empty triangle to get the ball. It seems like a commonly used trick is to make a super triangle very large compared to a set of points.

But according to Numerical Recipes: The Art of Scientific Computing:

"... if the distance is just finite (to the boundary points), the constructed triangulation may not be entirely Delaunay. For example, its outer border in some cases may be slightly concave, with small negative angles, on the order of the diameter of a" real "set of points divided by distance to "fictitious" (boundary) points.

So, what are the options for increasing the Cartesian coordinates with points at infinity, without having to convert all the input to another coordinate system, such as uniform coordinates? How do these points fit into the regular geometric predicates CCW and Incircle?

Enable (a, b, c) Infinity → False. provided that a, b, c are finite.

But what about when one of a, b, c is a point at infinity? The circle becomes a half-plane, and the test then becomes a CCW check? What if two or more points on a circle are infinite? Does the circle expand to a full plane, forcing the test to always give the truth? How about CCW? how do you classify a point relative to a line that has one or more points at infinity?

+4
source share
2 answers

I think that you make life difficult for yourself by trying to determine the complete mathematics of geometries, which contains points at infinite distance. This is not necessary for the purposes of your original problem of calculating the Delaunay triangulation accurately.

I wrote the Delaunay generator in Java some time ago and it is available here: http://open.trickl.com/trickl-graph/index.html

See http://open.trickl.com/trickl-graph/apidocs/index.html and in particular:

// Check if fourth point is within the circumcircle defined by the first three private boolean isWithinCircumcircle(PlanarGraph<V, E> graph, V first, V second, V third, V fourth) { // Treat the boundary as if infinitely far away Coordinate p = vertexToCoordinate.get(fourth); if (PlanarGraphs.isVertexBoundary(graph, first)) { return isLeftOf(third, second, p); } else if (PlanarGraphs.isVertexBoundary(graph, second)) { return isLeftOf(first, third, p); } else if (PlanarGraphs.isVertexBoundary(graph, third)) { return isLeftOf(second, first, p); } else if (PlanarGraphs.isVertexBoundary(graph, fourth)) { return false; } Coordinate a = vertexToCoordinate.get(first); Coordinate b = vertexToCoordinate.get(second); Coordinate c = vertexToCoordinate.get(third); boolean within = (ax * ax + ay * ay) * getDblOrientedTriangleArea(b, c, p) - (bx * bx + by * by) * getDblOrientedTriangleArea(a, c, p) + (cx * cx + cy * cy) * getDblOrientedTriangleArea(a, b, p) - (px * px + py * py) * getDblOrientedTriangleArea(a, b, c) > 0; return within; }

Here, the boundary points are explicitly checked when checking the circle conditions, so they can be effectively considered as "infinite". This is much simpler than figuring out all the geometric consequences than you describe.

0
source

It is very easy to implement Delaunay triangulation by adding an infinite point. Choose an agreement for an infinite vertex (for example, vertex index -1).

First, you create the initial end tetrahedron T0 between 4 non-coplanar points taken from the input pointer, and then create four infinite tetrahedra that connect each face of T0 to infinite vertex 0 (and remember to connect them correctly along their common infinite faces).

Then you insert each point p one by one, as usual (Boyer-Watson algo), by (1) calculating the tetrahedron T that contains the point p (find) and (2) finding the conflict zone, as follows

(1) the location is unmodified: you go to p from a random end tetrahedron. While walking, if you arrive in an infinite tetrahedron, then you stop there (this means that the point is outside the convex hull of the previously inserted points)

(2) The definition of a conflict zone requires a slight modification:

  • Point p is in contradiction with the finite tetrahedron T if it is in the described sphere (as usual)

  • For an infinite tetrahedron T = (p1, p2, p3, p4), one of p1, p2, p3, p4 is an infinite vertex (for example, p2, then T = (p1, infinitely, p3, p4)). To check if p is in conflict with T, replace the infinite vertex with p and calculate the signed volume of the tetrahedron: signed_volume (p1, p, p3, p4) in our example, if it is positive, then T is in conflict with. If it is negative, then T does not contradict p. If p is exactly on the reference plane of three end vertices of T, then T is in conflict with p, if T "is in conflict with p, where T" is a tetrahedron next to T along the final face of T (equivalently, instead of query T ', you can check if p is in the circumscribed circle of the finite face T).

See implementations in:

0
source

More articles:


All Articles