# Partition a 2D polygon - extract graph faces

10 messages
Open this post in threaded view
|

## Partition a 2D polygon - extract graph faces

 To partition a polygon, there's https://doc.cgal.org/latest/Partition_2/index.htmlhttps://doc.cgal.org/latest/Partition_2/group__PkgPolygonPartitioning2.html#ga3ca9fb1f363f9f792bfbbeca65ad5cc5But it returns a list of separate polygons, each with its own set of points. How do I extract a graph partition from that (find corresponding points between the sub-polygons)? One may consider feeding them to an Arrangement_2 and extract the faces, but it sounds like an overkill. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 Here is a nucleus of something that might work. https://gist.github.com/afabri/b1bd0df0866d5f15590d4d7be6a12eba What would be the input you want to partition?  The face of an Arrangement_2 ? andreas On 3/21/2019 8:59 PM, Zohar wrote: To partition a polygon, there's https://doc.cgal.org/latest/Partition_2/index.html https://doc.cgal.org/latest/Partition_2/group__PkgPolygonPartitioning2.html#ga3ca9fb1f363f9f792bfbbeca65ad5cc5 But it returns a list of separate polygons, each with its own set of points. How do I extract a graph partition from that (find corresponding points between the sub-polygons)? One may consider feeding them to an Arrangement_2 and extract the faces, but it sounds like an overkill. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 I would expect the interface to be: - Input: an array of polygon vertices (Point_2). - Output: list of (inner partition) edges given as pair of (integer) indices in the input array, or alternatively a list of faces given as indices of vertices in the input (the former sounds easier and better). I think I can extract that from your surface. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 Instead of vertex_descriptor of a Surface_mesh, you might store a std::list::iterator in the std::pair. On 3/26/2019 12:19 AM, Zohar wrote: I would expect the interface to be: - Input: an array of polygon vertices (Point_2). - Output: list of (inner partition) edges given as pair of (integer) indices in the input array, or alternatively a list of faces given as indices of vertices in the input (the former sounds easier and better). I think I can extract that from your surface. -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 Sorry, I wasn't familiar with Surface_mesh. It's a cool class, I can add faces on the fly and extract the indices of the inner edges. Would it be straightforward to do the same for convex partition? -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 I think I also made it work for convex partition. On 3/29/2019 12:00 AM, Zohar wrote: Sorry, I wasn't familiar with Surface_mesh. It's a cool class, I can add faces on the fly and extract the indices of the inner edges. Would it be straightforward to do the same for convex partition? -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 That works nicely, thanks. Would it work with CGAL::optimal_convex_partition_2 as well? -- Sent from: http://cgal-discuss.949826.n4.nabble.com/-- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|

## Re: Partition a 2D polygon - extract graph faces

 yes, it does. On 4/4/2019 11:24 PM, Zohar wrote: That works nicely, thanks. Would it work with CGAL::optimal_convex_partition_2 as well? -- Sent from: http://cgal-discuss.949826.n4.nabble.com/ -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri