Хавтгай графын нүүрийг олох¶
$n$ орой ба $m$ ирмэгтэй $G$ графыг авч үзье, түүнийг хоёр ирмэг зөвхөн нийтлэг оройд (хэрэв байгаа бол) огтлолцохоор хавтгай дээр зурж болно. Ийм графыг хавтгай гэж нэрлэдэг. Одоо бидэнд хавтгай граф түүний шулуун шугаман шигтгээний хамт өгөгдсөн гэж үзье, энэ нь орой $v$ бүрийн хувьд бидэнд харгалзах $(x, y)$ цэг байх ба бүх ирмэгийг эдгээр цэгүүдийн хооронд огтлолцолгүйгээр хэрчим хэлбэрээр зурсан гэсэн үг юм (ийм шигтгээ үргэлж оршин байдаг). Эдгээр хэрчим хавтгайг хэд хэдэн муж болгон хуваах ба тэдгээрийг нүүр гэж нэрлэдэг. Нүүрнүүдийн яг нэг нь хязгаарлагдмал биш байна. Энэ нүүрийг гадна гэж нэрлэх ба бусад нүүрийг дотор гэж нэрлэдэг.
Энэ өгүүлэлд бид хавтгай графын дотор ба гадна нүүрийг хоёуланг нь олох талаар авч үзнэ. Бид граф холбоост гэж үзнэ.
Хавтгай графын талаарх зарим баримт¶
Энэ хэсэгт бид хавтгай графын талаарх хэд хэдэн баримтыг баталгаагүйгээр танилцуулна. Баталгаа сонирхож буй уншигчид R. Diestel-ийн Graph Theory (мөн энэ номон дээр суурилсан хавтгай чанарын видео лекцүүдийг үз) эсвэл өөр номыг үзэх хэрэгтэй.
Эйлерийн теорем¶
Эйлерийн теорем нь $n$ орой, $m$ ирмэг, $f$ нүүртэй холбоост хавтгай графын дурын зөв шигтгээ дараахыг хангана гэж өгүүлдэг:
Мөн илүү ерөнхийд нь $k$ холбоост компоненттой хавтгай граф бүр дараахыг хангана:
Хавтгай графын ирмэгийн тоо.¶
Хэрэв $n \ge 3$ бол $n$ оройтой хавтгай графын ирмэгийн хамгийн их тоо $3n - 6$ байна. Энэ тоонд нүүр бүр нь гурвалжнаар хүрээлэгдсэн дурын холбоост хавтгай граф хүрдэг. Complexity-ийн хувьд энэ баримт нь дурын хавтгай графын хувьд $m = O(n)$ гэсэн үг юм.
Хавтгай графын нүүрийн тоо.¶
Дээрх баримтын шууд үр дагавар болгон хэрэв $n \ge 3$ бол $n$ оройтой хавтгай графын нүүрийн хамгийн их тоо $2n - 4$ байна.
Хавтгай граф дахь оройн хамгийн бага зэрэг.¶
Хавтгай граф бүр 5 буюу түүнээс бага зэрэгтэй оройтой байна.
Алгоритм¶
Эхлээд орой бүрийн зэргэлдээ ирмэгүүдийг туйлын өнцгөөр эрэмбэл. Одоо графыг дараах байдлаар тойрцгооё. Бид $u$ оройд $(v, u)$ ирмэгээр орсон бөгөөд $(u, w)$ нь $u$-ийн эрэмбэлэгдсэн зэргэлдээгийн жагсаалт дахь $(v, u)$-ийн дараах ирмэг гэж үзье. Тэгвэл дараагийн орой $w$ байна. Хэрэв бид энэ тойролтыг ямар нэг $(v, u)$ ирмэгээс эхлүүлбэл бид $(v, u)$-д зэргэлдээ нүүрнүүдийн яг нэгийг тойрох ба яг аль нүүр байх нь бидний эхний алхам $u$-ээс $v$ рүү эсвэл $v$-ээс $u$ рүү байхаас хамаарна.
Одоо алгоритм нэлээд илэрхий болно. Бид графын бүх ирмэгийг тойрч, өмнөх тойролтуудын аль нэгээр нь зочлоогүй ирмэг бүрийн хувьд тойролтыг эхлүүлэх ёстой. Ингэснээр бид нүүр бүрийг яг нэг удаа олох ба ирмэг бүрийг хоёр удаа тойрно (чиглэл тус бүрд нэг удаа).
Дараагийн ирмэгийг олох¶
Тойролтын явцад бид цагийн зүүний эсрэг дараалал дахь дараагийн ирмэгийг олох ёстой. Дараагийн ирмэгийг олох хамгийн илэрхий арга бол өнцгөөр хоёртын хайлт хийх явдал юм. Гэвч орой бүрийн зэргэлдээ ирмэгүүдийн цагийн зүүний эсрэг эрэмбийг харгалзвал бид дараагийн ирмэгүүдийг урьдчилан тооцоолж, хэш хүснэгтэд хадгалж болно. Хэрэв ирмэгүүд аль хэдийн өнцгөөр эрэмбэлэгдсэн бол энэ тохиолдолд бүх нүүрийг олох complexity шугаман болно.
Гадна нүүрийг олох¶
Алгоритм дотор нүүр бүрийг цагийн зүүний дагуу дарааллаар, гадна нүүрийг цагийн зүүний эсрэг дарааллаар тойрдгийг харахад хэцүү биш тул гадна нүүрийг нүүр бүрийн эрэмбийг шалгах замаар олж болно.
Complexity¶
Эрэмбэлэлтээс болж алгоритмын complexity нь $O(m \log m)$ бөгөөд $m = O(n)$ тул үнэндээ $O(n \log n)$ болох нь нэлээд тодорхой. Өмнө дурдсанчлан эрэмбэлэлтгүйгээр complexity нь $O(n)$ болно.
Хэрэв граф холбоост биш бол яах вэ?¶
Эхлээд харахад холбоост биш графын нүүрийг олох нь тийм ч хэцүү биш мэт санагдаж болно, учир нь бид холбоост компонент бүрийн хувьд ижил алгоритмыг ажиллуулж болно. Гэвч компонентууд үүрлэсэн байдлаар зурагдаж, нүх үүсгэж болно (доорх зургийг үз). Энэ тохиолдолд зарим компонентын дотор нүүр нь бусад зарим компонентын гадна нүүр болох ба төвөгтэй холбоост биш заагтай байна. Ийм тохиолдлуудтай ажиллах нь нэлээд хэцүү бөгөөд нэг боломжит арга бол үүрлэсэн компонентуудыг цэгийн байршлыг олох алгоритмуудаар тодорхойлох явдал юм.
Implementation¶
The following implementation returns a vector of vertices for each face, outer face goes first. Inner faces are returned in counter-clockwise orders and the outer face is returned in clockwise order.
For simplicity we find the next edge by doing binary search by angle.
struct Point {
int64_t x, y;
Point(int64_t x_, int64_t y_): x(x_), y(y_) {}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
int64_t cross (const Point & p) const {
return x * p.y - y * p.x;
}
int64_t cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
int half () const {
return int(y < 0 || (y == 0 && x < 0));
}
};
std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::vector<std::vector<size_t>> adj) {
size_t n = vertices.size();
std::vector<std::vector<char>> used(n);
for (size_t i = 0; i < n; i++) {
used[i].resize(adj[i].size());
used[i].assign(adj[i].size(), 0);
auto compare = [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[i];
Point pr = vertices[r] - vertices[i];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
};
std::sort(adj[i].begin(), adj[i].end(), compare);
}
std::vector<std::vector<size_t>> faces;
for (size_t i = 0; i < n; i++) {
for (size_t edge_id = 0; edge_id < adj[i].size(); edge_id++) {
if (used[i][edge_id]) {
continue;
}
std::vector<size_t> face;
size_t v = i;
size_t e = edge_id;
while (!used[v][e]) {
used[v][e] = true;
face.push_back(v);
size_t u = adj[v][e];
size_t e1 = std::lower_bound(adj[u].begin(), adj[u].end(), v, [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[u];
Point pr = vertices[r] - vertices[u];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
}) - adj[u].begin() + 1;
if (e1 == adj[u].size()) {
e1 = 0;
}
v = u;
e = e1;
}
std::reverse(face.begin(), face.end());
Point p1 = vertices[face[0]];
__int128 sum = 0;
for (int j = 0; j < face.size(); ++j) {
Point p2 = vertices[face[j]];
Point p3 = vertices[face[(j + 1) % face.size()]];
sum += (p2 - p1).cross(p3 - p2);
}
if (sum <= 0) {
faces.insert(faces.begin(), face);
} else {
faces.emplace_back(face);
}
}
}
return faces;
}
Хэрчмүүдээс хавтгай граф байгуулах¶
Заримдаа танд граф шууд өгөгддөггүй, харин хавтгай дээрх хэрчмүүдийн олонлог хэлбэрээр өгөгддөг ба доорх зурган дээр үзүүлсэнчлэн бодит граф нь тэдгээр хэрчмийг огтлолцуулах замаар үүснэ. Энэ тохиолдолд та графыг гараар байгуулах ёстой. Үүнийг хийх хамгийн хялбар арга нь дараах байдалтай. Хэрчмийг тогтоогоод түүнийг бусад бүх хэрчимтэй огтлолцуул. Дараа нь бүх огтлолцлын цэгийг хэрчмийн хоёр үзүүрийн цэгтэй нь хамт лексикографын дарааллаар эрэмбэлж, тэдгээрийг график орой болгон нэм. Мөн лексикографын дараалал дахь зэргэлдээ хоёр орой бүрийг ирмэгээр холбо. Бүх ирмэгийн хувьд энэ үйл ажиллагааг хийсний дараа бид графыг авна. Мэдээж бид тэнцүү хоёр огтлолцлын цэг үргэлж нэг оройд харгалзахыг баталгаажуулах ёстой. Үүнийг хийх хамгийн хялбар арга бол цэгүүдийг координатаар нь map-д хадгалж, координат нь бага тоогоор (жишээ нь $10^{-9}$-ээс бага) ялгаатай цэгүүдийг тэнцүү гэж үзэх явдал юм. Энэ алгоритм $O(n^2 \log n)$-д ажиллана.
Implementation¶
using dbl = long double;
const dbl eps = 1e-9;
struct Point {
dbl x, y;
Point(){}
Point(dbl x_, dbl y_): x(x_), y(y_) {}
Point operator * (dbl d) const {
return Point(x * d, y * d);
}
Point operator + (const Point & p) const {
return Point(x + p.x, y + p.y);
}
Point operator - (const Point & p) const {
return Point(x - p.x, y - p.y);
}
dbl cross (const Point & p) const {
return x * p.y - y * p.x;
}
dbl cross (const Point & p, const Point & q) const {
return (p - *this).cross(q - *this);
}
dbl dot (const Point & p) const {
return x * p.x + y * p.y;
}
dbl dot (const Point & p, const Point & q) const {
return (p - *this).dot(q - *this);
}
bool operator < (const Point & p) const {
if (fabs(x - p.x) < eps) {
if (fabs(y - p.y) < eps) {
return false;
} else {
return y < p.y;
}
} else {
return x < p.x;
}
}
bool operator == (const Point & p) const {
return fabs(x - p.x) < eps && fabs(y - p.y) < eps;
}
bool operator >= (const Point & p) const {
return !(*this < p);
}
};
struct Line{
Point p[2];
Line(Point l, Point r){p[0] = l; p[1] = r;}
Point& operator [](const int & i){return p[i];}
const Point& operator[](const int & i)const{return p[i];}
Line(const Line & l){
p[0] = l.p[0]; p[1] = l.p[1];
}
Point getOrth()const{
return Point(p[1].y - p[0].y, p[0].x - p[1].x);
}
bool hasPointLine(const Point & t)const{
return std::fabs(p[0].cross(p[1], t)) < eps;
}
bool hasPointSeg(const Point & t)const{
return hasPointLine(t) && t.dot(p[0], p[1]) < eps;
}
};
std::vector<Point> interLineLine(Line l1, Line l2){
if(std::fabs(l1.getOrth().cross(l2.getOrth())) < eps){
if(l1.hasPointLine(l2[0]))return {l1[0], l1[1]};
else return {};
}
Point u = l2[1] - l2[0];
Point v = l1[1] - l1[0];
dbl s = u.cross(l2[0] - l1[0])/u.cross(v);
return {Point(l1[0] + v * s)};
}
std::vector<Point> interSegSeg(Line l1, Line l2){
if (l1[0] == l1[1]) {
if (l2[0] == l2[1]) {
if (l1[0] == l2[0])
return {l1[0]};
else
return {};
} else {
if (l2.hasPointSeg(l1[0]))
return {l1[0]};
else
return {};
}
}
if (l2[0] == l2[1]) {
if (l1.hasPointSeg(l2[0]))
return {l2[0]};
else
return {};
}
auto li = interLineLine(l1, l2);
if (li.empty())
return li;
if (li.size() == 2) {
if (l1[0] >= l1[1])
std::swap(l1[0], l1[1]);
if (l2[0] >= l2[1])
std::swap(l2[0], l2[1]);
std::vector<Point> res(2);
if (l1[0] < l2[0])
res[0] = l2[0];
else
res[0] = l1[0];
if (l1[1] < l2[1])
res[1] = l1[1];
else
res[1] = l2[1];
if (res[0] == res[1])
res.pop_back();
if (res.size() == 2u && res[1] < res[0])
return {};
else
return res;
}
Point cand = li[0];
if (l1.hasPointSeg(cand) && l2.hasPointSeg(cand))
return {cand};
else
return {};
}
std::pair<std::vector<Point>, std::vector<std::vector<size_t>>> build_graph(std::vector<Line> segments) {
std::vector<Point> p;
std::vector<std::vector<size_t>> adj;
std::map<std::pair<int64_t, int64_t>, size_t> point_id;
auto get_point_id = [&](Point pt) {
auto repr = std::make_pair(
int64_t(std::round(pt.x * 1000000000) + 1e-6),
int64_t(std::round(pt.y * 1000000000) + 1e-6)
);
if (!point_id.count(repr)) {
adj.emplace_back();
size_t id = point_id.size();
point_id[repr] = id;
p.push_back(pt);
return id;
} else {
return point_id[repr];
}
};
for (size_t i = 0; i < segments.size(); i++) {
std::vector<size_t> curr = {
get_point_id(segments[i][0]),
get_point_id(segments[i][1])
};
for (size_t j = 0; j < segments.size(); j++) {
if (i == j)
continue;
auto inter = interSegSeg(segments[i], segments[j]);
for (auto pt: inter) {
curr.push_back(get_point_id(pt));
}
}
std::sort(curr.begin(), curr.end(), [&](size_t l, size_t r) { return p[l] < p[r]; });
curr.erase(std::unique(curr.begin(), curr.end()), curr.end());
for (size_t j = 0; j + 1 < curr.size(); j++) {
adj[curr[j]].push_back(curr[j + 1]);
adj[curr[j + 1]].push_back(curr[j]);
}
}
for (size_t i = 0; i < adj.size(); i++) {
std::sort(adj[i].begin(), adj[i].end());
// removing edges that were added multiple times
adj[i].erase(std::unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
return {p, adj};
}