Simple Polygon Difference Results in Non-Simple Polygon

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

Simple Polygon Difference Results in Non-Simple Polygon

Bryant
When taking the difference between a /simple/ Polygon_set_2 and a /simple/
Polygon_2, the result may be non-simple. This appears to occur when one
would expect the difference to result in two polygons with holes that share
a point.

I use the following definitions:
- A Polygon_set_2 is simple if the Polygon_with_holes_2s composing it are
simple.
- A Polygon_with_holes_2 is simple if its outer boundary and holes are
simple.

Here's a minimum working example:
        CGAL::Polygon_2<K> poly1;
        poly1.push_back(CGAL::Point_2<K>(0, 0));
        poly1.push_back(CGAL::Point_2<K>(2, 0));
        poly1.push_back(CGAL::Point_2<K>(2, 1));
        poly1.push_back(CGAL::Point_2<K>(1, 1));
        poly1.push_back(CGAL::Point_2<K>(1, 2));
        poly1.push_back(CGAL::Point_2<K>(0, 2));
        CGAL::Polygon_set_2<K> poly_set(poly1);

        CGAL::Polygon_2<K> hole;
        hole.push_back(CGAL::Point_2<K>(0, 0));
        hole.push_back(CGAL::Point_2<K>(1, 0));
        hole.push_back(CGAL::Point_2<K>(1, 1));
        hole.push_back(CGAL::Point_2<K>(0, 1));

        poly_set.difference(hole);

Note: I have only tested with the EPEC Kernel.

The above code results in poly_set containing the following polygon:
(0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)

I would expect it to contain the following polygons:
(1, 0), (2, 0), (2, 1), (1, 1)
        and
(0, 1), (1, 1), (1, 2), (0, 2)




--
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: Simple Polygon Difference Results in Non-Simple Polygon

Efi Fogel
I haven't tested it myself, but if you meant to say:

The above code results in poly_set containing a polygon with holes with the following outer boundary:
(0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)

Then there is no problem, cause according to the rules the boundary is a relatively simple polygon; see https://doc.cgal.org/latest/Boolean_set_operations_2/index.html
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Wed, 20 Feb 2019 at 06:17, Bryant <[hidden email]> wrote:
When taking the difference between a /simple/ Polygon_set_2 and a /simple/
Polygon_2, the result may be non-simple. This appears to occur when one
would expect the difference to result in two polygons with holes that share
a point.

I use the following definitions:
- A Polygon_set_2 is simple if the Polygon_with_holes_2s composing it are
simple.
- A Polygon_with_holes_2 is simple if its outer boundary and holes are
simple.

Here's a minimum working example:
        CGAL::Polygon_2<K> poly1;
        poly1.push_back(CGAL::Point_2<K>(0, 0));
        poly1.push_back(CGAL::Point_2<K>(2, 0));
        poly1.push_back(CGAL::Point_2<K>(2, 1));
        poly1.push_back(CGAL::Point_2<K>(1, 1));
        poly1.push_back(CGAL::Point_2<K>(1, 2));
        poly1.push_back(CGAL::Point_2<K>(0, 2));
        CGAL::Polygon_set_2<K> poly_set(poly1);

        CGAL::Polygon_2<K> hole;
        hole.push_back(CGAL::Point_2<K>(0, 0));
        hole.push_back(CGAL::Point_2<K>(1, 0));
        hole.push_back(CGAL::Point_2<K>(1, 1));
        hole.push_back(CGAL::Point_2<K>(0, 1));

        poly_set.difference(hole);

Note: I have only tested with the EPEC Kernel.

The above code results in poly_set containing the following polygon:
(0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)

I would expect it to contain the following polygons:
(1, 0), (2, 0), (2, 1), (1, 1)
        and
(0, 1), (1, 1), (1, 2), (0, 2)




--
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: Simple Polygon Difference Results in Non-Simple Polygon

Bryant
Thank you for your reply!

You were correct that I meant:

> The above code results in poly_set containing
/*
> a polygon with holes with the following outer boundary
*/
I'm still surprised that I never came across this fact while reading the
docs.

Nevertheless, do you know of a /built-in/ way of converting a relatively
simple polygon into a list of simple ones? I'm not finding anything online.


Efi Fogel wrote

> I haven't tested it myself, but if you meant to say:
>
> The above code results in poly_set containing *a polygon with holes with
> the following outer boundary*:
> (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)
>
> Then there is no problem, cause according to the rules the boundary is a
> relatively simple polygon; see
> https://doc.cgal.org/latest/Boolean_set_operations_2/index.html
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
>
> On Wed, 20 Feb 2019 at 06:17, Bryant &lt;

> bryantcurto@

