CGAL::difference for 2d polygon return a incorrect result polygon

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

CGAL::difference for 2d polygon return a incorrect result polygon

Luoyu
Hi,
    I'm newer to use cgal, I want to split the given polygon by another
polygon. Then I choose the CGAL::difference function. But in some cases,
it's function return incorrect result polygon for me.

Here is my code:

// TArray is a template for an array, FVector2D is a struct for a 2d point,
use float number type.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Polygon_set_2.h>

#include <list>

typedef CGAL::Exact_predicates_exact_constructions_kernel exactKernel;
typedef exactKernel::Point_2                              exactPoint_2;
typedef CGAL::Polygon_2<exactKernel>                      exactPolygon_2;
typedef CGAL::Polygon_with_holes_2<exactKernel>          
exactPolygon_with_holes_2;
typedef CGAL::Polygon_set_2<exactKernel>                
exactPolygon_set_2;
typedef exactKernel::Segment_2                            exactSegment_2;
typedef exactKernel::Point_2  exactPoint_2;
typedef exactKernel::Vector_2  exactVector_2;

void UPaveMethodFunctionLibrary::FiltrationPolygon(const
TArray<FPolygonData>& InHolesPolygon, TArray<FVector2D>&
OutFiltrationPolygon)
{
        if (OutFiltrationPolygon.Num() < 3 || InHolesPolygon.Num() == 0){
                return;
        }

        exactPolygon_2 targetPolygon;
        std::list<exactPolygon_2> holesPolygon;

        for (int32 filtrationPolygonIndex = 0; filtrationPolygonIndex <
OutFiltrationPolygon.Num(); ++filtrationPolygonIndex)
        {
       
targetPolygon.push_back(exactPoint_2(OutFiltrationPolygon[filtrationPolygonIndex].X,
OutFiltrationPolygon[filtrationPolygonIndex].Y));
        }

        if (targetPolygon.is_clockwise_oriented()) {
                targetPolygon.reverse_orientation();
        }

        for (int32 holePolygonIndex = 0; holePolygonIndex < InHolesPolygon.Num();
++holePolygonIndex)
        {
                exactPolygon_2 currentHolePolygon;

                for (int32 holePointIndex = 0; holePointIndex <
InHolesPolygon[holePolygonIndex].Polygon.Num(); ++holePointIndex)
                {
               
currentHolePolygon.push_back(exactPoint_2(InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].X,
InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].Y));
                }

                if (currentHolePolygon.is_clockwise_oriented()) {
                        currentHolePolygon.reverse_orientation();
                }

                holesPolygon.push_back(currentHolePolygon);
        }

        bool IsExistInList = false;

        std::list<exactPolygon_2> tempholesPolygon;
       
        for (std::list<exactPolygon_2>::const_iterator holePolygonListIt =
holesPolygon.cbegin(); holePolygonListIt != holesPolygon.cend();
++holePolygonListIt)
        {
                for (exactPolygon_2::Edge_const_iterator holePolygonIt =
holePolygonListIt->edges_begin(); holePolygonIt !=
holePolygonListIt->edges_end(); ++holePolygonIt)
                {
                        for (exactPolygon_2::Edge_const_iterator targetPolygonIt =
targetPolygon.edges_begin(); targetPolygonIt != targetPolygon.edges_end();
++targetPolygonIt)
                        {
                                if (targetPolygonIt->collinear_has_on(holePolygonIt->start()) &&
targetPolygonIt->collinear_has_on(holePolygonIt->end()))
                                {
                                        IsExistInList = true;
                                        tempholesPolygon.push_back(*holePolygonListIt);
                                        break;
                                }
                        }
                        if (IsExistInList){
                                break;
                        }
                }
                IsExistInList = false;
        }

        if (tempholesPolygon.size() == 0){
                return;
        }

        for (exactPolygon_2 currentHolePolygon : tempholesPolygon)
        {
                std::list<exactPolygon_with_holes_2> differencePolygons;

                CGAL::difference(targetPolygon, currentHolePolygon,
std::back_inserter(differencePolygons));

                if (differencePolygons.size() != 1) {
                        return;
                }

                targetPolygon = differencePolygons.front().outer_boundary();
                if (targetPolygon.is_clockwise_oriented()) {
                        targetPolygon.reverse_orientation();
                }
        }
       
        if (targetPolygon.size() < 3 || !targetPolygon.is_simple()){
                return;
        }

        OutFiltrationPolygon.Empty();

        for (exactPolygon_2::Vertex_const_iterator it =
targetPolygon.vertices_begin(); it != targetPolygon.vertices_end(); it++)
        {
                double pointX = CGAL::to_double(it->x());
                double pointY = CGAL::to_double(it->y());
                OutFiltrationPolygon.AddUnique(FVector2D(pointX, pointY));
        }
}



--
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: CGAL::difference for 2d polygon return a incorrect result polygon

Efi Fogel
Please provide a simple test case, nicely indented, using only point type from EPEC (exact predicates exact constructions),  that can be used to reproduce the problem.

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




