Polygon intersection with duplicated vertex

[Alison-97]

Issue Details

I've created two polygons to check if they intersect with each other. The code runs and produces result when the two polygons are far apart that their square boundary boxes are not overlapping. But when an additional point is added, which extends the shape of the polygon, making the two square boundary boxes overlap, there's a precondition violation error.
Note: In both scenario the polygons do not actually intersect, the difference lies in the overlapping of their square boundary boxes.

What's strange is that the test with the additional point runs fine previously in CGAL 4.11, but failed in CGAL 5.5.

Source Code

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <CGAL/Polygon_2.h>
#include <CGAL/Boolean_set_operations_2/do_intersect.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Polygon_2<K>                                  Polygon_2;
typedef CGAL::Point_2<K>                                    Point_2;
typedef std::map<int, Polygon_2>                            PolygonIndex;
typedef PolygonIndex::iterator                              Iterator;
typedef CGAL::Box_intersection_d::Box_with_handle_d<double, 2, Iterator>    Box;


struct KeyValuePair
{
    int key;
    int value;
    KeyValuePair(int ee1, int ee2) {
        key = ee1;
        value = ee2;
    };
};

std::list<KeyValuePair> intersectedPairList;

void CollectAllIntersectPairs(const Box& a, const Box& b)
{
    Iterator ait = a.handle();
    Iterator bit = b.handle();

    Polygon_2 pol1 = (*ait).second;
    Polygon_2 pol2 = (*bit).second;
    bool isIntersect = CGAL::do_intersect(pol1, pol2);

    if (isIntersect)
    {
        KeyValuePair kyPair = KeyValuePair((*ait).first, (*bit).first);
        intersectedPairList.push_back(kyPair);
    }
}

auto callback (const Box& a, const Box& b) { CollectAllIntersectPairs(a, b); };


int main(int argc, char* argv[])
{
    Polygon_2 pol1;
    pol1.push_back(Point_2(0, 0));
    pol1.push_back(Point_2(4, 0));
    pol1.push_back(Point_2(0, 4));

    Polygon_2 pol2;
    pol2.push_back(Point_2(5, 3));
    pol2.push_back(Point_2(6, 3));
    pol2.push_back(Point_2(5, 4));
    pol2.push_back(Point_2(5, 4));
    pol2.push_back(Point_2(3, 4));      // Adding this point introduce a runtime error
    // adding that point extends the shape of the pol2, causing the boundary box of pol1 & pol2 to overlap

    std::vector<Polygon_2> polies;
    polies.push_back(pol1);
    polies.push_back(pol2);

    PolygonIndex   faces;
    for (unsigned int i = 0; i < polies.size(); i++)
    {
        faces.insert(std::pair<int, Polygon_2>(i, polies[i]));
    }

    // Create the corresponding vector of bounding boxes
    std::vector<Box> boxes;
    for (Iterator i = faces.begin(); i != faces.end(); ++i) {
        Polygon_2 poly = i->second;
        boxes.push_back(Box(poly.bbox(), i));
    }

    CGAL::box_self_intersection_d(boxes.begin(), boxes.end(), callback);

    return 0;
}   

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Windows 11 version 21H2, 64 bits
• Compiler: Visual Studio 2022
• Release or debug mode: Debug
• CGAL version: 5.5
• Boost version: 1_65_1

[Alison-97]

I've tried using Exact_predicates_exact_constructions_kernel instead of Exact_predicates_inexact_constructions_kernel as suggested here but the error persists.
I've also written a short function that indicates the problem with duplicated vertex, where a same error is thrown.

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <list>
#include <CGAL/Boolean_set_operations_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel	K;
typedef CGAL::Polygon_2<K>                                  Polygon_2;
typedef CGAL::Polygon_with_holes_2<K>                       Polygon_with_holes_2;
typedef CGAL::Point_2<K>                                    Point_2;

void main()
{
	Polygon_2 p;
	p.push_back(Point_2(0, 0));
	p.push_back(Point_2(1, 0));
	p.push_back(Point_2(1, 1));

	Polygon_2 p1;
	p1.push_back(Point_2(0, 0));
	p1.push_back(Point_2(1, 0));
	p1.push_back(Point_2(1, 1));
	p1.push_back(Point_2(1, 1));     // this duplicated point causes the error in CGAL 5.5

	std::list<Polygon_2> polies;

	polies.push_back(p);
	polies.push_back(p1);

	Polygon_with_holes_2 polyHole;

	CGAL::join(p, p1, polyHole);
}

[efifogel]

You have two duplicate points in the second polygon: pol2.push_back(Point_2(5, 4)); pol2.push_back(Point_2(5, 4)); You also get a meaningful error message: Explanation: Cannot construct a degenerated segment Remove one of the lines above and it will work just fine.

…

____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

