Determine distance from point in Voronoi triangulation to input polygon

[bVess12]

I'm not sure if I'm missing something obvious or if this isn't supported at all by this library but I thought I'd ask. Any help is appreciated!

My code does the following:

1. Create a polygon with holes
2. Triangulate the polygon to acquire a Delaunay triangulation
3. For each triangle in the resulting mesh, calculate the circumcenter
4. Connect each circumcenter to that of each of its neighbors to form the Voronoi diagram
5. Iterate over each point in the Voronoi diagram and compare it to the input polygons to calculate shortest distance

What I would like to achieve: Currently, step #5 takes too long with large datasets. I'm not much of a mathematician, and I was wondering if there was some way along steps #1 - #4 that I could extract or derive this information. If this is outside the scope of this library, please let me know and I can take my question elsewhere.

Thank you!

[wo80]

If your input has n points, then step 1-4 will be O(n*log(n)), but step 5 is O(n^2).

The first thing that comes to mind:

• Each Voronoi cell is generated by a vertex of the Delaunay triangulation (you can store this generator when computing the Voronoi diagram).
• In step 5, for each Voronoi vertex, check only the generators of the adjacent Voronoi cells.
• All of those generators should be part of the input polygon, so one of them should be connected to the edge with the shortest distance.

Actually, I don't know if the last point is true, since I don't know what your input might look like. But this way, you only compare the Voronoi vertices to a small subset of the input points, which should be O(n).

Triangle.NET provides code to compute the bounded Voronoi diagram. Maybe that works for you, see Triangle/Voronoi/VoronoiBase.cs and Triangle/Voronoi/BoundedVoronoi.cs.

Also make sure that your triangulation is conforming Delaunay, see Triangle/Meshing/ConstraintOptions.cs

[bVess12]

Thank you for the quick reply!

I was unaware that the BoundedVoronoi was a built in feature, I'll go ahead and use that, thank you! However, I was relying on the "region" and corresponding "label" property to differentiate between vertices that were on/outside the input polygon and those inside it. When I use the BoundedVoronoi, it seems that all edges/vertices have a label of "0." Am I missing something or do regions not work for the BoundedVoronoi?

[wo80]

I was relying on the "region" and corresponding "label" property to differentiate between vertices that were on/outside the input polygon and those inside it.

The BoundedVoronoi class already takes care of that. So if you don't need that information later on, you should be fine.

When I use the BoundedVoronoi, it seems that all edges/vertices have a label of "0". Am I missing something or do regions not work for the BoundedVoronoi?

You are right. The Vertex class doesn't have a label property at all (edit: the HalfEdge class has a Boundary property, but that isn't used anywhere). It would be fairly easy to set this up, so let me know if you need it.

I'd suggest to first try the approach described in the previous post. The generators of the Voronoi cell are actually the original points of the triangulation. So if you create a map [vertex] -> connected edges of the input polygon, you should have all the information needed.

To process all faces adjacent to a Voronoi vertex, use the vertex.EnumerateEdges() method and the Face property of the half-edge.

[wo80]

So if you create a map [vertex] -> connected edges of the input polygon, you should have all the information needed.

When triangulating the input polygon, the ConformingDelaunay option will make sure that all triangles are truly Delaunay (otherwise, the dual graph would not be a Voronoi diagram). To achieve this, input segments might be split and new vertices created on the boundary. This means you should actually create the map mentioned above from the segments of the mesh and not the input polygon.

Also note that my approach relies on the fact that there are no additional (loose) vertices inside the polygon (implying that you are not using any quality constraints like min/max angle).

[wo80]

I have updated the code so that Voronoi vertices now have their label properly set.

You can identify vertices that are not dual to a triangle (for example endpoints of "infinite" edges) by checking label == 0 and id >= mesh.Triangles.Count.

[bVess12]

Wow, this was so helpful! Thank you so much!

I was successfully able to filter out the edges I didn't want by taking vertices.Where(v => v.id < mesh.Triangle.Count) Was this described anywhere? I didn't realize Id was used this way.

I now have everything I need to solve my problem. But just so you know, I don't believe the region fixed worked? After I pulled I still never had a single vertex/edge/face that had a non-zero Label

[wo80]

Wow, this was so helpful! Thank you so much!

You're welcome! Happy this worked out for you.

Was this described anywhere? I didn't realize Id was used this way.

It's not documented, you'd have to look at the code. But I guess it's rather intuitive to have the match between dual entities.

I now have everything I need to solve my problem. But just so you know, I don't believe the region fixed worked? After I pulled I still never had a single vertex/edge/face that had a non-zero Label

Edges are not set up. Vertex labels should be correct since https://github.com/wo80/Triangle.NET/commit/d65272098fce31e78202278a3d220007b3e0debe and I just pushed another simple change in https://github.com/wo80/Triangle.NET/commit/826057a5e0a3d196b279d30bc475574b2d27d089 setting the face labels (that info was already present in the generators labels). Tests are passing, see BoundedVoronoiTest.cs.