c++ - 具有共线点的礼品包装算法

因此，我根据用于查找一组点的凸包的礼品包装算法示例编写了以下代码:

std::vector<sf::Vector2f> convexHull(const std::vector<sf::Vector2f>& _shape)
{
    std::vector<sf::Vector2f> returnValue;
    returnValue.push_back(leftmostPoint(_shape));
    for (std::vector<sf::Vector2f>::const_iterator it = _shape.begin(), end = _shape.end(); it != end; ++it)
    {
        if (elementIncludedInVector(*it, returnValue)) continue;
        bool allPointWereToTheLeft = true;
        for (std::vector<sf::Vector2f>::const_iterator it1 = _shape.begin(); it1 != end; ++it1)
        {
            if (*it1 == *it || elementIncludedInVector(*it1, returnValue)) continue;
            if (pointPositionRelativeToLine(returnValue.back(), *it, *it1) > 0.0f)
            {
                allPointWereToTheLeft = false;
                break;
            }
        }
        if (allPointWereToTheLeft)
        {
            returnValue.push_back(*it);
            it = _shape.begin();
        }
    }
    return returnValue;
}

这是我用于确定第三个点位于线的哪一侧的函数:

float pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

返回负数表示该点在一侧，另一侧为正数，0 表示三点共线。
现在，问题是:即使 _shape 中有共线点，如何修改上述代码才能正常工作？

最佳答案

如果某些点共线，则必须选择离它们最远的点(与当前点的最大距离)

关于c++ - 具有共线点的礼品包装算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32317077/