On Sun, 26 Apr 2020 at 13:14, Luoyu <[hidden email]> wrote:
Hi,
    I'm newer to use cgal, I want to split the given polygon by another
polygon. Then I choose the CGAL::difference function. But in some cases,
it's function return incorrect result polygon for me.

Here is my code:

// TArray is a template for an array, FVector2D is a struct for a 2d point,
use float number type.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Polygon_set_2.h>

#include <list>

typedef CGAL::Exact_predicates_exact_constructions_kernel exactKernel;
typedef exactKernel::Point_2                              exactPoint_2;
typedef CGAL::Polygon_2<exactKernel>                      exactPolygon_2;
typedef CGAL::Polygon_with_holes_2<exactKernel>         
exactPolygon_with_holes_2;
typedef CGAL::Polygon_set_2<exactKernel>                 
exactPolygon_set_2;
typedef exactKernel::Segment_2                            exactSegment_2;
typedef exactKernel::Point_2                                                      exactPoint_2;
typedef exactKernel::Vector_2                                                     exactVector_2;

void UPaveMethodFunctionLibrary::FiltrationPolygon(const
TArray<FPolygonData>& InHolesPolygon, TArray<FVector2D>&
OutFiltrationPolygon)
{
        if (OutFiltrationPolygon.Num() < 3 || InHolesPolygon.Num() == 0){
                return;
        }

        exactPolygon_2 targetPolygon;
        std::list<exactPolygon_2> holesPolygon;

        for (int32 filtrationPolygonIndex = 0; filtrationPolygonIndex <
OutFiltrationPolygon.Num(); ++filtrationPolygonIndex)
        {

targetPolygon.push_back(exactPoint_2(OutFiltrationPolygon[filtrationPolygonIndex].X,
OutFiltrationPolygon[filtrationPolygonIndex].Y));
        }

        if (targetPolygon.is_clockwise_oriented()) {
                targetPolygon.reverse_orientation();
        }

        for (int32 holePolygonIndex = 0; holePolygonIndex < InHolesPolygon.Num();
++holePolygonIndex)
        {
                exactPolygon_2 currentHolePolygon;

                for (int32 holePointIndex = 0; holePointIndex <
InHolesPolygon[holePolygonIndex].Polygon.Num(); ++holePointIndex)
                {

currentHolePolygon.push_back(exactPoint_2(InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].X,
InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].Y));
                }

                if (currentHolePolygon.is_clockwise_oriented()) {
                        currentHolePolygon.reverse_orientation();
                }

                holesPolygon.push_back(currentHolePolygon);
        }

        bool IsExistInList = false;

        std::list<exactPolygon_2> tempholesPolygon;

        for (std::list<exactPolygon_2>::const_iterator holePolygonListIt =
holesPolygon.cbegin(); holePolygonListIt != holesPolygon.cend();
++holePolygonListIt)
        {
                for (exactPolygon_2::Edge_const_iterator holePolygonIt =
holePolygonListIt->edges_begin(); holePolygonIt !=
holePolygonListIt->edges_end(); ++holePolygonIt)
                {
                        for (exactPolygon_2::Edge_const_iterator targetPolygonIt =
targetPolygon.edges_begin(); targetPolygonIt != targetPolygon.edges_end();
++targetPolygonIt)
                        {
                                if (targetPolygonIt->collinear_has_on(holePolygonIt->start()) &&
targetPolygonIt->collinear_has_on(holePolygonIt->end()))
                                {
                                        IsExistInList = true;
                                        tempholesPolygon.push_back(*holePolygonListIt);
                                        break;
                                }
                        }
                        if (IsExistInList){
                                break;
                        }
                }
                IsExistInList = false;
        }

        if (tempholesPolygon.size() == 0){
                return;
        }

        for (exactPolygon_2 currentHolePolygon : tempholesPolygon)
        {
                std::list<exactPolygon_with_holes_2> differencePolygons;

                CGAL::difference(targetPolygon, currentHolePolygon,
std::back_inserter(differencePolygons));

                if (differencePolygons.size() != 1) {
                        return;
                }

                targetPolygon = differencePolygons.front().outer_boundary();
                if (targetPolygon.is_clockwise_oriented()) {
                        targetPolygon.reverse_orientation();
                }
        }

        if (targetPolygon.size() < 3 || !targetPolygon.is_simple()){
                return;
        }

        OutFiltrationPolygon.Empty();

        for (exactPolygon_2::Vertex_const_iterator it =
targetPolygon.vertices_begin(); it != targetPolygon.vertices_end(); it++)
        {
                double pointX = CGAL::to_double(it->x());
                double pointY = CGAL::to_double(it->y());
                OutFiltrationPolygon.AddUnique(FVector2D(pointX, pointY));
        }
}



--
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: CGAL::difference for 2d polygon return a incorrect result polygon

Luoyu
sorry, i sent another email for my question contain my simple test code and test data, please ignore this one

发自我的iPhone

