Otočné třmeny - Rotating calipers

Posloupnost sond kolem konvexního trupu mnohoúhelníku k určení jeho průměru pomocí metody Rotating Caliper.

v výpočetní geometrie, metoda rotační třmeny je návrh algoritmu technika, kterou lze použít k řešení optimalizačních problémů, včetně zjištění šířky nebo průměr množiny bodů.

Metoda je tak pojmenována, protože myšlenka je analogická otáčení pružinou posuvné měřítko noniem kolem vnějšku a konvexní mnohoúhelník.[1] Pokaždé, když jedna čepel třmenu leží naplocho proti okraji mnohoúhelníku, tvoří antipodální pár špičkou nebo hranou dotýkající se protilehlé čepele. Úplná „rotace“ třmenu kolem mnohoúhelníku detekuje všechny antipodální páry; množina všech párů, nahlížená jako graf, tvoří a thrackle. Metodu otáčení třmenů lze interpretovat jako projektivní duální a algoritmus zatáčkové čáry ve kterém je tažení spíše napříč svahy čar než napříč X- nebo y- souřadnice bodů.

Dějiny

An antipodální dvojice vrcholů a jejich podporující rovnoběžky.

Metoda rotujících třmenů byla poprvé použita při disertační práci Michael Shamos v roce 1978.[2] Shamos používá tuto metodu ke generování všech antipodální dvojice bodů na a konvexní mnohoúhelník a vypočítat průměr konvexního mnohoúhelníku v čas. Godfried Toussaint vytvořil frázi „rotující posuvná měřítka“ a také prokázal, že metoda byla použitelná při řešení mnoha dalších problémů s výpočetní geometrií.[3]

Rotující třmeny, nalezení mostu mezi dvěma konvexními polygony

Shamosův algoritmus

Shamos ve své disertační práci (str. 77–82) uvedl následující algoritmus pro metodu rotujících třmenů, který generoval všechny antipodální páry vrcholů na konvexním polygonu:[2]

/ * p [] je ve standardní formě, tj. proti směru hodinových ručiček,      odlišné vrcholy, žádné kolineární vrcholy.   ANGLE (m, n) je procedura, která vrací úhel ve směru hodinových ručiček      zametl paprskem, jak se otáčí z polohy rovnoběžné      do směrovaného segmentu Pm, Pm + 1 do polohy rovnoběžné s Pn, Pn + 1   Předpokládáme, že všechny indexy jsou redukovány na mod N (takže N + 1 = 1).*/GetAllAntiPodalPair(p[1..n])    // Najděte první antipodální pár umístěním vrcholu proti P1    i = 1    j = 2    zatímco úhel(i, j) < pi        j++    výtěžek i, j    / * Nyní pokračujte kolem mnohoúhelníku s přihlédnutím k         možná rovnoběžné hrany. Linka L prochází         Pi, Pi + 1 a M prochází Pj, Pj + 1    */    // Smyčka na j, dokud nebude naskenováno celé P    proud = i        zatímco j != n        -li úhel(proud, i + 1) <= úhel(proud, j + 1)            j++            proud = j        jiný            i++            proud = i        výtěžek i, j        // Nyní se postarejte o rovnoběžné hrany        -li úhel(proud, i + 1) = úhel(proud, j + 1)            výtěžek i + 1, j            výtěžek i, j + 1            výtěžek i + 1, j + 1            -li proud = i                j++            jiný                i++

Další verze tohoto algoritmu se objevila v textu Preparata a Shamos v roce 1985, která zabránila výpočtu úhlů:[4]

