清华计算几何-ConvexHull(凸包)-求极点InTriangle/ToLeft Test-CSDN博客
上篇博客描述了一种从点集合暴力求解极点的算法,复杂度为O(n4), 耗费相当高. 下面介绍一种优于暴力求极点的算法
和极点概念类似, 如果点集合中,存在两个点连成一条线, 其他点都在这条边的同一侧,则这条线为极边(extremity edge), 这两个点为极点。
遍历所有的边, 判断其他点是否都在这条边的同一侧。
算法复杂度: O(n3), n2用于遍历所有边,n用于遍历所有点
- #include
- #include
-
- using namespace std;
-
- struct Point
- {
- float x;
- float y;
- bool extreme;
- };
-
- 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;
- }
-
-
- void CheckExtrmtiEdge(vector
& inPoints, int idxA, int idxB) - {
- bool bLeftEmpty = true;
- bool bRightEmpty = true;
- int pointNum = inPoints.size();
-
- for (int idx = 0; idx < pointNum; idx++)
- {
- if (idx != idxA && idx != idxB)
- {
-
- if (IsLeftTest(inPoints[idx], inPoints[idxA], inPoints[idxB]))
- {
- bLeftEmpty = false;
- }
- else
- {
- bRightEmpty = false;
- }
-
- if (!bLeftEmpty && !bRightEmpty)
- break;
- }
- }
-
- if (bLeftEmpty || bRightEmpty)
- {
- inPoints[idxA].extreme = true;
- inPoints[idxB].extreme = true;
- }
- }
-
-
- void GetEpFromExtrmtiEdge(vector
& inPoints) - {
- int pointNum = inPoints.size();
- for (auto& point : inPoints)
- {
- point.extreme = false;
- }
-
- for (int idxA = 0; idxA < pointNum; idxA++)
- {
- for (int idxB = idxA + 1; idxB < pointNum; idxB++)
- {
- CheckExtrmtiEdge(inPoints, idxA, idxB);
- }
- }
-
-
- }
-
-
- int main()
- {
- std::cout << "Hello World!\n";
-
- // point set contruct
- vector
inPoints = - {
- {0, 0},
- {-1, -1},
- {5, 2},
- {4, 5},
- {3, 3},
- {-1, 3},
- {2, 2},
- {-3, 2},
- };
-
-
- GetEpFromExtrmtiEdge(inPoints);
-
- for (int index = 0; index < inPoints.size(); index++)
- {
- if (inPoints[index].extreme)
- {
- printf("(%f, %f)\n", inPoints[index].x, inPoints[index].y);
- }
- }
-
- }
对于和上节同样的数据集,得出的结果一致
[1]清华计算几何 P13-P15