On Thu, 1 Sept 2022 at 05:30, Alison-97 ***@***.***> wrote: Issue Details I've created two polygons to check if they intersect with each other. The code runs and produces result when the two polygons are far apart that their square boundary boxes are not overlapping. But when an additional point is added, which extends the shape of the polygon, making the two square boundary boxes overlap, there's a precondition violation error. Note: In both scenario the polygons do not actually intersect, the difference lies in the overlapping of their square boundary boxes. What's strange is that the test with the additional point runs fine previously in CGAL 4.11, but failed in CGAL 5.5. Source Code #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/box_intersection_d.h> #include <vector> #include <CGAL/Polygon_2.h> #include <CGAL/Boolean_set_operations_2/do_intersect.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Polygon_2<K> Polygon_2; typedef CGAL::Point_2<K> Point_2; typedef std::map<int, Polygon_2> PolygonIndex; typedef PolygonIndex::iterator Iterator; typedef CGAL::Box_intersection_d::Box_with_handle_d<double, 2, Iterator> Box; struct KeyValuePair { int key; int value; KeyValuePair(int ee1, int ee2) { key = ee1; value = ee2; }; }; std::list<KeyValuePair> intersectedPairList; void CollectAllIntersectPairs(const Box& a, const Box& b) { Iterator ait = a.handle(); Iterator bit = b.handle(); Polygon_2 pol1 = (*ait).second; Polygon_2 pol2 = (*bit).second; bool isIntersect = CGAL::do_intersect(pol1, pol2); if (isIntersect) { KeyValuePair kyPair = KeyValuePair((*ait).first, (*bit).first); intersectedPairList.push_back(kyPair); } } auto callback (const Box& a, const Box& b) { CollectAllIntersectPairs(a, b); }; int main(int argc, char* argv[]) { Polygon_2 pol1; pol1.push_back(Point_2(0, 0)); pol1.push_back(Point_2(4, 0)); pol1.push_back(Point_2(0, 4)); Polygon_2 pol2; pol2.push_back(Point_2(5, 3)); pol2.push_back(Point_2(6, 3)); pol2.push_back(Point_2(5, 4)); pol2.push_back(Point_2(5, 4)); pol2.push_back(Point_2(3, 4)); // Adding this point introduce a runtime error // adding that point extends the shape of the pol2, causing the boundary box of pol1 & pol2 to overlap std::vector<Polygon_2> polies; polies.push_back(pol1); polies.push_back(pol2); PolygonIndex faces; for (unsigned int i = 0; i < polies.size(); i++) { faces.insert(std::pair<int, Polygon_2>(i, polies[i])); } // Create the corresponding vector of bounding boxes std::vector<Box> boxes; for (Iterator i = faces.begin(); i != faces.end(); ++i) { Polygon_2 poly = i->second; boxes.push_back(Box(poly.bbox(), i)); } CGAL::box_self_intersection_d(boxes.begin(), boxes.end(), callback); return 0; } Environment - Operating system (Windows/Mac/Linux, 32/64 bits): Windows 11 version 21H2, 64 bits - Compiler: Visual Studio 2022 - Release or debug mode: Debug - CGAL version: 5.5 - Boost version: 1_65_1 — Reply to this email directly, view it on GitHub <#6821>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNODF67SQCGFXZJ4ELHLV4AIOFANCNFSM6AAAAAAQB5LROY> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[Alison-97]

Is this an intended behavior in the latest CGAL? Or is there an option to permit such duplication of points without throwing error as in the previous versions like CGAL 4.11?

[efifogel]

It has never been permitted! ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Thu, 1 Sept 2022 at 11:20, Alison-97 ***@***.***> wrote: Is this an intended behavior in the latest CGAL? Or is there an option to permit such duplication of points without throwing error as in the previous versions like CGAL 4.11? — Reply to this email directly, view it on GitHub <#6821 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNODZYOVZT6T7QUXIVHLV4BRNFANCNFSM6AAAAAAQB5LROY> . You are receiving this because you commented.Message ID: ***@***.***>

[Alison-97]

Sorry that I've oversimplified the code in the original post that the duplicated points were next to each other. What I meant for duplicated point is actually the following (I've made the necessary changes in polygon pol2):

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
#include <vector>
#include <CGAL/Polygon_2.h>
#include <CGAL/Boolean_set_operations_2/do_intersect.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef CGAL::Polygon_2<K>                                  Polygon_2;
typedef CGAL::Point_2<K>                                    Point_2;
typedef std::map<int, Polygon_2>                            PolygonIndex;
typedef PolygonIndex::iterator                              Iterator;
typedef CGAL::Box_intersection_d::Box_with_handle_d<double, 2, Iterator>    Box;


struct KeyValuePair
{
    int key;
    int value;
    KeyValuePair(int ee1, int ee2) {
        key = ee1;
        value = ee2;
    };
};

std::list<KeyValuePair> intersectedPairList;

void CollectAllIntersectPairs(const Box& a, const Box& b)
{
    Iterator ait = a.handle();
    Iterator bit = b.handle();

    Polygon_2 pol1 = (*ait).second;
    Polygon_2 pol2 = (*bit).second;
    bool isIntersect = CGAL::do_intersect(pol1, pol2);

    if (isIntersect)
    {
        KeyValuePair kyPair = KeyValuePair((*ait).first, (*bit).first);
        intersectedPairList.push_back(kyPair);
    }
}

