CGAL warning: check violation! The polygon has a wrong orientation.

[ChrisE2018]

Please use the following template to help us solving your issue.

Issue Details

At runtime I am getting a check violation, using code that is a slight modification of an example from the documentation.

This appears to be the same bug described in https://stackoverflow.com/questions/42009418/precondition-exception-when-intersecting-polygons-in-cgal

The CGAL installation was via: brew install cgal

I have make a number of CGAL examples work, including QT functions.

Source Code

See below

Environment

I am building using a custom MakeFile without using cmake. I know this is a hack but I am just trying to verify that my critical functions can be implemented before I spend time cleaning up the build process.

QT_FRAMEWORK_HEADERS := /usr/local/Cellar/qt/6.9.0/lib/QtWidgets.framework/Versions/A/Headers
QTGUI_HEADERS := /usr/local/Cellar/qt/6.9.0/lib/QtGui.framework/Versions/A/Headers
QT_3D_HEADERS := /usr/local/Cellar/qt/6.9.0/lib/Qt3DInput.framework/Versions/A/Headers
QT_CORE_HEADERS := /usr/local/Cellar/qt/6.9.0/lib/QtCore.framework/Versions/A/Headers
QT_OPENGL_HEADERS := /usr/local/Cellar/qt/6.9.0/lib/QtOpenGLWidgets.framework/Versions/A/Headers /usr/local/Cellar/qt/6.9.0/lib/QtOpenGL.framework/Versions/A/Headers
QT_INCLUDE_HEADERS := $(QT_FRAMEWORK_HEADERS) $(QTGUI_HEADERS) $(QT_3D_HEADERS) $(QT_CORE_HEADERS) $(QT_OPENGL_HEADERS)
MAPPER_INCLUDE_FLAGS := -I/usr/local/Cellar/cgal/6.0.1/CGAL-6.0.1/examples/Triangulation_2 $(addprefix -I,$(MAPPER_INCLUDE)) $(addprefix -I,$(QT_INCLUDE_HEADERS))


QTFLAGS :=  -lCGAL_Qt6_moc_and_resources /usr/local/lib/QtSvg.framework/Versions/A/QtSvg /usr/local/lib/QtOpenGLWidgets.framework/Versions/A/QtOpenGLWidgets /usr/local/lib/QtWidgets.framework/Versions/A/QtWidgets /usr/local/lib/QtOpenGL.framework/Versions/A/QtOpenGL /usr/local/lib/QtGui.framework/Versions/A/QtGui /usr/local/lib/QtCore.framework/Versions/A/QtCore

# Build the mapper target.
$(MAPPER_TARGET): $(MAPPER_OBJECTS)
	echo "Mapper target " $(MAPPER_TARGET) 
	echo "Mapper objects " $(MAPPER_OBJECTS)
	$(CXX) $(MAPPER_OBJECTS) $(ROBOT_OBJECTS) $(SIM_OBJECTS) -L/usr/local/Cellar/cgal/6.0.1/CGAL-6.0.1/examples -F/usr/local/lib $(QTFLAGS) /usr/local/lib/libgmpxx.dylib /usr/local/lib/libmpfr.dylib /usr/local/lib/libgmp.dylib -o $@ $(LDFLAGS)
	cp configuration.yaml $(MAPPER_BUILD_DIR)
endif

• Operating system (Windows/Mac/Linux, 32/64 bits): Mac OS Sequoia 15.4.1 (24E263) 64 bits (iMac 2019) 64 GB 2667 MHz DDR4 Radeon Pro Vega 48 8 GB
• Compiler:
• Release or debug mode: debug mode
• Specific flags used (if any):
• CGAL version: 6.0.1
• Boost version:
• Other libraries versions if used (Eigen, TBB, etc.):

Console Output

