具有共线点的礼品包装算法
Gift Wrapping Algorithm with Collinear Points
所以我根据礼品包装算法的例子编写了以下代码,用于查找一组点的凸包:
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 中存在共线点时也能正常工作?
如果某些点共线,则必须选择离它们最远的点(到当前点的距离最大)
这比您演示的代码更难正确执行。我只会关注你的谓词的稳定性,而不是你如何处理共线点。谓词是您进行几何计算的地方 - pointPositionRelativeToLine
.
您的代码设计得很好,因为您只在谓词中进行几何计算。这是使其坚固的必要条件。 las,您的谓词不应该 return 一个浮点数,而是一个小集合的结果: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;
}
然后您可以弄清楚如何保证给定任何三个点,正确答案是 return 对它们的任何排列。这是必须的,否则你的算法不能保证有效。
有两种通用方法:
使用正确的数据类型以保证在谓词中使用时得到准确的结果。
接受您使用的不精确的数据类型,有些输入无法计算结果。具体来说,您可以让谓词提供第四个值,INDETERMINATE
,在这种情况下 return。
通过为输入的所有排列调用原始谓词,第二种方法很容易实现:
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;
}
你可以根据两点之间的"exclude"关系(围绕一个公共中心)进行推理,意思是如果A和B的相对位置证明B不能在凸包。
在图中,绿点排除了蓝点,而红点则没有。在两个对齐的点中,离中心最远的点排除另一个。排除轨迹是一个开放的半平面和半直线。
请注意 "excludes" 是可传递的并且定义了总排序。
所以我根据礼品包装算法的例子编写了以下代码,用于查找一组点的凸包:
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 中存在共线点时也能正常工作?
如果某些点共线,则必须选择离它们最远的点(到当前点的距离最大)
这比您演示的代码更难正确执行。我只会关注你的谓词的稳定性,而不是你如何处理共线点。谓词是您进行几何计算的地方 - pointPositionRelativeToLine
.
您的代码设计得很好,因为您只在谓词中进行几何计算。这是使其坚固的必要条件。 las,您的谓词不应该 return 一个浮点数,而是一个小集合的结果: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;
}
然后您可以弄清楚如何保证给定任何三个点,正确答案是 return 对它们的任何排列。这是必须的,否则你的算法不能保证有效。
有两种通用方法:
使用正确的数据类型以保证在谓词中使用时得到准确的结果。
接受您使用的不精确的数据类型,有些输入无法计算结果。具体来说,您可以让谓词提供第四个值,
INDETERMINATE
,在这种情况下 return。
通过为输入的所有排列调用原始谓词,第二种方法很容易实现:
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;
}
你可以根据两点之间的"exclude"关系(围绕一个公共中心)进行推理,意思是如果A和B的相对位置证明B不能在凸包。
在图中,绿点排除了蓝点,而红点则没有。在两个对齐的点中,离中心最远的点排除另一个。排除轨迹是一个开放的半平面和半直线。
请注意 "excludes" 是可传递的并且定义了总排序。