資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究凸包賈維斯演算法或用 C++ 包裝
在本教程中，我們將討論一個使用賈維斯演算法找到一組給定點的凸包的程式。
凸包是最小的多邊形凸形，包含邊界或圖形內部的所有給定點。
在賈維斯演算法中，我們選擇最左邊的點，並保持包裝點的順時針移動。
範例
#include <bits/stdc++.h>
using namespace std;
//structure of the point
struct Point{
int x, y;
};
//calculating the position of the points
int cal_orientation(Point p, Point q, Point r){
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; //collinear
return (val > 0)? 1: 2; //clock or counterclockwise
}
//printing convex hull
void convexHull(Point points[], int n){
if (n < 3) return;
vector<Point> hull;
//calculating the leftmost point
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
//moving in the clockwise direction
int p = l, q;
do{
//adding current point to result
hull.push_back(points[p]);
q = (p+1)%n;
for (int i = 0; i < n; i++){
if (cal_orientation(points[p], points[i], points[q]) == 2)
q = i;
}
p = q;
} while (p != l); //if didn't reached the first point
for (int i = 0; i < hull.size(); i++)
cout << "(" << hull[i].x << ", "
<< hull[i].y << ")\n";
}
int main(){
Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
{3, 0}, {0, 0}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
}輸出
(0, 3) (0, 0) (3, 0) (3, 3)
更新於：2020 年 1 月 29 日
557 次瀏覽
廣告