Removing boundary points from a mesh?

Aug 15, 2015 at 12:21 AM
Edited Aug 15, 2015 at 12:23 AM
First off, your port is beautiful and I want to thank you so much for it. I made a codeplex account because of this project.

I am using the latest source code (77033) and am attempting to create voronoi diagrams within a concave (non-complex) polygon. I would like to be able to specify a point cloud and a bounding polygon, and generate a voronoi diagram bounded to my polygon. The problem I am having is I can't figure out a way to specify a bounding polygon without its vertices being included in the triangulation of the mesh, and therefore becoming a face in the resulting voronoi diagram. Or if I don't specify the bounding polygon the triangulation ends up crossing boundary lines.

Does anyone have any suggestions on what the best way to go about doing this would be? Is it possible to remove the boundary points and corresponding triangles from the triangulation before passing it to the voronoi diagram, and still have the voronoi diagram faces be bounded to the original boundary?
Aug 15, 2015 at 8:54 AM
Edited Aug 15, 2015 at 9:01 AM
So you have a point cloud and an approximate boundary polygon. You compute the Voronoi diagram, but don't want the faces generated by the boundary vertices to be included.

Why don't you just ignore them (or remove them in a post-process step)? Just give the vertices of the boundary polygon a common, unique boundary mark. Then loop over all Voronoi faces and identify the unwanted faces by looking at the boundary property of the face generator.

EDIT: Just saw that the generator isn't exposed as a public member. You'll have to edit the TriangleNet.Topology.DCEL.Face class.
Aug 15, 2015 at 3:04 PM
Edited Aug 15, 2015 at 7:51 PM
So I'm not sure that will work because I need the voronoi diagram to extend all the way and fill my boundary. The use case for this is I am generating voronoi diagrams within voronoi cells, but I don't want the cell vertices to be necessarily included in the voronoi diagram. Further the cells will be slightly modified so they will be concave, which led me to the following workflow:

1) Generate the point cloud inside my border polygon
2) Generate the delaunay triangulation on the point cloud only
3) cull the resulting mesh, removing all segments and corresponding triangles that intersect with my boundary edges (O(n^2)) I know I won't have to remove any vertices, but edges may have to be removed because of concavity.
4) pass the new mesh to a standard voronoi
5) cull the voronoi to the boundary edges, closing faces as necessary

I am currently working on step 3 and it requires a bit of manipulation to the mesh class, would love guidance on how to remove an edge and corresponding triangles from the mesh. I don't need the whole mesh to necessarily be triangulated after each step either, as I believe it is guaranteed to be triangulated after the end of step 3. As long as it is in a "stable" state by step 4 I should be okay.

Perhaps there is more merit in the idea that I generate the voronoi diagraam, take out the boundary faces, and then extend the remaining faces to fill out the polygon, but I am not really sure how I would go about doing that.

So I got step 3 to work by using the ToMesh in the converter class, removing triangles without having to much with the mesh source code.. However I am no longer certain this is the path to proceed. I am willing to generate a bounded voronoi diagram which includes the specified edge points, I just don't want any additional boundary points. I found this disscussion: but when I specify conforming delauanay = true and Segment Splitting = 1, my bounded voronoi is not actually bounded to the boundary..

Picture: (EDIT: Not sure why it didn't link correctly)
SplittingSegments = 1
SplittingSegments = 0

var poly = new Polygon();
// add the bounds
poly.AddContour(bounds.Select(x => new Vertex(x.x, x.y)), 2, false, true);

// add point cloud
foreach (var p in points) { poly.Add(p); }

// Triangulate the mesh
var constraints = new ConstraintOptions() { ConformingDelaunay = true, SegmentSplitting = 1};
mesh = (TriangleNet.Mesh)poly.Triangulate(constraints, new QualityOptions(), new SweepLine());
voronoi = new TriangleNet.Voronoi.BoundedVoronoi(mesh);

VoronoiVertices = voronoi.Vertices.Select(x => new Vector2f(x.X, x.Y)).ToList();
VoronoiEdges = voronoi.Edges.Select(x => new LineSegment(VoronoiVertices[x.P0], VoronoiVertices[x.P1])).ToList();
Aug 18, 2015 at 10:22 AM
Edited Aug 18, 2015 at 10:45 AM
Well, specifying both options doesn't make too much sense. If you specify ConformingDelaunay = true, additional vertices will most likely be inserted to make the mesh truly Delaunay and from what you describe, I guess the SegmentSplitting option is ignored.

Computing the Voronoi diagram from a triangulation requires the triangulation to be Delaunay. Otherwise you'll run into problems like non-simple Voronoi cells.

EDIT: looking at the image, obviously the ConformingDelaunay option gets ignored. Since the triangulation is not truly Delaunay, the Voronoi diagram cannot be computed correctly.

One option might be to compute the Voronoi diagram directly using Fortune's algorithm (though I don't know any implementation to compute bounded Voronoi diagrams for polygons).