INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
583
Abdullayev Shaxboz Solijon o‘g‘li
FarDU Axborot texnologiyalari kafedrasi dotsenti
shaxbozfardu2023@gmail.com
ORCID ID
Akramova Madinaxon Mashrabjon qizi
Farg‘ona davlat universiteti
Axborot tizimlari va texnologiyalari yoʻnalishi I kurs talabasi
akramovamadinabonu676@gmail.com
GEOMETRIK ALGORITMLAR
Annotatsiya:
Mazkur maqolada hisoblash geometriyasining muhim yo‘nalishi bo‘lgan geometrik
algoritmlar chuqur tahlil qilinadi. Geometrik obyektlar — nuqta, chiziq, ko‘pburchak va aylana
bilan ishlaydigan algoritmlar turlari, ularning matematik asoslari va dasturlashda qo‘llanilishi
ko‘rib chiqiladi. Graham scan, Delaunay triangulyatsiyasi, Voronoy diagrammalari, KD-daraxt
kabi algoritmlarning ishlash mexanizmi va amaliy dasturiy sohalardagi o‘rni yoritiladi. Ayniqsa,
ularning kompyuter grafikasi, robototexnika, o‘yinlar ishlab chiqish va geoinformatsion
tizimlardagi ahamiyati alohida tahlil qilinadi. Ushbu maqola texnik fanlar bilan shug‘ullanuvchi
talabalar va dasturchilar uchun foydali bo‘lishi mumkin.
Аннотатция:
В данной статье проводится подробный анализ геометрических алгоритмов
— одного из ключевых направлений вычислительной геометрии. Рассматриваются
алгоритмы,
работающие
с
геометрическими
объектами:
точками,
линиями,
многоугольниками и окружностями. Подробно описаны такие алгоритмы, как метод
Грэма, триангуляция Делоне, диаграммы Вороного и KD-деревья. Особое внимание
уделяется их применению в компьютерной графике, робототехнике, разработке игр и
геоинформационных системах. Материал статьи будет полезен студентам технических
специальностей и программистам, интересующимся задачами на основе геометрии.
Annotation:
This paper provides an in-depth analysis of geometric algorithms, a key area within
computational geometry. It explores various algorithms used for processing geometric entities
such as points, lines, polygons, and circles. Algorithms like Graham scan, Delaunay triangulation,
Voronoi diagrams, and KD-trees are discussed in terms of their underlying logic and practical
implementations. The relevance of these algorithms in computer graphics, robotics, game
development, and geographic information systems is thoroughly examined. This article aims to
be a useful resource for students of technical disciplines and software developers interested in
geometry-based problem-solving.
Kalit so‘zlar:
geometrik algoritmlar, hisoblash geometriyasi, konveks qobiq, Voronoy
diagrammasi, Delaunay triangulyatsiyasi, algoritmik murakkablik, kompyuter grafikasi, KD-
daraxt
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
584
Ключевые слова:
геометрические алгоритмы, вычислительная геометрия, выпуклая
оболочка, диаграмма Вороного, триангуляция Делоне, сложность алгоритма,
компьютерная графика, KD-дерево
Keywords:
geometric algorithms, computational geometry, convex hull, Voronoi diagram,
Delaunay triangulation, algorithm complexity, computer graphics, KD-tree
Kirish
Hisoblash geometriyasi zamonaviy informatika va muhandislik fanining asosiy yo‘nalishlaridan
biridir. Uning markazida turuvchi geometrik algoritmlar yordamida fazoviy obyektlar bilan
bog‘liq murakkab masalalar yechiladi. Bu algoritmlar yordamida nafaqat shakllar ustida amallar
bajariladi, balki obyektlar o‘zaro taʼsirini bashorat qilish, fazoviy harakatlarni simulyatsiya qilish
va ko‘plab texnologik jarayonlarni avtomatlashtirish mumkin.
Geometrik algoritmlarning nazariy asoslari
Geometrik algoritmlar hisoblash geometriyasi fanining bir bo‘limi hisoblanadi. Ushbu
algoritmlar ikki yoki uch o‘lchovli fazoda joylashgan obyektlar ustida amallar bajarishga
qaratilgan bo‘lib, ular quyidagi asosiy turlarni o‘z ichiga oladi:
1. Qamrab oluvchi konveks (Convex Hull) — nuqtalar to‘plamini tashqi tomondan qamrab
oluvchi eng kichik konveks shaklni topish.
2. Nuqtaning ko‘pburchak ichida joylashganligini aniqlash — turli geolokatsion ilovalarda
ishlatiladi.
3. Chiziqlar kesishishini aniqlash (Intersection Detection) — yo‘l tarmog‘i yoki grafik
tizimlarida zarur.
4. Voronoy diagrammasi va Delaunay uchburchalash — hududlarni bo‘lish, tarmoq hosil
qilishda keng qo‘llaniladi.
5. Triangulyatsiya va chizmalarni tarmoqlash — 3D modellash va finite element analizlarida
muhim.
Bu algoritmlar kombinatorika, evklid geometriyasi, grafik nazariyasi, trigonometriya va
algebraik metodlarga asoslanadi.
Mashhur algoritmlar va ularning ishlash prinsiplari
Graham Scan: Konveks qobiq yasash uchun tezkor va samarali algoritm. Nuqtalar qiyosiy
burchakka qarab saralanadi va stek yordamida konveks shakl hosil qilinadi.
Jarvis March: "Gift wrapping" algoritmi sifatida tanilgan. Har bir bosqichda eng chapdagi
nuqtadan boshlab, keyingi tashqi nuqtani aniqlash orqali konveks qobiq tuziladi.Sweep Line
algoritmi: Ko‘pburchaklar va chiziqlar to‘plamida kesishuvlarni aniqlash uchun ideal. U fazoni
gorizontal chiziq bilan "supurish" orqali harakat qiladi.
Voronoy diagrammasi: Fazoni berilgan nuqtalar atrofida bo‘lib chiqadi. Har bir hududga tegishli
nuqtalar unga eng yaqin bo‘lgan nuqtalardan iborat bo‘ladi.
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
585
Delaunay triangulyatsiyasi: Har bir uchburchakning aylana ichida boshqa nuqtalar tushmasligini
taʼminlaydigan triangulyatsiya.
Matematik asoslar
Ko‘plab geometrik algoritmlar matematik isbot va formulalarga tayanadi. Masalan, Graham
Scan algoritmida vektorlar orasidagi burchakni hisoblashda quyidagidan foydalaniladi:
Bu orqali nuqtalar saralanadi va konveks qobiq shakllanadi. Shuningdek, Delaunay
triangulyatsiyasi uchun quyidagi shart bajarilishi kerak:
Afzallik va murakkablik
Geometrik algoritmlar quyidagi afzalliklarga ega:
Yuqori aniqlik
Fazoviy tahlil imkoniyati
Har xil fanlarga moslashuvchanlik
Vaqt va xotira jihatdan optimallashtirilgan
Murakkablik darajasi esa algoritmning tuzilishiga bog‘liq
Graham Scan:
Jarvis March: (h — qobiqdagi nuqtalar soni)
Sweep Line: , bu yerda k — kesishuvlar soni
Geometrik algoritmlarning qo‘llanilishi
Kompyuter grafikasi — tasvirlarni chizish, 3D modellashtirish va animatsiyalar yaratishda.
GPS va xarita ilovalari — joylashuv aniqlash va yo‘l qidirishda.
Robototexnika — robotlarning muhitda harakatlanishini rejalashtirishda.
Arxitektura va dizayn — binolar va interyer loyihalarini qurishda.
O‘yin sanoati — virtual dunyolarda obyektlar harakatini hisoblashda.
Xulosa
Geometrik algoritmlar – bu zamonaviy hisoblash texnologiyalarining ajralmas tarkibiy
qismlaridan biridir. Ular turli xil geometrik shakllar va obyektlar ustida aniq, tezkor va optimal
hisob-kitoblarni amalga oshirish imkonini beradi. Maqolada ko‘rib chiqilgan konveks qobiq
aniqlash, chiziqlar kesishuvini topish, Voronoy diagrammalari va Delaunay triangulyatsiyasi
kabi algoritmlar bugungi kunda kompyuter grafikasi, sun’iy intellekt, robototexnika,
geoinformatsion tizimlar, 3D modellashtirish va simulyatsiyalar kabi ko‘plab sohalarda keng
foydalanilmoqda.
INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCHERS
ISSN: 3030-332X Impact factor: 8,293
Volume 11, issue 1, April 2025
https://wordlyknowledge.uz/index.php/IJSR
worldly knowledge
Index:
google scholar, research gate, research bib, zenodo, open aire.
https://scholar.google.com/scholar?hl=ru&as_sdt=0%2C5&q=wosjournals.com&btnG
https://www.researchgate.net/profile/Worldly-Knowledge
https://journalseeker.researchbib.com/view/issn/3030-332X
586
Ushbu algoritmlar orqali fazodagi obyektlarning o‘zaro aloqasi, chegaralanishi, harakat
yo‘nalishi va boshqa ko‘plab muhim parametrlar samarali aniqlanadi. Ayniqsa, ularning
algoritmik murakkabligi va vaqt tejamkorligi nuqtayi nazaridan tahlili muhim hisoblanadi.
Xulosa qilib aytganda, geometrik algoritmlar nafaqat nazariy informatika va matematika uchun,
balki amaliy dasturlash va texnologik yechimlar ishlab chiqish uchun ham katta ahamiyatga ega.
Ularni chuqur o‘rganish va rivojlantirish kelajakdagi ilmiy va texnik yutuqlar asosini tashkil
etadi
Foydalanilgan adabiyotlar:
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.
Introduction to Algorithms (3rd Edition), The MIT Press, 2009.
2. Knuth, D. E.
3. The Art of Computer Programming, Volume 1-4, Addison-Wesley, 1997.
4. Sedgewick, R., Wayne, K.
5. Algorithms (4th Edition), Addison-Wesley, 2011.
6. Baxtiyor Saidov, Temur G‘ulomov.
7. Algoritmlash va dasturlash asoslari, TATU nashriyoti, Toshkent, 2020.S. Obidov, M.
Qodirov.
8. Dasturlash asoslari va algoritmik tafakkur, TDYU nashriyoti, 2021.
9. Tim Roughgarden.
10. Algorithms Illuminated (Vol. 1–4), Soundlik LLC, 2018–2020.
11. Ullman, J. D., Hopcroft, J. E., Motwani, R.
12. Automata Theory, Languages and Computation, Pearson, 2006.
