ساخت پوش محدب¶
در این مقاله به مسئله‌ی ساختن پوش محدب از مجموعه‌ای از نقاط می‌پردازیم.
با داشتن $N$ نقطه در یک صفحه، هدف ساختن یک پوش محدب است، یعنی کوچکترین چندضلعی محدبی که شامل تمام نقاط داده شده باشد.
ما الگوریتم اسکن گراهام (Graham's scan) که در سال ۱۹۷۲ توسط گراهام منتشر شد و همچنین الگوریتم زنجیره‌ی یکنوا (Monotone chain) که در سال ۱۹۷۹ توسط اندرو منتشر شد را بررسی خواهیم کرد. هر دو الگوریتم از مرتبه‌ی زمانی $\mathcal{O}(N \log N)$ هستند و از نظر مجانبی بهینه محسوب می‌شوند (چرا که ثابت شده است الگوریتمی با مرتبه‌ی زمانی بهتر وجود ندارد)، به استثنای چند مسئله‌ی خاص که شامل پردازش موازی یا برخط (آنلاین) می‌شوند.
الگوریتم اسکن گراهام (Graham's scan)¶
این الگوریتم ابتدا پایین‌ترین نقطه، $P_0$، را پیدا می‌کند. اگر چندین نقطه با مختصات Y یکسان وجود داشته باشند، نقطه‌ای با مختصات X کوچکتر در نظر گرفته می‌شود. این مرحله $\mathcal{O}(N)$ زمان می‌برد.
سپس، تمام نقاط دیگر بر اساس زاویه‌ی قطبی و به ترتیب ساعتگرد مرتب‌سازی می‌شوند. اگر زاویه‌ی قطبی بین دو یا چند نقطه یکسان باشد، گره‌گشایی باید بر اساس فاصله از $P_0$ و به ترتیب صعودی انجام شود.
سپس ما هر نقطه را یک به یک پیمایش می‌کنیم و اطمینان حاصل می‌کنیم که نقطه‌ی فعلی و دو نقطه‌ی قبل از آن یک چرخش ساعتگرد ایجاد کنند، در غیر این صورت نقطه‌ی قبلی حذف می‌شود، زیرا شکلی غیرمحدب ایجاد می‌کند. بررسی ساعتگرد یا پادساعتگرد بودن چرخش می‌تواند با بررسی جهت انجام شود.
ما از یک پشته (stack) برای ذخیره‌ی نقاط استفاده می‌کنیم، و هنگامی که به نقطه‌ی اصلی $P_0$ می‌رسیم، الگوریتم به پایان رسیده و ما پشته را که حاوی تمام نقاط پوش محدب به ترتیب ساعتگرد است، برمی‌گردانیم.
اگر نیاز دارید که نقاط هم‌خط را هنگام اجرای اسکن گراهام در نظر بگیرید، به یک مرحله‌ی دیگر پس از مرتب‌سازی نیاز دارید. باید نقاطی را که بیشترین فاصله‌ی قطبی را از $P_0$ دارند (این نقاط باید در انتهای بردار مرتب‌شده قرار گیرند) و هم‌خط هستند، پیدا کنید. نقاط موجود در این خط باید معکوس شوند تا بتوانیم تمام نقاط هم‌خط را خروجی دهیم، در غیر این صورت الگوریتم نزدیک‌ترین نقطه در این خط را گرفته و خارج می‌شود. این مرحله نباید در نسخه‌ی غیرهم‌خط الگوریتم گنجانده شود، وگرنه کوچکترین پوش محدب را دریافت نخواهید کرد.
پیاده‌سازی¶
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; // ساعتگرد
if (v > 0) return +1; // پادساعتگرد
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;
}
الگوریتم زنجیره‌ی یکنوا (Monotone chain)¶
این الگوریتم ابتدا چپ‌ترین و راست‌ترین نقاط، یعنی A و B را پیدا می‌کند. اگر چندین نقطه با این مشخصات وجود داشته باشند، پایین‌ترین نقطه در میان نقاط چپ (با کمترین مختصات Y) به عنوان A و بالاترین نقطه در میان نقاط راست (با بیشترین مختصات Y) به عنوان B در نظر گرفته می‌شود. واضح است که هر دو نقطه A و B باید به پوش محدب تعلق داشته باشند، زیرا آن‌ها دورترین نقاط هستند و نمی‌توانند توسط هیچ خطی که از یک جفت نقطه دیگر تشکیل شده باشد، محصور شوند.
حال، خطی از A به B رسم می‌کنیم. این خط تمام نقاط دیگر را به دو مجموعه‌ی S1 و S2 تقسیم می‌کند، که در آن S1 شامل تمام نقاط بالای خط واصل A و B است و S2 شامل تمام نقاط پایین خط واصل A و B است. نقاطی که روی خط واصل A و B قرار دارند می‌توانند به هر یک از این دو مجموعه تعلق داشته باشند. نقاط A و B به هر دو مجموعه تعلق دارند. اکنون الگوریتم مجموعه‌ی بالایی S1 و مجموعه‌ی پایینی S2 را می‌سازد و سپس آن‌ها را برای به دست آوردن پاسخ نهایی ترکیب می‌کند.
برای به دست آوردن مجموعه‌ی بالایی، ما تمام نقاط را بر اساس مختصات x مرتب می‌کنیم. برای هر نقطه بررسی می‌کنیم که آیا - نقطه‌ی فعلی، آخرین نقطه (که آن را B تعریف کردیم) است، یا اینکه جهت‌گیری سه‌نقطه‌ی A، نقطه‌ی فعلی و B پادساعتگرد است. در این موارد، نقطه‌ی فعلی به مجموعه‌ی بالایی S1 تعلق دارد. بررسی ساعتگرد یا پادساعتگرد بودن جهت می‌تواند با بررسی جهت انجام شود.
اگر نقطه‌ی داده شده به مجموعه‌ی بالایی تعلق داشته باشد، ما زاویه‌ی ایجاد شده توسط خطی که نقطه‌ی یکی به آخر و نقطه‌ی آخر در پوش محدب بالایی را به هم وصل می‌کند، با خطی که نقطه‌ی آخر در پوش محدب بالایی و نقطه‌ی فعلی را به هم وصل می‌کند، بررسی می‌کنیم. اگر زاویه ساعتگرد نباشد (یعنی پادساعتگرد یا هم‌خط باشد)، ما آخرین نقطه‌ی اضافه شده به پوش محدب بالایی را حذف می‌کنیم، زیرا نقطه‌ی فعلی پس از اضافه شدن به پوش محدب، قادر خواهد بود نقطه‌ی قبلی را در بر بگیرد.
منطق مشابهی برای مجموعه‌ی پایینی S2 نیز به کار می‌رود. اگر - نقطه‌ی فعلی B باشد، یا جهت‌گیری سه‌نقطه‌ی A، نقطه‌ی فعلی و B ساعتگرد باشد - آنگاه این نقطه به S2 تعلق دارد.
اگر نقطه‌ی داده شده به مجموعه‌ی پایینی تعلق داشته باشد، ما مشابه حالتی که برای نقطه‌ای در مجموعه‌ی بالایی عمل کردیم، رفتار می‌کنیم، با این تفاوت که به جای جهت ساعتگرد، جهت پادساعتگرد را بررسی می‌کنیم. بنابراین، اگر زاویه‌ی ایجاد شده توسط خطی که نقطه‌ی یکی به آخر و نقطه‌ی آخر در پوش محدب پایینی را به هم وصل می‌کند، با خطی که نقطه‌ی آخر در پوش محدب پایینی و نقطه‌ی فعلی را به هم وصل می‌کند، پادساعتگرد نباشد (یعنی ساعتگرد یا هم‌خط باشد)، ما آخرین نقطه‌ی اضافه شده به پوش محدب پایینی را حذف می‌کنیم، زیرا نقطه‌ی فعلی پس از اضافه شدن به پوش، قادر خواهد بود نقطه‌ی قبلی را در بر بگیرد.
پوش محدب نهایی از اجتماع پوش محدب بالایی و پایینی به دست می‌آید و یک پوش ساعتگرد را تشکیل می‌دهد. پیاده‌سازی آن به شرح زیر است.
اگر به نقاط هم‌خط نیاز دارید، کافی است در روال‌های بررسی ساعتگرد/پادساعتگرد آن‌ها را نیز در نظر بگیرید. با این حال، این کار اجازه‌ی یک حالت خاص را می‌دهد که در آن تمام نقاط ورودی روی یک خط مستقیم قرار دارند و الگوریتم نقاط تکراری را خروجی می‌دهد. برای حل این مشکل، ما بررسی می‌کنیم که آیا پوش بالایی شامل تمام نقاط است یا خیر، و اگر چنین بود، فقط نقاط را به ترتیب معکوس برمی‌گردانیم، زیرا این همان چیزی است که پیاده‌سازی گراهام در این حالت برمی‌گرداند.
پیاده‌سازی¶
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; // ساعتگرد
if (v > 0) return +1; // پادساعتگرد
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]);
}