Mnohoúhelník ve tvaru hvězdy - Star-shaped polygon

Pro další použití viz Jádro (geometrie).
Nesmí být zaměňována s Hvězda mnohoúhelník.
Mnohoúhelník ve tvaru hvězdy (nahoře). Jeho jádro je v dolní části zobrazeno červeně.

A hvězdicovitý mnohoúhelník je polygonální oblast v rovině, která je a hvězdičková doména, tj. mnohoúhelník, který obsahuje bod, od kterého je celá hranice mnohoúhelníku viditelné.

Formálně polygon P je ve tvaru hvězdy, pokud existuje bod z tak, že pro každý bod p z P segmentu zp leží zcela uvnitř P.[1] Sada všech bodů z s touto vlastností (tj. množinou bodů, ze kterých všechny P je viditelný) se nazývá jádro z P.

Pokud je mnohoúhelník ve tvaru hvězdy konvexní, vzdálenost odkazu mezi libovolnými dvěma jeho body (minimální počet sekvenčních úseček dostatečný k propojení těchto bodů) je 1, a tak je průměr polygonu (maximální vzdálenost mezi všemi páry bodů) 1. Pokud je polygon ve tvaru hvězdy není konvexní, vzdálenost spojení mezi bodem v jádře a jakýmkoli jiným bodem v polygonu je 1, zatímco vzdálenost mezi dvěma body, které jsou v polygonu, ale mimo jádro, jsou buď 1 nebo 2; v tomto případě je maximální vzdálenost odkazu 2.

Příklady

Konvexní mnohoúhelníky jsou ve tvaru hvězdy a konvexní polygon se shoduje s jeho vlastním jádrem.

Pravidelný hvězdné polygony jsou ve tvaru hvězdy a jejich střed je vždy v jádře.

Antiparalelogramy a protínají se Lemoine šestiúhelníky jsou ve tvaru hvězdy, přičemž jádro tvoří jediný bod.

Polygony viditelnosti jsou ve tvaru hvězdy, protože každý bod v nich musí být podle definice viditelný pro střed.

Algoritmy

Testování, zda má mnohoúhelník tvar hvězdy, a nalezení jediného bodu v jádře, lze vyřešit v lineární čas formulací problému jako lineární program a použití technik pro nízkodimenzionální lineární programování (viz http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, strana 16).

Každá hrana mnohoúhelníku definuje interiér polorovina, polorovina, jejíž hranice leží na přímce obsahující hranu a která obsahuje body mnohoúhelníku v a sousedství jakéhokoli vnitřního bodu hrany. Jádro mnohoúhelníku je průsečík všech jeho vnitřních polorovin. Průsečík libovolné množiny N poloroviny lze nalézt v Θ (N log N) čas pomocí rozděl a panuj přístup.[1] U jader polygonů je však možná rychlejší metoda: Lee & Preparata (1979)[2] představil algoritmus pro konstrukci jádra v lineárním čase.

Viz také

Reference

  1. ^ A b Franco P. Preparata a Michael Ian Shamos (1985). Výpočetní geometrie - úvod. Springer-Verlag. 1. vydání: ISBN  0-387-96131-3; 2. tisk, opraveno a rozšířeno, 1988: ISBN  3-540-96131-3.
  2. ^ Lee, D. T.; Preparata, F. P. (Červenec 1979), „Optimální algoritmus pro nalezení jádra polygonu“, Deník ACM, 26 (3): 415–421, doi:10.1145/322139.322142, hdl:2142/74090