测试多边形是否非常简单

Question

我无法想出一种算法来检测弱的简单多边形(即允许边接触但不能交叉的多边形).目前我只是检查每一方之间的交叉点 - 这是我呼吁所有非相邻方的功能.这样,只允许简单的多边形(根本不接触).多边形是点的向量.

bool linesIntersect(const point &a1, const point &a2, const point &b1, const point &b2) {
    // Solve intersection of parametric lines using inverse matrix
    // The equation of the parametric lines are line1 = (a2 - a1)*s + a1
    // and line2 = (b2 - b1)*t + b1, where a1, a2, etc. are vectors.
    // Two equations can be produced from the two components, and these
    // this system of two equations can be solved for s and t
    // If the parameters s and t are between 0 and 1, it means that the lines intersect
    float x21 = a2.x - a1.x, x43 = b2.x - b1.x, x31 = b1.x - a1.x,
        y21 = a2.y - a1.y, y43 = b2.y - b1.y, y31 = b1.y - a1.y;
    float determinant = x43*y21 - x21*y43;
    if(determinant == 0.) return false;

    float s = float(x43*y31 - x31*y43)/determinant;
    float t = float(x21*y31 - x31*y21)/determinant; 

    if(s <= 1. && s >= 0. && t <= 1. && t >= 0.) return true; // lines intersect
    return false;
}

使用s < 1. && s > 0. && t < 1. && t > 0.不起作用,因为它接受一些复杂的多边形很简单.

这个问题的第一个数字显示了几个例子.下面是程序将要处理的典型的弱简单多边形.

我更喜欢伪代码,因为前面提到的问题(1)中的数学术语让我感到害怕,我认为我不具备实现任何复杂算法的知识.我正在使用Boost.Polygon作为其他东西,如果那里有东西,但我没有找到任何东西.

编辑:

这是我如何使用该功能.checkPts是vector<point>从最后一个点到第一个点的假定边.

// Check for self-intersecting polygons
for(int i = 0; i < checkPts.size() - 2; ++i) {
    for(int j = i + 2; j < checkPts.size() - 2; ++j) {
        if(linesIntersect(checkPts[i], checkPts[i+1], checkPts[j], checkPts[j+1])) error("self-intersecting polygon");
    }
}

Answer 1

我不确定我明白了，因为你似乎已经有了解决方案。只需调用lineIntersects每对不相邻的边即可。

如果两条边没有公共点，则lineIntersects返回 false，这是预期的。

如果两条边相互交叉，lineIntersects则返回 true，因此您知道该多边形不是弱简单的。

如果两条边接触（如图所示），则您在linesIntersects 中计算的行列式为0（即：线是平行的）。lineIntersects返回假。这就是你想要的（你允许边缘接触）

当然，总是存在棘手的部分，即浮点运算会导致舍入错误，但对我来说，函数中的数学是正确的。（并且绝对应该适用于图片中的示例）

编辑：一种更“数学”的方法。两条边要么有 0 个公共点，要么有 1 个公共点，要么有无数个公共点（它们“接触”）。弱简单意味着对于任意两对边，不允许出现“1 个公共点”的情况。因此，您需要一个函数来找出你们何时恰好有 1 个共同点。我的主张是lineIntersects已经做到了

编辑 2：我忘了解释一下，有 1 个共同点并不总是一个问题。但前提是两条边之间的公共点位于两条边之一的端点处。那么我们应该“允许”它（返回 false）。但这并没有改变我的答案，因为在 中lineIntersects，我们计算s < 1. && s > 0. && t < 1. && t > 0.而不是s <= 1. && s >= 0. && t <= 1. && t >= 0.。所以我们已经“允许”这种情况了。