Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В геометрії множина K Rn буде ортогонально опуклою якщо для будь якої прямої L паралельної одному зі стандартних базисни

Ортогональна опукла оболонка

Ортогональна опукла оболонка

В геометрії, множина K ⊂ Rn буде ортогонально опуклою, якщо для будь-якої прямої L, паралельної одному зі стандартних базисних векторів Rn, перетин K з L буде або порожнім або точкою або відрізком. Термін «ортогональний» стосується відповідного декартового базису і координат в евклідовому просторі, де різні базисні вектори перпендикулярні, а також до відповідних прямих. На відміну від звичайних опуклих множин, ортогонально опукла оболонка не обов'язково буде зв'язною множиною.

image
Ортогональна опукла оболонка множини точок

Ортогональна опукла оболонка множини S ⊂ Rn є перетином всіх зв'язних ортогонально опуклих множин, що містять S.

Ці визначення зроблені за аналогією з класичною теорією опуклості, в якій множина K є опуклою, якщо для будь-якої прямої L, перетин К з L буде порожньою множиною, точкою, або сегментом (інтервалом). Ортогональна опуклість обмежує множину прямих, для яких ця властивість виконується. Таким чином, кожна опукла множина буде ортогонально опуклою але не навпаки. З тієї ж причини, ортогональна опукла оболонка сама є підмножиною опуклої оболонки того ж набору точок. Точка р належить ортогональній опуклій оболонці S тоді і тільки тоді, коли кожен із закритих, вирівняних по осях ортів, що містить р як вершину, має непорожній перетин з S.

Ортогональна опукла оболонка також знана як прямолінійна опукла оболонка, або, двовимірна х-у опукла оболонка.

Приклад

На малюнку показано набір з 16 точок на площині та їх ортогональна опукла оболонка. Як можна бачити на малюнку, ортогональна опукла оболонка являє собою багатокутник, який містить вироджені ребра, що з'єднують крайні вершини в кожному координатному напрямку. Для дискретної множини точок, такій як ця, усі ортогональні опуклі краї оболонки горизонтальні або вертикальні. У наведеному прикладі ортогональна опукла оболонка зв'язна.

Алгоритми

Наступні автори досліджували алгоритми побудови ортогональних опуклих оболонок: Montuno & Fournier (1982); Nicholl et al. (1983); Ottman, Soisalon-Soisinen & Wood (1984); Karlsson & Overmars (1988). У підсумку можна стверджувати, що ортогональна опукла оболонка K точок на площині може бути побудовано за час O(k log k), або, можливо, і швидше, якщо використовувати цілочисельні пошукові структури даних для точок з цілими координатами.

Пов'язані поняття

Природно узагальнити ортогональну опуклість, як обмежено орієнтовану опуклість, в якій множина K є опуклою, якщо кожна пряма, яка паралельна одному з кінцевого набору напрямків, перетинає K по зв'язній підмножині; див., наприклад Rawlins(1987 ), Rawlins та Wood (1987, 1988), або Fink та Wood (1996, 1998).

Крім того, метрична обгортка метричного простору тісно пов'язана з ортогональною опуклою оболонкою. Якщо скінченна множина точок на площині має зв'язну ортогонально опуклу оболонку, тоді оболонка буде метричною обгорткою для манхеттенської метрики на множині точок. Проте, ортогональна оболонка і метрична обгортка відрізняються у випадку множин точок з незв'язною ортогональною оболонкою, або в багатовимірних L р просторах.

O'Rourke (1993) описує дещо інші результати по ортогональній опуклості і ортогональній видимості.

