清华计算几何-ConvexHull(凸包)-极点InTriangle/ToLeft Test
ConvexHull(凸包)的基本概念
给定一个点集, 求出最外围的点所形成的几何, 就是凸包。如下所示
凸包在计算几何是一个非常基础和核心的一个概念, 很多几何计算算法都围绕凸包展开。
极点和非极点
如上图所示, 蓝图圈圈住的点都是极端点, 极端点具备一个重要的特性:
极点(extremity point): 存在一条经过此点的线L, 把其他所有点列在线L的同一端。
非极点：与极点相反, 不具备这样的线L.
凸组合(Convex Combination)
也就是说给定一个点集合S，数量为N, 每个点都存在一个权重R(x)，
当保证 每个R >= 0 并且 R1 + R2... Rn = 1.0
由计算公式: P = Point1 * R1 + Point2 * R2 + ... PointN * Rn
求出的点集合为S的凸组合.
凸相关
某个点加入后，S集合依然不变，则该点和S凸组合是凸相关的，也就是该点原本就在S组合里。
对于1和4构成的S集合, 2和3是凸相关。
凸无关
某个点加入后，S集合发生改变, 则该点和S凸组合是凸无关的。也就是该点原本不在S组合里。
点4的加入使用"1-2-3" S凸组合的范围变大了，因为点4和"1-2-3"凸组合是凸无关的。
ConvexHull(凸包)的求解
流程分解
总结：遍历所有三角形，判断每个点是否在任意一个三角形内。用In-Trignle|InLeft|Determinant叉积。算法复杂度：O(n4)
伪代码全流程
InTrianle测试
ToLeft测试
这里2*S的[1, 1, 1]理解为三维空间中，三个点为同一Z平面。叉积就是带正负的面积。
代码实现求凸包-极点集合(2D)
InTrianleTest + ToLeftTest
给定一个点的集合求所有极点
#include <iostream>
#include <vector>
using namespace std;
struct Point
{
float x;
float y;
};
float Area2(const Point& inPointA, const Point& inPointB, const Point& inPointC)
{
float value =
inPointA.x * inPointB.y - inPointA.y * inPointB.x
+ inPointB.x * inPointC.y - inPointB.y * inPointC.x
+ inPointC.x * inPointA.y - inPointC.y * inPointA.x;
return value;
}
bool IsLeftTest(const Point& inPointA, const Point& inPointB, const Point& inPointC)
{
return Area2(inPointA, inPointB, inPointC) > 0;
}
bool IsInTrianle(const Point& inPoint, const Point& triangleA, const Point& triangleB, const Point& triangleC)
{
bool bLeftA = IsLeftTest(triangleA, triangleB, inPoint);
bool bLeftB = IsLeftTest(triangleB, triangleC, inPoint);
bool bLeftC = IsLeftTest(triangleC, triangleA, inPoint);
// 取决于CCW/CW
return (bLeftA == bLeftB) && (bLeftB == bLeftC);
}
void GetConvexPointSet(const vector<Point>& inPoints, vector<Point>& outPoints)
{
int pointNum = inPoints.size();
vector<bool> extrmeFlags;
extrmeFlags.resize(pointNum);
for (int index = 0; index < pointNum; index++)
{
extrmeFlags[index] = true;
}
// O(n4)
for (int idxA = 0; idxA < pointNum; idxA++)
{
for (int idxB = idxA + 1; idxB < pointNum; idxB++)
{
for (int idxC = idxB + 1; idxC < pointNum; idxC++)
{
for (int s = 0; s < pointNum; s++)
{
if (s == idxA || s == idxB || s == idxC || !extrmeFlags[s])
continue;
if (IsInTrianle(inPoints[s], inPoints[idxA], inPoints[idxB], inPoints[idxC]))
{
extrmeFlags[s] = false;
}
}
}
}
}
for (int index = 0; index < pointNum; index++)
{
if (extrmeFlags[index])
{
outPoints.push_back(inPoints[index]);
}
}
}
int main()
{
std::cout << "Hello World!\n";
// point set contruct
vector<Point> inPoints =
{
{0, 0},
{-1, -1},
{5, 2},
{4, 5},
{3, 3},
{-1, 3},
{2, 2},
{-3, 2},
};
vector<Point> outPoints;
GetConvexPointSet(inPoints, outPoints);
for (int index = 0; index < outPoints.size(); index++)
{
printf("(%f, %f)\n", outPoints[index].x, outPoints[index].y);
}
}测试结果
很显然，求的凸包存在问题，遗漏了(-1, -1)
按照InTriangle-ToLeft测试，(-1, -1)(0,0)(2, 2)(3, 3)四个点刚好是位于一条线上，(-1, -1) In-Triangle三次ToLeft都是相同结果，(-1, -1)被认定在三角形[(0,0)(2, 2)(3, 3)]内.
所以得改进In-Triangle测试，判断四点共线的情况。
改进InTrianleTest，消除四点共线
bool IsInTrianle(const Point& inPoint, const Point& triangleA, const Point& triangleB, const Point& triangleC)
{
float a_area2 = Area2(triangleA, triangleB, inPoint);
float b_area2 = Area2(triangleB, triangleC, inPoint);
float c_area2 = Area2(triangleC, triangleA, inPoint);
if (a_area2 == 0 && b_area2 == 0 && c_area2 == 0)
return false;
bool bLeftA = a_area2 > 0;
bool bLeftB = b_area2 > 0;
bool bLeftC = c_area2 > 0;
// 取决于CCW/CW
return (bLeftA == bLeftB) && (bLeftB == bLeftC);
}测试结果
资料参考
原文地址：https://blog.csdn.net/qq_29523119/article/details/140310455
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！