Voronoi diagram bound by circular tour

1
votes

I'm facing the following problem:
I'm given a point cloud P and a subset of that point cloud B. The nodes b in B constitute the boundary of the (whole) point cloud P. (In fact, B is given as a closed, oriented circular tour). Now, I would like to compute the Voronoi diagram of P, intersected by B, and extract the Area of each (intersected) Voronoi polygon. Here is an illustration of the situation:
(source: 666kb.com)

Basically I would like to intersect the blue polygons with the green segments. To my questions:

  • Is there, by chance, a C library that solves this exact problem?
  • If not, is there a better way to solve this problem then computing the Voronoi diagram using some Library, then explicitly intersecting the (green) segments with the polygons from the library output? Maybe by exploiting a constrained Delaunay triangulation?

PS: I know that this feat would probably be possible using CGAL. However, having never used CGAL, CGAL seems quite complex and adapting Example code such as this seems far from straight forward. Also, I would strongly prefer a solution in C.

1
ccomputational-geometryvoronoi
You can try an alphashape. Its a delaunay triangulation without edges exceeding alpha. - Micromega
Can you maybe elaborate a bit how alpha shapes could be used for my purpose? - Matthias
:You can also delete the infinity edges but with alphashapes you have the alpha value you can play with. But I think you need a constrained vd even intersection isn't accurate, isn't? - Micromega
There is no need for explicitly intersection since intersection point is middle point of segment connecting two boundary points. Voronoi lib, for a point, returns list of segments of point's Voronoi cell. For two neighbouring boundary points, find segment that is in both Voronoi cells and split it with middle point of segment connecting boundary points. - Ante

1 Answers

0
votes
(source: [666kb.com](http://666kb.com/i/csphx8ow43habobik.gif))