CGAL约束Delaunay三角剖分中相交约束的处理问题

我使用CGAL的Constrained Delaunay Triangulation对OpenCV contourFinder自动生成的折线进行三角剖分，但当形状稍复杂时，CGAL会抛出Intersection_of_constraints_exception()，导致程序终止。

为避免该问题，我在将折线传入CGAL前实现了相交检查，确保不添加相交线段，但仍遇到相同异常。

我的处理方案 #

• 使用OpenCV的cv::approxPolyDP()简化轮廓；
• 遍历简化后的点，检查添加新线段是否与现有线段相交；
• 若无相交则将线段加入折线；
• 将过滤后的折线传入CGAL进行三角剖分。

即便加入该过滤步骤，CGAL仍检测到相交并抛出异常。

疑问 #

1. 是否有更好的预处理或处理相交约束的方法可用于CGAL？
2. 我的相交检查是否存在缺陷，或是CGAL有额外要求？
3. CGAL是否有可自动处理或移除相交约束的函数？

核心代码 #

//find contour
contourFinder.findContours(grayscaleImage, *minimumArea, *maximumArea, *considered, false, true);

//find outlines
polylines.clear();
meshes.clear();

for (int i = 0; i < contourFinder.nBlobs; i++) {

    ofPolyline polyline;
    polyline.clear();

    vector<cv::Point> contour;
    for (const auto& p : contourFinder.blobs.at(i).pts) {
        contour.push_back(cv::Point(p.x, p.y));
    }

    if (contour.size() > 0) {

        //reduce points
        vector<cv::Point> approx;
        cv::approxPolyDP(contour, approx, *polygonApproximation, true);
            
        //store end coordinate to check first segment
        cv::Point previousPoint = approx.at(approx.size() - 1);

        //go through all segments, add only if not causing an intersection
        for (int i = 0; i < approx.size(); i++) {

            bool wouldIntersect = false;

            for (int j = 0; j < polyline.size(); j++) {
                if (
                    doIntersect(
                        ofPoint(
                            previousPoint.x,
                            previousPoint.y
                        ),
                        ofPoint(
                            approx.at(i).x,
                            approx.at(i).y
                        ),
                        ofPoint(
                            polyline.getVertices().at((j + 1) % polyline.getVertices().size()).x,
                            polyline.getVertices().at((j + 1) % polyline.getVertices().size()).y
                        ),
                        ofPoint(
                            polyline.getVertices().at(j).x,
                            polyline.getVertices().at(j).y
                        )
                    )
                ) {
                    wouldIntersect = true;
                }
            }

            if (wouldIntersect == false) {
                cout << "ok: " << i << endl;
                polyline.addVertex(approx.at(i).x, approx.at(i).y);
                previousPoint = approx.at(i);
            }
            else {
                cout << "intersecting: " << i << endl;
            }

        }

        polyline.close();
        polylines.push_back(polyline);

    }

}
    
for (int i = 0; i < polylines.size(); i++) {
    meshes.push_back(
        cgal.triangulate(polylines.at(i), *maximumEdgeLength)
    );
}

辅助函数 #

// Helper function to check the orientation of the triplet (p, q, r)
int ofApp::orientation(const ofPoint& p, const ofPoint& q, const ofPoint& r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    
    //if (val == 0) return 0;  // collinear
    const double EPSILON = 1e-9;
    if (std::abs(val) < EPSILON) return 0;

    return (val > 0) ? 1 : 2; // clockwise or counterclockwise
}

// Helper function to check if point q lies on the line segment pr
bool ofApp::onSegment(const ofPoint& p, const ofPoint& q, const ofPoint& r) {
    return (q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
        q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y));
}

// Function to check if two line segments p1p2 and p3p4 intersect
bool ofApp::doIntersect(const ofPoint& p1, const ofPoint& p2, const ofPoint& p3, const ofPoint& p4) {

    int o1 = orientation(p1, p2, p3);
    int o2 = orientation(p1, p2, p4);
    int o3 = orientation(p3, p4, p1);
    int o4 = orientation(p3, p4, p2);

    // General case: segments intersect
    if (o1 != o2 && o3 != o4) {
        return true;
    }

    // Special cases: check if the points are collinear and on the segment
    if (o1 == 0 && onSegment(p1, p3, p2)) return true;
    if (o2 == 0 && onSegment(p1, p4, p2)) return true;
    if (o3 == 0 && onSegment(p3, p1, p4)) return true;
    if (o4 == 0 && onSegment(p3, p2, p4)) return true;

    // If none of the above conditions are true, the lines do not intersect
    return false;
}

恳请各位提供关于我的方案是否存在缺陷，或更优预处理方法的见解。谢谢！

内容的提问来源于stack exchange，提问作者Harry Vermeulen