c++代码实现:由一些x、y平面坐标点所组成的不规则图形,输出所有边框上的顶点坐标。
时间: 2024-05-02 12:17:30 浏览: 65
以下是一个基于C++的实现,使用vector容器存储坐标点并遍历求解:
```c++
#include <iostream>
#include <vector>
using namespace std;
struct Point {
int x;
int y;
};
vector<Point> getBoundaryPoints(vector<Point>& points) {
vector<Point> boundaryPoints;
int n = points.size();
// Find the leftmost point
int leftmostIndex = 0;
for (int i = 1; i < n; i++) {
if (points[i].x < points[leftmostIndex].x) {
leftmostIndex = i;
}
}
// Traverse the boundary clockwise
int currentIndex = leftmostIndex;
int nextIndex;
do {
boundaryPoints.push_back(points[currentIndex]);
nextIndex = (currentIndex + 1) % n;
for (int i = 0; i < n; i++) {
if (i != currentIndex && i != nextIndex &&
(points[i].x - points[currentIndex].x) * (points[nextIndex].y - points[currentIndex].y) -
(points[nextIndex].x - points[currentIndex].x) * (points[i].y - points[currentIndex].y) > 0) {
nextIndex = i;
}
}
currentIndex = nextIndex;
} while (currentIndex != leftmostIndex);
return boundaryPoints;
}
int main() {
vector<Point> points = {{0, 0}, {5, 0}, {5, 5}, {3, 3}, {2, 4}, {0, 5}};
vector<Point> boundaryPoints = getBoundaryPoints(points);
for (Point p : boundaryPoints) {
cout << "(" << p.x << ", " << p.y << ")" << endl;
}
return 0;
}
```
该算法基于计算凸包的思想,通过找到最左侧的点开始遍历,每次找到下一个点,直到回到最左侧的点为止。在搜索下一个点时,用叉积的方法判断候选点是否在当前点的顺时针方向上,如果是,则更新下一个点。
阅读全文