GetAllAntiPodalPair(p[1..n])    i0 = n    i = 1    j = i + 1    zatímco (Plocha(i, i + 1, j + 1) > Plocha(i, i + 1, j))        j = j + 1        j0 = j    zatímco (j != i0)        i = i + 1        výtěžek i, j        zatímco (Plocha(i, i + 1, j + 1) > Plocha(i, i + 1, j)            j = j + 1            -li ((i, j) != (j0, i0))                výtěžek i, j            jiný                 vrátit se        -li (Plocha(j, i + 1, j + 1) = Plocha(i, i + 1, j))            -li ((i, j) != (j0, i0))                výtěžek i, j + 1            jiný                 výtěžek i + 1, j

Aplikace

Pirzadeh[5] popisuje různé aplikace metody rotačních třmenů.

Vzdálenosti

  • Průměr (maximální šířka) konvexního mnohoúhelníku[6][7]
  • Šířka (minimální šířka ) konvexního mnohoúhelníku[8]
  • Maximální vzdálenost mezi dvěma konvexními polygony[9][10]
  • Minimální vzdálenost mezi dvěma konvexními polygony[11][12]
  • Nejširší prázdný (nebo oddělovací) pás mezi dvěma konvexními polygony (zjednodušená nízkodimenzionální varianta problému vznikajícího v podporovat vektorový stroj založené na strojovém učení)
  • Grenanderova vzdálenost mezi dvěma konvexními polygony[13]
  • Optimální oddělení pásu (používané v lékařském zobrazování a modelování těles)[14]

Ohraničující krabice

Triangulace

Multi-polygonové operace

  • Spojení dvou konvexních polygonů
  • Společné tangenty dvou konvexních mnohoúhelníků
  • Průnik dvou konvexních mnohoúhelníků[16]
  • Kritické linie podpory dvou konvexních polygonů
  • Vektorové součty (nebo Minkowského součet) dvou konvexních mnohoúhelníků[17]
  • Konvexní trup dvou konvexních mnohoúhelníků

Traversals

  • Nejkratší příčné[18][19]
  • Nejtenčí příčné příčky[20]

Ostatní

  • Neparametrická pravidla rozhodování pro strojově naučenou klasifikaci[21]
  • Optimalizace clonového úhlu pro problémy s viditelností v počítačovém vidění[22]
  • Nalezení nejdelších buněk v milionech biologických buněk[23]
  • Porovnání přesnosti dvou lidí na střelnici
  • Klasifikujte části mozku ze skenovaných obrázků

Viz také

Reference

  1. ^ „Rotující posuvná měřítka“ na domovské stránce Toussainta
  2. ^ A b Shamos, Michael (1978). „Výpočetní geometrie“ (PDF). Univerzita Yale. str. 76–81.
  3. ^ Toussaint, Godfried T. (1983). "Řešení geometrických problémů s rotujícími třmeny". Proc. MELECON '83, Atény. CiteSeerX  10.1.1.155.5671. Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ Shamos, Franco P. Preparata, Michael Ian (1985). Výpočetní geometrie Úvod. New York, NY: Springer New York. ISBN  978-1-4612-7010-2.
  5. ^ Pirzadeh, Hormoz (1999). "Výpočetní geometrie s rotujícími třmeny". McGillova knihovna.
  6. ^ Binay K. Bhattacharya a Godfried T. Toussaint, „Rychlé algoritmy pro výpočet průměru konečné plošné množiny“ Vizuální počítač, Sv. 3, č. 6, květen 1988, str. 379–388.
  7. ^ Binay K. Bhattacharya a Godfried T. Toussaint, „Protiklad k algoritmu průměru pro konvexní polygony,“ Transakce IEEE na analýze vzorů a strojové inteligenci, Sv. PAMI-4, č. 3, květen 1982, str. 306–309.
  8. ^ Michael E. Houle a Godfried T. Toussaint, „Výpočet šířky sady,“ Transakce IEEE na analýze vzorů a inteligenci strojů, Sv. 10, č. 5, září 1988, s. 761–765.
  9. ^ Godfried T. Toussaint a Jim A. McAlear, „Jednoduchý O (n log n) algoritmus pro zjištění maximální vzdálenosti mezi dvěma konečnými rovinnými množinami, “ Písmena pro rozpoznávání vzorů, Sv. 1, 1982, s. 21–24.
  10. ^ Binay K. Bhattacharya a Godfried T. Toussaint, „Efektivní algoritmy pro výpočet maximální vzdálenosti mezi dvěma konečnými rovinnými množinami,“ Journal of Algorithms, sv. 14, 1983, s. 121–136.
  11. ^ Godfried T. Toussaint a Binay K. Bhattacharya, „Optimální algoritmy pro výpočet minimální vzdálenosti mezi dvěma konečnými rovinnými množinami,“ Písmena pro rozpoznávání vzorů, sv. 2, prosinec 1983, s. 79–82.
  12. ^ „Rotující posuvná měřítka“. 2015-03-30. Archivovány od originálu na 2015-03-30. Citováno 2017-03-22.CS1 maint: BOT: stav původní adresy URL neznámý (odkaz)
  13. ^ MARTINEZ, HUGO M. (1. ledna 1978). „Recenze:„ PATTERN SYNTHESIS “, autor: U. Grenander, Springer-Verlag, New York, 1976. 509 stran“. International Journal of General Systems. 4 (2): 126–127. doi:10.1080/03081077808960672. ISSN  0308-1079.
  14. ^ Barequet a Wolfers (1998). "Optimalizace pásu oddělujícího dva polygony". Grafické modely a zpracování obrazu. 60 (3): 214–221. doi:10.1006 / gmip.1998.0470.
  15. ^ Teichmann, Marek (1989). „Problémy s optimalizací umístění klínu“. Citovat deník vyžaduje | deník = (Pomoc)
  16. ^ Godfried T. Toussaint, „Jednoduchý lineární algoritmus pro protínání konvexních polygonů, Vizuální počítač, Sv. 1, 1985, s. 118–123.
  17. ^ Tomas Lozano-Perez, „Prostorové plánování: Konfigurační prostorový přístup,“ Transakce IEEE na počítačích, Sv. 32, č. 2, 1983, s. 108–120.
  18. ^ Binay K. Bhattacharya a Godfried T. Toussaint, „Computing shortest transversals,“ Výpočetní, sv. 46, 1991, s. 93–119.
  19. ^ Binay K. Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried T. Toussaint a Jorje Urrutia, „Výpočet nejkratších průřezů množin,“ International Journal of Computational Geometry and Applications, Sv. 2, č. 4, prosinec 1992, s. 417–436.
  20. ^ Jean-Marc Robert a Godfried T. Toussaint, „Lineární aproximace jednoduchých objektů“ Výpočetní geometrie: Teorie a aplikace, Sv. 4, 1994, s. 27–52.
  21. ^ Rasson a Granville (1996). Msgstr "Geometrické nástroje v klasifikaci". Výpočetní statistika a analýza dat. 23 (1): 105–123. doi:10.1016 / S0167-9473 (96) 00024-2.
  22. ^ Bose, P .; Hurtado-Diaz, F .; Omaña-Pulido, E .; Snoeyink, J .; Toussaint, G. T. (01.08.2002). „Některé problémy s optimalizací clonového úhlu“. Algorithmica. 33 (4): 411–435. CiteSeerX  10.1.1.16.7118. doi:10.1007 / s00453-001-0112-9. ISSN  0178-4617.
  23. ^ „Nesprávné algoritmy průměru pro konvexní polygony“.