CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.97k stars 1.39k forks source link

optimal_convex_partition_2 does not always return an optimal partition #4398

Open lcrombez opened 4 years ago

lcrombez commented 4 years ago

Issue Details

In some "simple" cases (No three points are aligned) optimal_convex_partition_2 does not return the optimal convex partition.

The source code below shows a 10 points polygon that can be partitioned in 3 convex polygons. optimal_convex_partition_2 returns 4 polygons. The second part of the code shows the same 10 points polygon but the first points listed is changed. This time optimal_convex_partition_2 returns the correct answer, which is a partition of 3 convex polygons.

Source Code

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>

using namespace std;

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K>                         Traits;
typedef Traits::Polygon_2                                   Polygon_2;
typedef Traits::Point_2                                     Point_2;
typedef std::list<Polygon_2>                                Polygon_list;
typedef Polygon_2::Vertex_iterator                          VertexIterator;

int main()
{
    Polygon_2             polygon;
    Polygon_list          partition_polys;

    polygon.push_back(Point_2(3,4));
    polygon.push_back(Point_2(1,5));
    polygon.push_back(Point_2(0,4));
    polygon.push_back(Point_2(2,2));
    polygon.push_back(Point_2(5,0));
    polygon.push_back(Point_2(4,3));
    polygon.push_back(Point_2(6,0));
    polygon.push_back(Point_2(6,6));
    polygon.push_back(Point_2(5,7));
    polygon.push_back(Point_2(4,5));
    CGAL::optimal_convex_partition_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     std::back_inserter(partition_polys));

    cout << partition_polys.size() << endl;
    for (Polygon_2 &pol: partition_polys) {
        for (VertexIterator vi = pol.vertices_begin();
             vi != pol.vertices_end(); ++vi)
        {
            cout << "(" << vi->x() << " " << vi->y() << ") ";
        }
        cout << endl;
    }

    Polygon_2       polygon2;
    Polygon_list    partition_polys2;
    //This is exactly the same polygon, the first points has just been moved
    //to the last position
    polygon2.push_back(Point_2(1,5));
    polygon2.push_back(Point_2(0,4));
    polygon2.push_back(Point_2(2,2));
    polygon2.push_back(Point_2(5,0));
    polygon2.push_back(Point_2(4,3));
    polygon2.push_back(Point_2(6,0));
    polygon2.push_back(Point_2(6,6));
    polygon2.push_back(Point_2(5,7));
    polygon2.push_back(Point_2(4,5));
    polygon2.push_back(Point_2(3,4));

    CGAL::optimal_convex_partition_2(polygon2.vertices_begin(),
                                     polygon2.vertices_end(),
                                     std::back_inserter(partition_polys2));

    cout << partition_polys2.size() << endl;
    for (Polygon_2 &pol: partition_polys2) {
        for (VertexIterator vi = pol.vertices_begin();
             vi != pol.vertices_end(); ++vi)
        {
            cout << "(" << vi->x() << " " << vi->y() << ") ";
        }
        cout << endl;
    }
}

Environment

My rough understanding of the origin of the issue

Note: I do not have access to Greene's paper which describes the algorithm implemented, so my understanding of the algorithm is at least partially flawed.

The starting edge (9 0) sees three points: 3,5 and 7 (which are not consecutive in the input polygon) The optimal partition uses the edges (0 3) and (3 9). Which the algorithm correctly sees both as only "requiring 1 convex polygon to partition the section of the input polygon that lies right to those edges". It looks like to me that the issue comes eeither from partition_opt_cvx_load and/or partition_opt_cvx_best_so_far (However, the intended behavior of this part of the algorithm is still blurry to me). I think that the fact that the optimal solution requires the polygon aounrd (9 0) not to use one of the extremum of the seen points from the edge (9 0) (so not using neither 3 nor 7 in this case) induces the bug.

lcrombez commented 4 years ago

I think I found the issue. partition_opt_cvx_best_so_far detroys the stack of pivot_vertex. I'm pretty sure that the stack should be preserved for future calls from partition_opt_cvx_load

I tried the lazy and dirty fix consisting of saving and the stack and restoring it after the call to partition_opt_cvx_best_so_far in partition_opt_cvx_load and I do get the correct result by doing that. I think it's safe to assume that partition_opt_cvx_best_so_far is supposed to iterate through the stack instead of poping it.