Гүдгэр бүрхүүл байгуулах¶
Энэ өгүүлэлд бид цэгүүдийн олонлогоос гүдгэр бүрхүүл байгуулах бодлогыг хэлэлцэнэ.
Хавтгай дээр $N$ цэг өгөгдсөн байг, зорилго нь гүдгэр бүрхүүл буюу өгөгдсөн бүх цэгийг агуулах хамгийн бага гүдгэр олон өнцөгтийг үүсгэх явдал юм.
Бид 1972 онд Graham-ийн нийтэлсэн Грахамын шүүрдэлт алгоритм, мөн 1979 онд Andrew-ийн нийтэлсэн Монотон гинж алгоритмыг үзнэ. Хоёул $\mathcal{O}(N \log N)$ бөгөөд асимптотоор оновчтой (учир нь асимптотоор илүү сайн алгоритм байхгүй нь батлагдсан), зөвхөн параллель эсвэл онлайн боловсруулалт хийгддэг цөөн хэдэн бодлогыг эс тооцвол.
Грахамын шүүрдэлт алгоритм¶
Алгоритм эхлээд хамгийн доод $P_0$ цэгийг олно. Хэрэв ижил Y координаттай хэд хэдэн цэг байвал X координат нь бага байгааг нь авч үзнэ. Энэ алхам $\mathcal{O}(N)$ хугацаа авна.
Дараа нь бусад бүх цэгийг туйлын өнцгөөр цагийн зүүний дагуу эрэмбэлнэ. Хэрэв хоёр буюу түүнээс дээш цэгийн туйлын өнцөг ижил бол тэнцээг $P_0$-ээс хэмжсэн зайгаар өсөх дарааллаар шийднэ.
Дараа нь бид цэг бүрийг нэг нэгээр нь тойрч, одоогийн цэг ба түүний өмнөх хоёр цэг цагийн зүүний дагуу эргэлт үүсгэж байгааг шалгана, эс бөгөөс өмнөх цэгийг хаяна, учир нь энэ нь гүдгэр биш дүрс үүсгэнэ. Цагийн зүүний дагуу эсвэл эсрэг эсэхийг чиглэлийг шалгах замаар шалгаж болно.
Бид цэгүүдийг хадгалахад стек ашиглах ба анхны $P_0$ цэгт хүрмэгц алгоритм дуусах ба бид гүдгэр бүрхүүлийн бүх цэгийг цагийн зүүний дагуу агуулсан стекийг буцаана.
Хэрэв та Грахамын шүүрдэлт хийхдээ коллинеар цэгүүдийг оруулах шаардлагатай бол эрэмбэлсний дараа өөр нэг алхам хэрэгтэй. Та $P_0$-ээс хамгийн их туйлын зайтай бөгөөд коллинеар байх цэгүүдийг авах хэрэгтэй (эдгээр нь эрэмбэлэгдсэн векторын төгсгөлд байх ёстой). Энэ шулуун дээрх цэгүүдийг эргүүлэх ёстой бөгөөд ингэснээр бид бүх коллинеар цэгийг гаргаж чадна, эс бөгөөс алгоритм энэ шулуун дээрх хамгийн ойрын цэгийг аваад зогсоно. Энэ алхмыг алгоритмын коллинеар биш хувилбарт оруулах ёсгүй, эс бөгөөс та хамгийн бага гүдгэр бүрхүүлийг авахгүй.
Implementation¶
struct pt {
double x, y;
bool operator == (pt const& t) const {
return x == t.x && y == t.y;
}
};
int orientation(pt a, pt b, pt c) {
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }
void convex_hull(vector<pt>& a, bool include_collinear = false) {
pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.y, a.x) < make_pair(b.y, b.x);
});
sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
int o = orientation(p0, a, b);
if (o == 0)
return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
< (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
return o < 0;
});
if (include_collinear) {
int i = (int)a.size()-1;
while (i >= 0 && collinear(p0, a[i], a.back())) i--;
reverse(a.begin()+i+1, a.end());
}
vector<pt> st;
for (int i = 0; i < (int)a.size(); i++) {
while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
st.pop_back();
st.push_back(a[i]);
}
if (include_collinear == false && st.size() == 2 && st[0] == st[1])
st.pop_back();
a = st;
}
Монотон гинж алгоритм¶
Алгоритм эхлээд хамгийн зүүн ба хамгийн баруун A ба B цэгүүдийг олно. Ийм хэд хэдэн цэг байвал зүүн талынхаас хамгийн доодыг (хамгийн бага Y координаттайг) A болгон, баруун талынхаас хамгийн дээдийг (хамгийн их Y координаттайг) B болгон авна. A ба B хоёул хамгийн хол байгаа бөгөөд өгөгдсөн цэгүүдийн дундаас аль ч хосын үүсгэсэн шулуунд агуулагдаж чадахгүй тул тэдгээр гүдгэр бүрхүүлд харьяалагдах нь тодорхой.
Одоо AB-ээр шулуун татъя. Энэ нь бусад бүх цэгийг S1 ба S2 гэсэн хоёр олонлогт хуваана, энд S1 нь A ба B-г холбосон шулуунаас дээш байгаа бүх цэгийг, S2 нь A ба B-г холбосон шулуунаас доош байгаа бүх цэгийг агуулна. A ба B-г холбосон шулуун дээр орших цэгүүд аль ч олонлогт харьяалагдаж болно. A ба B цэгүүд хоёр олонлогт хоёуланд нь харьяалагдана. Одоо алгоритм дээд олонлог S1 ба доод олонлог S2-г байгуулаад дараа нь хариултыг авахын тулд тэдгээрийг нэгтгэнэ.
Дээд олонлогийг авахын тулд бид бүх цэгийг x координатаар эрэмбэлнэ. Цэг бүрийн хувьд бид дараахыг шалгана — одоогийн цэг сүүлчийн цэг мөн эсэх (бидний B гэж тодорхойлсон), эсвэл A ба одоогийн цэгийн хоорондох шулуун ба одоогийн цэг ба B-ийн хоорондох шулууны хоорондох чиглэл цагийн зүүний дагуу эсэх. Тэдгээр тохиолдолд одоогийн цэг дээд олонлог S1-д харьяалагдана. Цагийн зүүний дагуу эсвэл эсрэг эсэхийг чиглэлийг шалгах замаар шалгаж болно.
Хэрэв өгөгдсөн цэг дээд олонлогт харьяалагдаж байвал бид дээд гүдгэр бүрхүүл дэх сүүлээс хоёр дахь цэг ба сүүлчийн цэгийг холбосон шулуун, мөн дээд гүдгэр бүрхүүл дэх сүүлчийн цэг ба одоогийн цэгийг холбосон шулууны үүсгэсэн өнцгийг шалгана. Хэрэв өнцөг цагийн зүүний дагуу биш бол бид дээд гүдгэр бүрхүүлд хамгийн сүүлд нэмсэн цэгийг хасна, учир нь одоогийн цэг гүдгэр бүрхүүлд нэмэгдмэгцээ өмнөх цэгийг агуулж чадна.
Доод олонлог S2-ийн хувьд ижил логик үйлчилнэ. Хэрэв одоогийн цэг B байх, эсвэл A ба одоогийн цэг, мөн одоогийн цэг ба B-ийн үүсгэсэн шулуунуудын чиглэл цагийн зүүний эсрэг байвал тэр нь S2-д харьяалагдана.
Хэрэв өгөгдсөн цэг доод олонлогт харьяалагдаж байвал бид цагийн зүүний дагуу чиглэлийн оронд цагийн зүүний эсрэг чиглэлийг шалгахаас бусад талаар дээд олонлогийн цэгтэй адилаар үйлдэнэ. Ингэснээр хэрэв доод гүдгэр бүрхүүл дэх сүүлээс хоёр дахь цэг ба сүүлчийн цэгийг холбосон шулуун, мөн доод гүдгэр бүрхүүл дэх сүүлчийн цэг ба одоогийн цэгийг холбосон шулууны үүсгэсэн өнцөг цагийн зүүний эсрэг биш бол бид доод гүдгэр бүрхүүлд хамгийн сүүлд нэмсэн цэгийг хасна, учир нь одоогийн цэг бүрхүүлд нэмэгдмэгцээ өмнөх цэгийг агуулж чадна.
Эцсийн гүдгэр бүрхүүлийг дээд ба доод гүдгэр бүрхүүлийн нэгдлээс авах ба энэ нь цагийн зүүний дагуу бүрхүүл үүсгэнэ, хэрэгжүүлэлт нь дараах байдалтай.
Хэрэв танд коллинеар цэгүүд хэрэгтэй бол та зөвхөн цагийн зүүний дагуу/эсрэг горимуудад тэдгээрийг шалгахад л хангалттай. Гэвч энэ нь оролтын бүх цэг нэг шулуун дээр коллинеар байх degenerate case-ийг үүсгэх ба алгоритм давтагдсан цэгүүдийг гаргана. Үүнийг шийдэхийн тулд бид дээд бүрхүүл бүх цэгийг агуулж байгаа эсэхийг шалгаж, хэрэв агуулж байвал зүгээр л цэгүүдийг эсрэгээр нь буцаана, учир нь энэ тохиолдолд Грахамын хэрэгжүүлэлт үүнийг буцаах болно.
Implementation¶
struct pt {
double x, y;
};
int orientation(pt a, pt b, pt c) {
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool ccw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o > 0 || (include_collinear && o == 0);
}
void convex_hull(vector<pt>& a, bool include_collinear = false) {
if (a.size() == 1)
return;
sort(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
});
pt p1 = a[0], p2 = a.back();
vector<pt> up, down;
up.push_back(p1);
down.push_back(p1);
for (int i = 1; i < (int)a.size(); i++) {
if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
up.pop_back();
up.push_back(a[i]);
}
if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
down.pop_back();
down.push_back(a[i]);
}
}
if (include_collinear && up.size() == a.size()) {
reverse(a.begin(), a.end());
return;
}
a.clear();
for (int i = 0; i < (int)up.size(); i++)
a.push_back(up[i]);
for (int i = down.size() - 2; i > 0; i--)
a.push_back(down[i]);
}