資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝設計
法學資料結構中的凸包示例
這裡我們將看到有關凸包的一個示例。假設我們有一組點。我們必須用更少的點繪製一個多邊形，以覆蓋給定的所有點。本節中，我們將看到 Jarvis 行進演算法以獲得凸包。
Jarvis 行進演算法用於從給定資料點集中檢測凸包的拐點。
從資料集的最左點開始，我們透過逆時針旋轉來保留凸包中的點。從當前點開始，我們可以透過檢查這些點從當前點出發的方向來選擇下一個點。當角度最大時，選擇該點。完成所有點後，當下一個點為起點時，停止演算法。
輸入 − 點集：{(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
輸出 − 凸包的邊界點為 −
(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)
演算法
findConvexHull(points, n) Input: The points, number of points. Output: Corner points of convex hull. Begin start := points[0] for each point i, do if points[i].x < start.x, then // get the left most point start := points[i] done current := start add start point to the result set. define colPts set to store collinear points while true, do //start an infinite loop next := points[i] for all points i except 0th point, do if points[i] = current, then skip the next part, go for next iteration val := cross product of current, next, points[i] if val > 0, then next := points[i] clear the colPts array else if cal = 0, then if next is closer to current than points[i], then add next in the colPts next := points[i] else add points[i] in the colPts done add all items in the colPts into the result if next = start, then break the loop insert next into the result current := next done return result End
示例
#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point{ //define points for 2d plane
int x, y;
bool operator==(point p2){
if(x == p2.x && y == p2.y)
return 1;
return 0;
}
bool operator<(const point &p2)const{ //dummy compare function used to sort in set
return true;
}
};
int crossProduct(point a, point b, point c){ //finds the place of c from ab vector
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
return y2*x1 - y1*x2; //if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are collinear
}
int distance(point a, point b, point c){
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
int item1 = (y1*y1 + x1*x1);
int item2 = (y2*y2 + x2*x2);
if(item1 == item2)
return 0; //when b and c are in same distance from a
else if(item1 < item2)
return -1; //when b is closer to a
return 1; //when c is closer to a
}
set<point> findConvexHull(point points[], int n){
point start = points[0];
for(int i = 1; i<n; i++){ //find the left most point for starting
if(points[i].x < start.x)
start = points[i];
}
point current = start;
set<point> result; //set is used to avoid entry of duplicate points
result.insert(start);
vector<point> *collinearPoints = new vector<point>;
while(true){
point nextTarget = points[0];
for(int i = 1; i<n; i++){
if(points[i] == current) //when selected point is current point, ignore rest part
continue;
int val = crossProduct(current, nextTarget, points[i]);
if(val > 0){ //when ith point is on the left side
nextTarget = points[i];
collinearPoints = new vector<point>; //reset collinear points
}else if(val == 0){ //if three points are collinear
if(distance(current, nextTarget, points[i]) < 0){ //add closer one to collinear list
collinearPoints->push_back(nextTarget);
nextTarget = points[i];
}else{
collinearPoints->push_back(points[i]); //when ith point is closer or same as nextTarget
}
}
}
vector<point>::iterator it;
for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){
result.insert(*it); //add allpoints in collinear points to result set
}
if(nextTarget == start) //when next point is start it means, the area covered
break;
result.insert(nextTarget);
current = nextTarget;
}
return result;
}
int main(){
point points[] = {
{-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},
{3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};
int n = 18;
set<point> result;
result = findConvexHull(points, n);
cout << "Boundary points of convex hull are: "<<endl;
set<point>::iterator it;
for(it = result.begin(); it!=result.end(); it++)
cout << "(" << it->x << ", " <<it->y <<") ";
}輸出
Boundary points of convex hull are: (-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)
更新日期：2019 年 8 月 27 日
2K+ 瀏覽次數
廣告