Partition a 2D polygon - extract graph faces

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Partition a 2D polygon - extract graph faces

Zohar
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/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

andreas.fabri


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
Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

Zohar

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


Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

andreas.fabri


Instead of vertex_descriptor of a Surface_mesh, you might store a std::list<Point_2>::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
Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

Zohar
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


Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

andreas.fabri

I think I also made it work for convex partition.

See https://github.com/CGAL/cgal/pull/3826

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
Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

Zohar
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


Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

andreas.fabri

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
Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

Zohar
Sorry, I didn't notice that you changed Rotation_tree_2.h as well. It works
fine after I updated to cgal4.14. Great, thanks.



--
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


Reply | Threaded
Open this post in threaded view
|

Re: Partition a 2D polygon - extract graph faces

andreas.fabri

We generalized that further in this pull request:

https://github.com/CGAL/cgal/pull/3848

and the example given in the online documentation of the PR here:

https://cgal.geometryfactory.com/~afabri/Partition_2/Partition_2/index.html#title3

Best,

Andreas

On 4/5/2019 1:12 PM, Zohar wrote:
Sorry, I didn't notice that you changed Rotation_tree_2.h as well. It works
fine after I updated to cgal4.14. Great, thanks.



--
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