在 2020年4月26日,下午7:00,Efi Fogel <[hidden email]> 写道:


Please provide a simple test case, nicely indented, using only point type from EPEC (exact predicates exact constructions),  that can be used to reproduce the problem.

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




On Sun, 26 Apr 2020 at 13:14, Luoyu <[hidden email]> wrote:
Hi,
    I'm newer to use cgal, I want to split the given polygon by another
polygon. Then I choose the CGAL::difference function. But in some cases,
it's function return incorrect result polygon for me.

Here is my code:

// TArray is a template for an array, FVector2D is a struct for a 2d point,
use float number type.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Polygon_set_2.h>

#include <list>

typedef CGAL::Exact_predicates_exact_constructions_kernel exactKernel;
typedef exactKernel::Point_2                              exactPoint_2;
typedef CGAL::Polygon_2<exactKernel>                      exactPolygon_2;
typedef CGAL::Polygon_with_holes_2<exactKernel>         
exactPolygon_with_holes_2;
typedef CGAL::Polygon_set_2<exactKernel>                 
exactPolygon_set_2;
typedef exactKernel::Segment_2                            exactSegment_2;
typedef exactKernel::Point_2                                                      exactPoint_2;
typedef exactKernel::Vector_2                                                     exactVector_2;

void UPaveMethodFunctionLibrary::FiltrationPolygon(const
TArray<FPolygonData>& InHolesPolygon, TArray<FVector2D>&
OutFiltrationPolygon)
{
        if (OutFiltrationPolygon.Num() < 3 || InHolesPolygon.Num() == 0){
                return;
        }

        exactPolygon_2 targetPolygon;
        std::list<exactPolygon_2> holesPolygon;

        for (int32 filtrationPolygonIndex = 0; filtrationPolygonIndex <
OutFiltrationPolygon.Num(); ++filtrationPolygonIndex)
        {

targetPolygon.push_back(exactPoint_2(OutFiltrationPolygon[filtrationPolygonIndex].X,
OutFiltrationPolygon[filtrationPolygonIndex].Y));
        }

        if (targetPolygon.is_clockwise_oriented()) {
                targetPolygon.reverse_orientation();
        }

        for (int32 holePolygonIndex = 0; holePolygonIndex < InHolesPolygon.Num();
++holePolygonIndex)
        {
                exactPolygon_2 currentHolePolygon;

                for (int32 holePointIndex = 0; holePointIndex <
InHolesPolygon[holePolygonIndex].Polygon.Num(); ++holePointIndex)
                {

currentHolePolygon.push_back(exactPoint_2(InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].X,
InHolesPolygon[holePolygonIndex].Polygon[holePointIndex].Y));
                }

                if (currentHolePolygon.is_clockwise_oriented()) {
                        currentHolePolygon.reverse_orientation();
                }

                holesPolygon.push_back(currentHolePolygon);
        }

        bool IsExistInList = false;

        std::list<exactPolygon_2> tempholesPolygon;

        for (std::list<exactPolygon_2>::const_iterator holePolygonListIt =
holesPolygon.cbegin(); holePolygonListIt != holesPolygon.cend();
++holePolygonListIt)
        {
                for (exactPolygon_2::Edge_const_iterator holePolygonIt =
holePolygonListIt->edges_begin(); holePolygonIt !=
holePolygonListIt->edges_end(); ++holePolygonIt)
                {
                        for (exactPolygon_2::Edge_const_iterator targetPolygonIt =
targetPolygon.edges_begin(); targetPolygonIt != targetPolygon.edges_end();
++targetPolygonIt)
                        {
                                if (targetPolygonIt->collinear_has_on(holePolygonIt->start()) &&
targetPolygonIt->collinear_has_on(holePolygonIt->end()))
                                {
                                        IsExistInList = true;
                                        tempholesPolygon.push_back(*holePolygonListIt);
                                        break;
                                }
                        }
                        if (IsExistInList){
                                break;
                        }
                }
                IsExistInList = false;
        }

        if (tempholesPolygon.size() == 0){
                return;
        }

        for (exactPolygon_2 currentHolePolygon : tempholesPolygon)
        {
                std::list<exactPolygon_with_holes_2> differencePolygons;

                CGAL::difference(targetPolygon, currentHolePolygon,
std::back_inserter(differencePolygons));

                if (differencePolygons.size() != 1) {
                        return;
                }

                targetPolygon = differencePolygons.front().outer_boundary();
                if (targetPolygon.is_clockwise_oriented()) {
                        targetPolygon.reverse_orientation();
                }
        }

        if (targetPolygon.size() < 3 || !targetPolygon.is_simple()){
                return;
        }

        OutFiltrationPolygon.Empty();

        for (exactPolygon_2::Vertex_const_iterator it =
targetPolygon.vertices_begin(); it != targetPolygon.vertices_end(); it++)
        {
                double pointX = CGAL::to_double(it->x());
                double pointY = CGAL::to_double(it->y());
                OutFiltrationPolygon.AddUnique(FVector2D(pointX, pointY));
        }
}



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