CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

For each polygon, insert each edges in the CDT by first inserting the 
endpoints and then constraining the edge using the corresponding 
vertex_handle.
You have then two choices:
*if you have your polygons consistently oriented (says counterclockwise 
for example), associate into a map, the ordered pair of vertex_handle
to the polygon id.
*otherwise, sort the vertex_handle pair and associate the pair into a 
multimap the polygon id.

The final step is to mark each face in the CDT (either use a map or a 
face type with info). Reconstruct each polygon by using maximal 
connected component of faces connected with non-constrained edges by 
starting from faces incident to the infinite vertex.
(see this for example: 
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-11/msg00150.html).
The id of the polygon is given by the id of the edge crossed given by 
the map or multimap.

Sebastien.







Graviton wrote:
> I have a set of non-overlapping polygons. These polygons can share nodes,
> edges, but strictly no overlapping.
>
> Now, I am going to mesh them using Constrainted Delaunay Triangulation (CDT)
> technique. I can get the mesh without problem.
>
> My problem is, after the mesh, I want to know which mesh element belongs to
> which original polygon. MY current approach is to compute the centroid for
> each mesh element, and check which of the original polygon this centroid
> falls into. But I don't like this approach as it is very computationally
> intensive.
>
> Is there any efficient ways to do this ( in terms of Big O the runtime)? My
> projects involve tens of thousands of polygons and I don't want the speed to
> slow down.
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Check-which-mesh-element-is-inside-the-original-polygons-tp4163729p4163729.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.