�[0m�[0K2025-05-12 18:43:28.482 INFO  [cgal_map@96] Q [0 0, 0 0.1, 0.1 0.1, 0 0.1]
�[0m�[0KCGAL warning: check violation!
Expression : valid_orientation
File       : /usr/local/include/CGAL/Boolean_set_operations_2/Gps_polygon_validation.h
Line       : 307
Explanation: The polygon has a wrong orientation.
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
CGAL error: precondition violation!
Expression : is_valid_unknown_polygon(p, t)
File       : /usr/local/include/CGAL/General_polygon_set_on_surface_2.h
Line       : 39
Explanation: 
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
libc++abi: terminating due to uncaught exception of type CGAL::Precondition_exception: CGAL ERROR: precondition violation!
Expr: is_valid_unknown_polygon(p, t)
File: /usr/local/include/CGAL/General_polygon_set_on_surface_2.h
Line: 39

Source Code

/*
 * main.cpp
 *
 *  Created on: May 10, 2025
 */

#define CGAL_USE_BASIC_VIEWER 1

#include "lidar/LidarPersistence.hpp"
#include "plog/Initializers/ConsoleInitializer.h"
#include "plog/Initializers/RollingFileInitializer.h"
#include "plog/Log.h"
#include <fstream>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_2.h>
#include <CGAL/draw_triangulation_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/draw_polygon_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Triangulation_2<K> Triangulation;
typedef Triangulation::Vertex_circulator Vertex_circulator;
typedef Triangulation::Point Point;
typedef K::Point_2 Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;

int cgal_demo ()
{
    std::ifstream in(
            "/usr/local/Cellar/cgal/6.0.1/CGAL-6.0.1/examples/Triangulation_2/data/triangulation_prog1.cin");
    std::istream_iterator<Point> begin(in);
    std::istream_iterator<Point> end;

    Triangulation t;
    t.insert(begin, end);
    LOG_INFO << "Triangulation data " << t;
    Vertex_circulator vc = t.incident_vertices(t.infinite_vertex());
    Vertex_circulator done(vc);
    if (vc != nullptr)
    {
        do
        {
            LOG_INFO << "==> " << vc->point();
        }
        while (++vc != done);
    }
    CGAL::draw(t);
    return 0;
}

void cgal_test_map ()
{
    LOG_INFO << "Creating simple Polygon";
    Point p0(-10, 30);
    Point p1(10, 30);
    Point p2(20, 15);
    Point p2b(-10, 15);
    Point p3(0, 0);
    Point p4(-20, 15);
    Polygon_2 p;
    p.push_back(p0);
    p.push_back(p1);
    p.push_back(p2);
    p.push_back(p2b);
    p.push_back(p3);
    p.push_back(p4);
    LOG_INFO << "Polygon_2 " << p;
    LOG_INFO << "done";
    CGAL::draw(p);
    LOG_INFO << "exit";
}

void cgal_map (robot::lidar::PointCloud cloud, std::map<const std::string, std::string> metadata)
{
    LOG_INFO << "Creating map from " << cloud << ", " << metadata;
    Polygon_2 t;
    std::vector<robot::lidar::SensorPoint> lidar_points(cloud.get_points());
//    std::reverse(lidar_points.begin(), lidar_points.end()); // Causes CGAL warning: check violation! Explanation: The polygon is not simple.
    for (robot::lidar::SensorPoint point : lidar_points)
    {
        Point p(point.get_x(), point.get_z());
        t.push_back(p);
//        LOG_INFO << "Point " << p;
    }
    //LOG_INFO << "Polygon " << t;
    CGAL::draw(t);
    LOG_INFO << "done";
    // Based on https://www.cs.tau.ac.il/~efif/doc_output10/Boolean_set_operations_2/Boolean_set_operations_2_2do_intersect_8cpp-example.html
    Polygon_2 q;
    q.push_back(Point_2(0, 0));
    q.push_back(Point_2(0, 0.1));
    q.push_back(Point_2 (0.1, 0.1));
    q.push_back(Point_2(0, 0.1));
    LOG_INFO << "Q " << q;
    if ((CGAL::do_intersect(t, q)))
        std::cout << "The two polygons intersect in their interior." << std::endl;
    else
        std::cout << "The two polygons do not intersect." << std::endl;
    CGAL::draw(q);
    LOG_INFO << "exit";
}

namespace mapper
{

#define LOG_ROOT "/Users/cre/Documents/Work/Projects/sbc/robots/countdown/logs"

#define TEST_DATA "/Users/cre/Documents/Work/Projects/sbc/robots/blue/logs/2025/04/28/20250428201843/lidar_scan_00001.lidar"

static std::string log_folder;

// For logging selection
enum
{
    // default is 0
    kConsole = 1,
    kFile
};

std::string get_log_pathname (const std::string &pathname)
{
    return log_folder + '/' + pathname;
}

void init_logging ()
{
    // [TODO] Put this into a configuration file.
    std::time_t time = std::time( {});
    const int buffer_size = 100;
    char buffer[buffer_size];
    std::strftime(buffer, buffer_size, LOG_ROOT "/%Y/%m/%d/%Y%m%d%H%M%S", std::gmtime(&time));
    log_folder = static_cast<std::string>(buffer);

    // Use a system call to make the folder.
    printf("Creating %s\n", log_folder.c_str());
    if (snprintf(buffer, sizeof(buffer), "mkdir -p %s", log_folder.c_str()) < buffer_size)
    {
        system(buffer);
    }

    // Create logger and file for primary trace messages.
    const std::string log_pathname = get_log_pathname(static_cast<std::string>("cadr.txt"));
    static plog::RollingFileAppender<plog::TxtFormatter> fileAppender(log_pathname.c_str(), // @suppress("Type cannot be resolved") // @suppress("Symbol is not resolved")
            100 * 1000, 10);
    plog::init<kFile>(plog::debug, &fileAppender); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")

    // Also send messages to the console.
    static plog::ColorConsoleAppender<plog::TxtFormatter> consoleAppender; // @suppress("Type cannot be resolved") // @suppress("Symbol is not resolved")
    plog::init<kConsole>(plog::info, &consoleAppender); // @suppress("Invalid arguments") // @suppress("Symbol is not resolved")
    plog::init(plog::debug, plog::get<kConsole>()).addAppender(plog::get<kFile>()); // @suppress("Invalid arguments") // @suppress("Method cannot be resolved")

    char buf[80];
    std::strftime(buf, sizeof(buf), "%m/%d/%Y %H:%M:%S", std::gmtime(&time));
    PLOGI << "Startup " << buf;
    PLOGI << "Data file " << log_pathname;
    PLOGI << "This will go to the file and to the console";
    PLOGD << "This will go to the file but not the console because of debug severity level";
}

extern "C" int main (int argc, char **argv)
{
    (void)argc;
    (void)argv;
    init_logging();
    robot::lidar::LidarPersistence loader;
    LOG_INFO << "Loader: " << loader;
    robot::lidar::PointCloud cloud("sample");
    std::map<const std::string, std::string> metadata;
    loader.load(static_cast<std::string>(TEST_DATA), cloud, metadata);
    LOG_INFO << "Point Cloud: " << cloud;
    LOG_INFO << "Point Cloud size: " << cloud.size();
    // Make a polygon using CGAL.
    // Convert polygon to drivable area.
//    cgal_demo();
//    cgal_test_map();
    cgal_map(cloud, metadata);
    return 0;
}
}

[ChenKe404]

polygon must be counterclockwise oriented, if your polygon might not counterclockwise , you should call "is_clockwise_oriented" or "is_counterclockwise_oriented" to check orientation, if it's clockwise oriented , then call "reverse_orientation" to switch orientation to counterclockwise.

[ChenKe404]

if your polygon has holes, then the outer must be counterclockwise oriented and the holes must be clockwise oriented.