c++geometrypolygoncgalconvex-polygon

Computing convex polygon segments using CGAL

I'm trying to compute convex segments of 2D polygons.

I have a polygon that looks like this when I plot it in matlab.

full Polygon

Coordinates:

225796.043479666,6614235.65748046
225810.567998704,6614196.64297454
225845.98597994,6614199.87498634
225890.17098232,6614182.52601038
225936.334851684,6614214.94566376
226007.697988493,6614296.73251355
226183.648576449,6614296.68302419
226183.705558557,6614063.80475619
225809.09078843,6614046.79681926
225809.057688672,6613796.65194834
225808.819271291,6613796.65197888
225808.820351664,6614046.78596429
225683.63987842,6614042.38155367
225683.649761896,6614296.67000115
225796.562029788,6614296.74302919

Here's the CGAL program I'm trying to use to perform convex segmentation:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/partition_2.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/property_map.h>
#include <vector>
#include <cassert>
#include <list>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Partition_traits_2<K, CGAL::Pointer_property_map<K::Point_2>::type > Partition_traits_2;
typedef Partition_traits_2::Point_2                         Point_2;
typedef Partition_traits_2::Polygon_2                       Polygon_2;  
typedef std::list<Polygon_2>                                Polygon_list;

int main( )
{
    std::vector<K::Point_2> points = 
    {
        K::Point_2(225796.043479666,6614235.65748046),
        K::Point_2(225810.567998704,6614196.64297454),
        K::Point_2(225845.98597994,6614199.87498634),
        K::Point_2(225890.17098232,6614182.52601038),
        K::Point_2(225936.334851684,6614214.94566376),
        K::Point_2(226007.697988493,6614296.73251355),
        K::Point_2(226183.648576449,6614296.68302419),
        K::Point_2(226183.705558557,6614063.80475619),
        K::Point_2(225809.09078843,6614046.79681926),
        K::Point_2(225809.057688672,6613796.65194834),
        K::Point_2(225808.819271291,6613796.65197888),
        K::Point_2(225808.820351664,6614046.78596429),
        K::Point_2(225683.63987842,6614042.38155367),
        K::Point_2(225683.649761896,6614296.67000115),
        K::Point_2(225796.562029788,6614296.74302919)
    };
    Partition_traits_2 traits(CGAL::make_property_map(points));
    Polygon_2 polygon;
    for (int i = 0; i < points.size(); i++)
    {
        polygon.push_back(i);    
    }
    Polygon_list partition_polys;

    CGAL::optimal_convex_partition_2
    (
        polygon.vertices_begin(),
        polygon.vertices_end(),
        std::back_inserter(partition_polys),
        traits
    );
    for (const Polygon_2& poly : partition_polys)
    {
        std::cout << "Polygon: " << std::endl;
        for(Point_2 p : poly.container())
        {
            std::cout << std::setprecision(15) << std::fixed << points[p] << std::endl;
        }
        std::cout << std::endl;
    }
    
    return 0;
}

So the output ended up looking like this

Polygon: 
226008 6.6143e+06
226184 6.6143e+06
226184 6.61406e+06
225809 6.61405e+06
225809 6.6138e+06
225809 6.6138e+06
225809 6.61405e+06
225684 6.61404e+06
225684 6.6143e+06
225797 6.6143e+06

Polygon:
225846 6.6142e+06
225890 6.61418e+06
225936 6.61421e+06
226008 6.6143e+06
225797 6.6143e+06

Polygon:
225796 6.61424e+06
225811 6.6142e+06
225846 6.6142e+06
225797 6.6143e+06

incorrect polygons

These polygons do not look like the optimal convex segments that I expected from the documentation's description.

It also looks like there are numerical issues as the point values are being rounded off far less precisely than I would have expected. I can understand some rounding but only 6 significant figures seems too inaccurate.

I was expecting to get a segmentation that looks something like:

expected

Is there anything I can do to fix this, or do I have to resort to writing my own algorithm?

EDIT

Thanks to @463035818_is_not_an_ai for the precision suggestion

precision fix

Now the polygons look less warped, but I am still not getting the segmentation I was expecting.

Solution

  • Input polygon must be counterclockwise oriented (compiling in debug you will get the assertion failing). Adding std::reverse(points.begin(), points.end()); I got the following as output: enter image description here