Посилання

  1. Montuno, D. Y.; Fournier, A. (1982), Finding the x-y convex hull of a set of x-y polygons, Technical Report 148, University of Toronto.
  2. Nicholl, T. M.; ; Liao, Y. Z.; Wong, C. K. (1983), On the X-Y convex hull of a set of X-Y polygons, BIT, 23 (4): 456—471, doi:10.1007/BF01933620.
  3. Ottman, T.; Soisalon-Soisinen, E.; Wood, Derick (1984), On the definition and computation of rectilinear convex hulls, Information Sciences, 33 (3): 157—171, doi:10.1016/0020-0255(84)90025-2.
  4. Karlsson, Rolf G.; Overmars, Mark H. (1988), Scanline algorithms on a grid, BIT, 28 (2): 227—241, doi:10.1007/BF01934088.
  5. Rawlins, G. J. E. (1987), Explorations in Restricted-Orientation Geometry, Ph.D. thesis and Tech. Rep. CS-87-57, University of Waterloo.
  6. Rawlins, G. J. E.; Wood, Derick (1987), Optimal computation of finitely oriented convex hulls, Information and Computation, 72 (2): 150—166, doi:10.1016/0890-5401(87)90045-9.
  7. Rawlins, G. J. E.; Wood, Derick (1988), Ortho-convexity and its generalizations, у (ред.), Computational Morphology, Elsevier, с. 137—152
  8. Fink, Eugene; Wood, Derick (1996), (PDF), Information Sciences, 92 (1–4): 175—196, doi:10.1016/0020-0255(96)00056-4, архів оригіналу (PDF) за 24 вересня 2015, процитовано 29 квітня 2014.
  9. Fink, Eugene; Wood, Derick (1998), (PDF), Journal of Geometry, 62: 99—120, doi:10.1007/BF01237603, архів оригіналу (PDF) за 24 вересня 2015, процитовано 29 квітня 2014.
  10. (1993), Computational Geometry in C, Cambridge University Press, с. 107—109.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V geometriyi mnozhina K Rn bude ortogonalno opukloyu yaksho dlya bud yakoyi pryamoyi L paralelnoyi odnomu zi standartnih bazisnih vektoriv Rn peretin K z L bude abo porozhnim abo tochkoyu abo vidrizkom Termin ortogonalnij stosuyetsya vidpovidnogo dekartovogo bazisu i koordinat v evklidovomu prostori de rizni bazisni vektori perpendikulyarni a takozh do vidpovidnih pryamih Na vidminu vid zvichajnih opuklih mnozhin ortogonalno opukla obolonka ne obov yazkovo bude zv yaznoyu mnozhinoyu Ortogonalna opukla obolonka mnozhini tochok Ortogonalna opukla obolonka mnozhini S Rn ye peretinom vsih zv yaznih ortogonalno opuklih mnozhin sho mistyat S Ci viznachennya zrobleni za analogiyeyu z klasichnoyu teoriyeyu opuklosti v yakij mnozhina K ye opukloyu yaksho dlya bud yakoyi pryamoyi L peretin K z L bude porozhnoyu mnozhinoyu tochkoyu abo segmentom intervalom Ortogonalna opuklist obmezhuye mnozhinu pryamih dlya yakih cya vlastivist vikonuyetsya Takim chinom kozhna opukla mnozhina bude ortogonalno opukloyu ale ne navpaki Z tiyeyi zh prichini ortogonalna opukla obolonka sama ye pidmnozhinoyu opukloyi obolonki togo zh naboru tochok Tochka r nalezhit ortogonalnij opuklij obolonci S todi i tilki todi koli kozhen iz zakritih virivnyanih po osyah ortiv sho mistit r yak vershinu maye neporozhnij peretin z S Ortogonalna opukla obolonka takozh znana yak pryamolinijna opukla obolonka abo dvovimirna h u opukla obolonka PrikladNa malyunku pokazano nabir z 16 tochok na ploshini ta yih ortogonalna opukla obolonka Yak mozhna bachiti na malyunku ortogonalna opukla obolonka yavlyaye soboyu bagatokutnik yakij mistit virodzheni rebra sho z yednuyut krajni vershini v kozhnomu koordinatnomu napryamku Dlya diskretnoyi mnozhini tochok takij yak cya usi ortogonalni opukli krayi obolonki gorizontalni abo vertikalni U navedenomu prikladi ortogonalna opukla obolonka zv yazna AlgoritmiNastupni avtori doslidzhuvali algoritmi pobudovi ortogonalnih opuklih obolonok Montuno amp Fournier 1982 Nicholl et al 1983 Ottman Soisalon Soisinen amp Wood 1984 Karlsson amp Overmars 1988 U pidsumku mozhna stverdzhuvati sho ortogonalna opukla obolonka K tochok na ploshini mozhe buti pobudovano za chas O k log k abo mozhlivo i shvidshe yaksho vikoristovuvati cilochiselni poshukovi strukturi danih dlya tochok z cilimi koordinatami Pov yazani ponyattyaPrirodno uzagalniti ortogonalnu opuklist yak obmezheno oriyentovanu opuklist v yakij mnozhina K ye opukloyu yaksho kozhna pryama yaka paralelna odnomu z kincevogo naboru napryamkiv peretinaye K po zv yaznij pidmnozhini div napriklad Rawlins 1987 Rawlins ta Wood 1987 1988 abo Fink ta Wood 1996 1998 Krim togo metrichna obgortka metrichnogo prostoru tisno pov yazana z ortogonalnoyu opukloyu obolonkoyu Yaksho skinchenna mnozhina tochok na ploshini maye zv yaznu ortogonalno opuklu obolonku todi obolonka bude metrichnoyu obgortkoyu dlya manhettenskoyi metriki na mnozhini tochok Prote ortogonalna obolonka i metrichna obgortka vidriznyayutsya u vipadku mnozhin tochok z nezv yaznoyu ortogonalnoyu obolonkoyu abo v bagatovimirnih L r prostorah O Rourke 1993 opisuye desho inshi rezultati po ortogonalnij opuklosti i ortogonalnij vidimosti PosilannyaMontuno D Y Fournier A 1982 Finding the x y convex hull of a set of x y polygons Technical Report 148 University of Toronto Nicholl T M Liao Y Z Wong C K 1983 On the X Y convex hull of a set of X Y polygons BIT 23 4 456 471 doi 10 1007 BF01933620 Ottman T Soisalon Soisinen E Wood Derick 1984 On the definition and computation of rectilinear convex hulls Information Sciences 33 3 157 171 doi 10 1016 0020 0255 84 90025 2 Karlsson Rolf G Overmars Mark H 1988 Scanline algorithms on a grid BIT 28 2 227 241 doi 10 1007 BF01934088 Rawlins G J E 1987 Explorations in Restricted Orientation Geometry Ph D thesis and Tech Rep CS 87 57 University of Waterloo Rawlins G J E Wood Derick 1987 Optimal computation of finitely oriented convex hulls Information and Computation 72 2 150 166 doi 10 1016 0890 5401 87 90045 9 Rawlins G J E Wood Derick 1988 Ortho convexity and its generalizations u red Computational Morphology Elsevier s 137 152 Fink Eugene Wood Derick 1996 PDF Information Sciences 92 1 4 175 196 doi 10 1016 0020 0255 96 00056 4 arhiv originalu PDF za 24 veresnya 2015 procitovano 29 kvitnya 2014 Fink Eugene Wood Derick 1998 PDF Journal of Geometry 62 99 120 doi 10 1007 BF01237603 arhiv originalu PDF za 24 veresnya 2015 procitovano 29 kvitnya 2014 1993 Computational Geometry in C Cambridge University Press s 107 109

Дата публікації:
Топ