> &gt; wrote:
>
>> When taking the difference between a /simple/ Polygon_set_2 and a
>> /simple/
>> Polygon_2, the result may be non-simple. This appears to occur when one
>> would expect the difference to result in two polygons with holes that
>> share
>> a point.
>>
>> I use the following definitions:
>> - A Polygon_set_2 is simple if the Polygon_with_holes_2s composing it are
>> simple.
>> - A Polygon_with_holes_2 is simple if its outer boundary and holes are
>> simple.
>>
>> Here's a minimum working example:
>>         CGAL::Polygon_2
> <K>
>  poly1;
>>         poly1.push_back(CGAL::Point_2
> <K>
> (0, 0));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (2, 0));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (2, 1));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (1, 1));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (1, 2));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (0, 2));
>>         CGAL::Polygon_set_2
> <K>
>  poly_set(poly1);
>>
>>         CGAL::Polygon_2
> <K>
>  hole;
>>         hole.push_back(CGAL::Point_2
> <K>
> (0, 0));
>>         hole.push_back(CGAL::Point_2
> <K>
> (1, 0));
>>         hole.push_back(CGAL::Point_2
> <K>
> (1, 1));
>>         hole.push_back(CGAL::Point_2
> <K>
> (0, 1));
>>
>>         poly_set.difference(hole);
>>
>> Note: I have only tested with the EPEC Kernel.
>>
>> The above code results in poly_set containing the following polygon:
>> (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)
>>
>> I would expect it to contain the following polygons:
>> (1, 0), (2, 0), (2, 1), (1, 1)
>>         and
>> (0, 1), (1, 1), (1, 2), (0, 2)
>>
>>
>>
>>
>> --
>> 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
>>
>>
>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss





--
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: Simple Polygon Difference Results in Non-Simple Polygon

Efi Fogel
This could be a nice addition.
What you could do right now is construct an arrangement from the polygons and then traverse the faces of the arrangement.
Better yet, you can extract the arrangement directly from the Polygon_set_2 object; something like the following:

Polygon_set_2 ps;
<fill ps>
const auto& arr = ps.arrangement()
for (auto it = arr.faces_begin(); it != arr.faces_end(); ++it) {
  ...
}
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Thu, 21 Feb 2019 at 10:11, Bryant <[hidden email]> wrote:
Thank you for your reply!

You were correct that I meant:

> The above code results in poly_set containing
/*
> a polygon with holes with the following outer boundary
*/
I'm still surprised that I never came across this fact while reading the
docs.

Nevertheless, do you know of a /built-in/ way of converting a relatively
simple polygon into a list of simple ones? I'm not finding anything online.


Efi Fogel wrote
> I haven't tested it myself, but if you meant to say:
>
> The above code results in poly_set containing *a polygon with holes with
> the following outer boundary*:
> (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)
>
> Then there is no problem, cause according to the rules the boundary is a
> relatively simple polygon; see
> https://doc.cgal.org/latest/Boolean_set_operations_2/index.html
>    ____  _        ____             _
>   /_____/_) o    /__________  __  //
>  (____ (   (    (    (_/ (_/-(-'_(/
>                          _/
>
>
>
>
> On Wed, 20 Feb 2019 at 06:17, Bryant &lt;

> bryantcurto@

> &gt; wrote:
>
>> When taking the difference between a /simple/ Polygon_set_2 and a
>> /simple/
>> Polygon_2, the result may be non-simple. This appears to occur when one
>> would expect the difference to result in two polygons with holes that
>> share
>> a point.
>>
>> I use the following definitions:
>> - A Polygon_set_2 is simple if the Polygon_with_holes_2s composing it are
>> simple.
>> - A Polygon_with_holes_2 is simple if its outer boundary and holes are
>> simple.
>>
>> Here's a minimum working example:
>>         CGAL::Polygon_2
> <K>
>  poly1;
>>         poly1.push_back(CGAL::Point_2
> <K>
> (0, 0));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (2, 0));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (2, 1));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (1, 1));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (1, 2));
>>         poly1.push_back(CGAL::Point_2
> <K>
> (0, 2));
>>         CGAL::Polygon_set_2
> <K>
>  poly_set(poly1);
>>
>>         CGAL::Polygon_2
> <K>
>  hole;
>>         hole.push_back(CGAL::Point_2
> <K>
> (0, 0));
>>         hole.push_back(CGAL::Point_2
> <K>
> (1, 0));
>>         hole.push_back(CGAL::Point_2
> <K>
> (1, 1));
>>         hole.push_back(CGAL::Point_2
> <K>
> (0, 1));
>>
>>         poly_set.difference(hole);
>>
>> Note: I have only tested with the EPEC Kernel.
>>
>> The above code results in poly_set containing the following polygon:
>> (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2)
>>
>> I would expect it to contain the following polygons:
>> (1, 0), (2, 0), (2, 1), (1, 1)
>>         and
>> (0, 1), (1, 1), (1, 2), (0, 2)
>>
>>
>>
>>
>> --
>> 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
>>
>>
>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss





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