用于共线点的礼包装算法

Question

我根据Gift Wrapping算法的示例编写了以下代码来寻找一组点的凸包：

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中存在共线点时仍然能够正确工作？

- Stefan Dimitrov

Answer 1

如果有些点共线，则必须选择距离它们最远的点（即与当前点的距离最大的点）。

- MBo

---

最远的点并不一定会使得所有其他点都在新形成的直线左侧，从而导致错误。 - Stefan Dimitrov

最不共线的那些！ - MBo

这个规则是非常正确的。实际上你执行了一个词典序比较：首先基于角度（通过有符号面积），然后在遇到平局的情况下按距离排序。 - user1196549

那个规则是正确的，但它需要额外的注意。当有多个“最左边点”时，我认为你应该从其中最上面或最下面的一个开始。因为如果你从中间一个开始，你将回到顶部或底部，具体取决于你的循环条件，如果你正在检查是否已经到达第一个元素，那么你可能会做出不必要的迭代或陷入无限循环。我不确定这个实现是否受到影响，但由于几乎没有成本，所以我认为最好总是这样做。 - TheGrayed

Answer 2

你可以基于两点（围绕公共中心）之间的“排除”关系来推理，如果A和B的相对位置证明B不可能在凸包上，则A会排除B。

在图中，绿色点排除了蓝色点，而红色点则没有。在两个共线的点中，离中心最远的点会排除另一个点。排除轨迹是一个开放的半平面和半直线。

请注意，“excludes”是及物动词，定义了一个全序关系。

- user1196549

Answer 3

这比你演示的代码要棘手一些。我只关注谓词的稳定性，而不是如何处理共线点。谓词是你进行几何计算的地方 - pointPositionRelativeToLine。

你的代码设计得很好，因为你只在谓词中进行几何计算。这是使它强大的必须条件。然而，你的谓词不应该返回一个浮点数，而是从一个小集合中返回一个结果：要么是LEFT，要么是RIGHT，要么是COLLINEAR：

enum RelPos { LEFT, RIGHT, COLLINEAR };

RelPos pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C)
{
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
    if (result < 0.0) return LEFT;
    else if (result > 0.0) return RIGHT;
    return COLLINEAR;
}

你可以找出如何保证对于任意三个点，无论它们的排列方式如何，都能返回正确的答案。否则，你的算法就不能保证正常工作。

有两种一般的方法：

1. 使用适当的数据类型，在谓词中使用时保证精确结果。

2. 接受使用不精确数据类型时，有些输入无法计算出结果的事实。具体来说，你可以让谓词提供第四个值“INDETERMINATE”，并在这种情况下返回它。

第二种方法很容易实现，只需为所有输入的排列方式调用原始谓词即可：

enum RelPos { LEFT, RIGHT, COLLINEAR, INDETERMINATE };
typedef sf::Vector2f Point_2;

RelPos ppImpl(const Point_2 & A, const Point_2 & B, const Point_2 & C)
{
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
    if (result < 0.0) return LEFT;
    else if (result > 0.0) return RIGHT;
    return COLLINEAR;
}

bool inverse(RelPos a, RelPos b) {
  return a == LEFT && b == RIGHT || a == RIGHT && b == LEFT;
}

bool equal(RelPos a, RelPos b, RelPos c, RelPos d, RelPos e, RelPos f) {
  return a==b && b==c && c==d && d==e && e==f;
}

RelPos pointPositionRelativeToLine(const Point_2 & A, const Point_2 & B, const Point_2 & C) {
  auto abc = ppImpl(A, B, C);
  auto bac = ppImpl(B, A, C);
  auto acb = ppImpl(A, C, B);
  auto cab = ppImpl(C, A, B);
  auto bca = ppImpl(B, C, A);
  auto cba = ppImpl(C, B, A);
  if (abc == COLLINEAR) return equal(abc, bac, acb, cab, bca, cba) ?
    COLLINEAR : INDETERMINATE;
  if (!inverse(abc, bac) || !inverse(acb, cab) || !inverse(bca, cba))
    return INDETERMINATE;
  if (abc != bca || abc != cab)
    return INDETERMINATE;
  return abc;
}

上述逻辑可能存在错误，希望我理解正确。但这是一般的方法。至少对于给定的数据集，上述测试必须通过才能使算法在该数据集上工作。但我不记得那是否是充分条件。

当从谓词获得一个INDETERMINATE结果时，算法必须终止：

const auto errVal = std::vector<sf::Vector2f>();
...
auto rel = pointPositionRelativeToLine(returnValue.back(), *it, *it1);
if (rel == INDETERMINATE) return errVal;
if (rel == RIGHT) {
  allPointWereToTheLeft = false;
  break;
}

- Kuba hasn't forgotten Monica