auto callback (const Box& a, const Box& b) { CollectAllIntersectPairs(a, b); };


int main(int argc, char* argv[])
{
    Polygon_2 pol1;
    pol1.push_back(Point_2(0, 0));
    pol1.push_back(Point_2(4, 0));
    pol1.push_back(Point_2(0, 4));

    Polygon_2 pol2;
    pol2.push_back(Point_2(0, 10));
    pol2.push_back(Point_2(10, 10));
    pol2.push_back(Point_2(5, 5));
    pol2.push_back(Point_2(10, 0));
    pol2.push_back(Point_2(0, 0));      
    pol2.push_back(Point_2(5, 5));      

    std::vector<Polygon_2> polies;
    polies.push_back(pol1);
    polies.push_back(pol2);

    PolygonIndex   faces;
    for (unsigned int i = 0; i < polies.size(); i++)
    {
        faces.insert(std::pair<int, Polygon_2>(i, polies[i]));
    }

    // Create the corresponding vector of bounding boxes
    std::vector<Box> boxes;
    for (Iterator i = faces.begin(); i != faces.end(); ++i) {
        Polygon_2 poly = i->second;
        boxes.push_back(Box(poly.bbox(), i));
    }

    CGAL::box_self_intersection_d(boxes.begin(), boxes.end(), callback);

    return 0;
}   

Here's a simple illustration of the polygons and the issue I'm facing. The error occurs when pol1 is in position A, but not when it is moved to position B. And the error only throws in CGAL 5.5, but not CGAL 4.11.

[efifogel]

This is an invalid polygon. See, e.g., the figure in the manual at https://doc.cgal.org/latest/Boolean_set_operations_2/index.html#fig__simpleDefsExamples and the explanation that follows. ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Thu, 1 Sept 2022 at 13:00, Alison-97 ***@***.***> wrote: Sorry that I've oversimplified the code in the original post that the duplicated points were next to each other. What I meant for duplicated point is actually the following (I've made the necessary changes in polygon pol2): #include <CGAL/Exact_predicates_exact_constructions_kernel.h> #include <CGAL/box_intersection_d.h> #include <vector> #include <CGAL/Polygon_2.h> #include <CGAL/Boolean_set_operations_2/do_intersect.h> typedef CGAL::Exact_predicates_exact_constructions_kernel K; typedef CGAL::Polygon_2<K> Polygon_2; typedef CGAL::Point_2<K> Point_2; typedef std::map<int, Polygon_2> PolygonIndex; typedef PolygonIndex::iterator Iterator; typedef CGAL::Box_intersection_d::Box_with_handle_d<double, 2, Iterator> Box; struct KeyValuePair { int key; int value; KeyValuePair(int ee1, int ee2) { key = ee1; value = ee2; }; }; std::list<KeyValuePair> intersectedPairList; void CollectAllIntersectPairs(const Box& a, const Box& b) { Iterator ait = a.handle(); Iterator bit = b.handle(); Polygon_2 pol1 = (*ait).second; Polygon_2 pol2 = (*bit).second; bool isIntersect = CGAL::do_intersect(pol1, pol2); if (isIntersect) { KeyValuePair kyPair = KeyValuePair((*ait).first, (*bit).first); intersectedPairList.push_back(kyPair); } } auto callback (const Box& a, const Box& b) { CollectAllIntersectPairs(a, b); }; int main(int argc, char* argv[]) { Polygon_2 pol1; pol1.push_back(Point_2(0, 0)); pol1.push_back(Point_2(4, 0)); pol1.push_back(Point_2(0, 4)); Polygon_2 pol2; pol2.push_back(Point_2(0, 10)); pol2.push_back(Point_2(10, 10)); pol2.push_back(Point_2(5, 5)); pol2.push_back(Point_2(10, 0)); pol2.push_back(Point_2(0, 0)); pol2.push_back(Point_2(5, 5)); std::vector<Polygon_2> polies; polies.push_back(pol1); polies.push_back(pol2); PolygonIndex faces; for (unsigned int i = 0; i < polies.size(); i++) { faces.insert(std::pair<int, Polygon_2>(i, polies[i])); } // Create the corresponding vector of bounding boxes std::vector<Box> boxes; for (Iterator i = faces.begin(); i != faces.end(); ++i) { Polygon_2 poly = i->second; boxes.push_back(Box(poly.bbox(), i)); } CGAL::box_self_intersection_d(boxes.begin(), boxes.end(), callback); return 0; } Here's a simple illustration of the polygons and the issue I'm facing. The error occurs when pol1 is in position A, but not when it is moved to position B. And the error only throws in CGAL 5.5, but not CGAL 4.11. [image: image] <https://user-images.githubusercontent.com/97237245/187887597-28c323cd-700c-4488-a7b8-24f6ae3af501.png> — Reply to this email directly, view it on GitHub <#6822 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHGIEVZXBXQYTDUDBTV4B5CNANCNFSM6AAAAAAQCGANQY> . You are receiving this because you commented.Message ID: ***@***.***>