55-rasm. Qobiq, qavariq qobiq va minimal qavariq qobiq
tushunchalari
Minimal
qavariq
qobiqni
qurish
masalasi
hisoblash
geometriyasidagi eng oddiy muammolardan biri hisoblanadi; buning
a) Qobiq
b) Qavariq qobiq
c) Minimal qavariq
qobiq
153
uchun juda ko'p turli algoritmlar mavjud. Quyida biz ikkita algoritmni
ko'rib chiqamiz – Grexem (Graham scan) va Jarvis (Jarvis march).
Grexem algoritmi quyidagi 56-rasmda ketma-ket keltirilgan.
1-qadam
2-qadam
3-qadam
4-qadam
5-qadam
6-qadam
154
7-qadam
8-qadam
9-qadam
10-qadam
11-qadam
12-qadam
56-rasm. Grexem algoritmining bajarilish ketma-ketligi
155
Grexem algoritmi realizatsiyasi (C++ tilida)
#include
#include
#include
using namespace std;
struct Point
{
int x, y;
};
Point p0;
Point nextToTop(stack
&S)
{
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);
return res;
}
void swap(Point &p1, Point &p2)
{
Point temp = p1;
p1 = p2;
p2 = temp;
}
int distSq(Point p1, Point p2)
{
return (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y);
}
int 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;
156
return (val > 0)? 1: 2;
}
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *)vp1;
Point *p2 = (Point *)vp2;
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
return (o == 2)? -1: 1;
}
void convexHull(Point points[], int n)
{
int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++)
{
int y = points[i].y;
if ((y < ymin) || (ymin == y &&
points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[1], n-1, sizeof(Point), compare);
int m = 1; // Initialize size of modified array
for (int i=1; i
{
while (i < n-1 && orientation(p0, points[i],
points[i+1]) == 0)
i++;
points[m] = points[i];
m++;
if (m < 3) return;
157
stack
S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for (int i = 3; i < m; i++)
{
while (S.size()>1 && orientation(nextToTop(S), S.top(), points[i])
!= 2)
S.pop();
S.push(points[i]);
}
while (!S.empty())
{
Point p = S.top();
cout << "(" << p.x << ", " << p.y <<")" << endl;
S.pop();
}
}
}
int main()
{
Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
{0, 0}, {1, 2}, {3, 1}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
}
12.2. Tekislikda chiziqlar kesishgan sohalarni qidirish algoritmi
(Sweep Line)
Tekislikda
chiziqlar
kesishgan
sohalarni
qidirish
algoritmi(Sweep Line) -
bu Yevklid fazosidagi turli xil muammolarni
hal qilish uchun kesishgan sohalardan foydalanadigan algoritmik
paradigma. Bu hisoblash geometriyasidagi asosiy texnikalardan biridir.
158
Ushbu turdagi algoritmlarning gʻoyasi ba'zi bir nuqtalarda to'xtab,
tekislik bo'ylab harakatlanadigan xayoliy to'gʻri chiziqni (ko'pincha
vertikal) tasavvur qilishdir. Geometrik amallar, kesishgan chiziqqa
qo'shni bo'lgan geometrik obyektlar bilan cheklanadi va chiziq barcha
obyektlardan o'tib ketganda to'liq yechim mavjud boʻladi.
Sweep Line
– bu tekislik bo'ylab to'gʻri yo'nalishda siljigan
xayoliy vertikal chiziq. Shuning uchun bu konsepsiyaga asoslangan
algoritmlarni ba'zan tekisliklarni tozalash algoritmlari deb ham
atashadi. Chiziqni diskretlashtirish uchun biz ba'zi hodisalarga asoslanib
tozalaymiz.
Yana shuni ta'kidlash kerakki, bu texnikaning samaradorligi biz
foydalanadigan ma'lumotlar tuzilmalariga bogʻliq. Umuman olganda, biz
C++ da setdan foydalanishimiz mumkin, lekin ba'zida biz qo'shimcha
ma'lumotlarni
saqlashni
talab
qilamiz,
shuning
uchun
biz
muvozanatlashgan ikkilik daraxtga o'tamiz.
Misol. Sweep Line algoritmining ishlash tartibi
Harakatlar:
SLH -ga s4 -ni kiriting
Test s4-s3 va s4-s2
N ga e1 ga qo'shing
Sweep Line holati: s0, s1, s2, s4, s3
Sweep Line holati
(SLH): s0, s1, s2, s3
Navbat (N): a4, b1, b2,
b0, b3, b4
159
Navbat: b1,e1, b2, b0, b3, b4
Harakatlar:
SLH dan s1 ni oʻchiring
Test s0-s2
N ga e2 ga qo'shing
Sweep Line holati: s0, s2, s4, s3
Navbat: e1, e2, b2, b0, b3, b4
Harakatlar:
SLH da s3 va s4 ni almashtiring
Test s3-s2
160
Sweep Line holati: s0, s2, s3, s4
Navbat: e2, b2, b0, b3, b4
|
