triangualize - ObjectVision/GeoDMS GitHub Wiki
Geometric functions triangualize
- triangualize(point_data_item)
triangualize(point_data_item) results in a new uint32 domain unit with one entry for each edge of the Delaunay triangulation of the points in the point_data_item argument.
The Delaunay triangulation is the triangulation in which no point lies inside the circumcircle of any triangle. It maximises the minimum angle over all triangles, which is why it avoids sliver triangles, and it is the dual graph of the voronoi diagram.
The function results in an F1 and F2 attribute with relations to the domain unit of the point_data_item attribute.
Each edge occurs once, with F1 < F2 (an edge between point 0 and point 1 occurs as F1: 0, F2: 1 and not also the other way round). The rows are sorted by F1 and then F2, so the result is stable between runs.
The number of edges follows from Euler's formula. With m distinct, defined points, of which h lie on the convex hull, the triangulation has exactly 3m - 3 - h edges and 2m - 2 - h triangles. Since 3 ≤ h ≤ m:
| case | number of edges |
|---|---|
| h = 3, all other points interior | 3m - 6 (the maximum) |
| h = m, all points in convex position | 2m - 3 (the minimum for a 2-dimensional result) |
| all points collinear | m - 1 |
| m = 2 / m ≤ 1 | 1 / 0 |
Use voronoi to obtain the dual: the Thiessen cell of each point.
attribute point_data_item with a point value type and Single composition.
- null points take no part in the triangulation and occur in no edge.
- Coinciding points collapse onto a single site that keeps one of their indexes; the other indexes occur in no edge.
- Collinear point sets are allowed: the triangulation is then one-dimensional and the result is the chain of m - 1 edges.
20.12
O(m log m). The implementation is CGAL's Delaunay_triangulation_2: randomised incremental construction, with the sites spatially sorted (Hilbert) up front so that point location is a walk from the previously inserted vertex and costs O(1) amortised. The Delaunay property is restored per insertion by flipping edges that fail the in-circle test. Predicates are filtered (interval arithmetic with an exact fallback), so the result is combinatorially exact even for cocircular or near-collinear input; no constructed coordinate enters the result, only point indexes.
Memory is O(m): about 200 bytes per point for the triangulation, plus 8 bytes per edge for the result.
unit<uint32> station: nrofrows = 4
{
attribute<ipoint> geometry: [yx(0,0), yx(0,1000), yx(1000,1000), yx(1000,0)];
}
unit<uint32> edge := triangualize(station/geometry);
| F1 | F2 |
|---|---|
| 0 | 1 |
| 0 | 3 |
| 1 | 2 |
| 1 | 3 |
| 2 | 3 |
domain edge, nr of rows = 5
The four corners of a square are cocircular, so which of the two diagonals is triangulated is an arbitrary but deterministic choice; here it is 1-3. The edge count is not arbitrary: m = 4 points all on the hull gives 3·4 - 3 - 4 = 5.
- voronoi - the dual: one Thiessen cell polygon per point
- polygon_connectivity - the same F1/F2 network shape, for adjacent polygons