資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究查詢 C++ 中給定點集的簡單封閉路徑
考慮我們有一組點。我們必須找到一個包含所有點的簡單封閉路徑。假設這些點如下，那麼下一張圖片是在這些點上形成的封閉路徑。
要獲取路徑，我們必須執行以下步驟 -
找到左下方的點作為 P
根據圍繞 P 的極角逆時針對其他 n - 1 點進行排序，如果兩個點的極角相同，則將它們作為最短距離
遍歷排序後的點列表，然後建立路徑
例項
#include <bits/stdc++.h>
using namespace std;
class Point {
public:
int x, y;
};
Point p0;
int euclid_dist(Point p1, Point p2) {
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
int orientation(Point p1, Point p2, Point p3) {
int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clockwise or counterclock wise
}
int compare(const void *vp1, const void *vp2) {
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (euclid_dist(p0, *p2) >= euclid_dist(p0, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
void findClosedPath(Point points[], int n) {
int y_min = points[0].y, min = 0;
for (int i = 1; i < n; i++) {
int y = points[i].y;
if ((y < y_min) || (y_min == y && points[i].x < points[min].x))
y_min = points[i].y, min = i;
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[1], n-1, sizeof(Point), compare); //sort on polar angle
for (int i=0; i<n; i++)
cout << "(" << points[i].x << ", "<< points[i].y <<"), ";
}
int main() {
Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},{0, 0}, {1, 2}, {3, 1}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
findClosedPath(points, n);
}產出
(0, 0), (3, 1), (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (0, 3),
更新於： 22-10-2019
280 次瀏覽
廣告