Poligon monoton
În geometrie un poligon P din plan este numit monoton față de dreapta L, dacă orice dreaptă ortogonală cu L intersectează frontiera lui P de cel mult două ori.[1] Similar, un lanț poligonal C este numit monoton față de dreapta L, dacă orice dreaptă ortogonală cu L intersectează C cel mult o dată.
Pentru multe scopuri practice, această definiție poate fi extinsă pentru a permite și cazurile în care unele laturi ale lui P sunt ortogonale cu L, adică un poligon simplu poate fi numit monoton dacă un segment care conectează două puncte din P și este ortogonal cu L aparține complet lui P.
Folosind terminologia de la funcție monotonă, prima definiție descrie poligoane strict monotone față de L. Expresia „față de” este necesară pentru a face deosebirea dintre strict/nestrict: un poligon nestrict monoton față de L este strict monoton față de o dreaptă L1 rotită față de L cu un unghi suficient de mic.
Proprietăți modificare
Să presupunem că L coincide cu axa x. Atunci vârfurile din extrema stângă și extrema dreaptă ale unui poligon monoton descompun frontiera în două lanțuri poligonale monotone, astfel încât, atunci când vârfurile oricăruia din cele două lanțuri sunt parcurse în ordinea lor naturală, coordonatele lor X cresc sau scad monoton. De fapt, această proprietate poate fi luată pentru definiția poligonului monoton și îi dă numele poligonului.
Un poligon convex este monoton în raport cu orice dreaptă, iar un poligon care este monoton în raport cu orice dreaptă este convex.
Există un algoritm în timp liniar care stabilește toate direcțiile în care un anumit poligon simplu este monoton.[2] Algoritmul a fost generalizat să stabilească toate modurile în care poate fi descompus un poligon simplu în două lanțuri monotone (posibil monotone în direcții diferite).[3]
Interogările punctelor din poligon cu privire la un poligon monoton pot primi răspuns în timp logaritmic după o preprocesare în timp liniar (pentru a găsi vârfurile din stânga și din dreapta).[1]
Un poligon monoton poate fi ușor triangulat în timp liniar.[4]
Un poligon simplu poate fi ușor împărțit în poligoane monotone în timp O(n log n). Totuși, deoarece un triunghi este un poligon monoton, triangularea poligonului este de fapt împărțirea unui poligon în poligoane monotone și poate fi efectuată pentru poligoane simple în timp liniar O(n).
Împărțirea unui poligon simplu în numărul minim de poligoane uniform monotone (adică monotone față de aceeași dreaptă) poate fi efectuată în timp polinomial.[5]
Note modificare
- ^ a b en Preparata, Franco P.; Shamos, Michael Ian (), Computational Geometry – An Introduction
, Springer-Verlag, ISBN 0-387-96131-3, 1st edition: ; 2nd printing, corrected and expanded, 1988: ; Russian translation, 1989
- ^ Preparata, Franco P.; Supowit, Kenneth J. (), „Testing a simple polygon for monotonicity”, Information Processing Letters, 12 (4): 161–164, doi:10.1016/0020-0190(81)90091-0
- ^ en Rappaport, David; Rosenbloom, Arnold (), „Moldable and castable polygons”, Computational Geometry, 4 (4): 219–233, doi:10.1016/0925-7721(94)90020-5
- ^ en Fournier, Alain; Montuno, D. Y. (), „Triangulating simple polygons and equivalent problems”, ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301
- ^ en Liu, Robin (), „On decomposing polygons into uniformly monotone parts”, Information Processing Letters, 27 (2): 85–89, doi:10.1016/0020-0190(88)90097-X.
