Problema dacă un punct aparține unui poligon

În geometria computațională, problema determinării dacă un punct aparține unui poligon este cunoscută . Un poligon și un punct sunt date într-un plan . Este necesar să se rezolve întrebarea dacă un punct aparține unui poligon.

Un poligon poate fi fie convex , fie neconvex. De obicei se presupune că poligonul este simplu, adică fără auto-intersecții; dar problema este luată în considerare și pentru poligoane non-simple. În acest din urmă caz, diferite moduri de a determina dacă un punct aparține unui poligon pot duce la rezultate diferite. Există algoritmi fără preprocesare; și algoritmi cu preprocesare, în timpul cărora sunt create unele structuri de date care le permit să răspundă mai rapid la multe întrebări despre dacă puncte diferite aparțin aceluiași poligon.

Metoda de urmărire a razei

Contabilizarea numărului de intersecții

Una dintre metodele standard pentru a determina dacă un punct aparține unui poligon simplu arbitrar este următoarea. Să tragem o rază dintr-un punct dat într-o direcție arbitrară (de exemplu, în direcția pozitivă a axei orizontale) și să numărăm de câte ori raza traversează marginile poligonului. Pentru a face acest lucru, este suficient să treceți prin marginile poligonului și să determinați dacă raza intersectează fiecare margine. Dacă numărul de intersecții este impar, atunci se declară că punctul se află în interiorul poligonului, dacă este par, atunci în exterior. Aceasta se bazează pe observația simplă că atunci când se deplasează de-a lungul razei, cu fiecare trecere a graniței, punctul se găsește alternativ în interiorul și în afara poligonului. Algoritmul este cunoscut sub denumiri precum algoritmul numărului de încrucișare (număr) sau regula par-impar .

Algoritmul are o dificultate în cazul degenerat când raza intersectează vârful poligonului. O modalitate de a o depăși este să presupunem că astfel de vârfuri de poligoane se află o cantitate infinitezimală deasupra (sau sub) liniei drepte a razei și, prin urmare, nu există de fapt nicio intersecție. [1] Astfel, intersecția unei raze cu o muchie este socotită dacă unul dintre capete ale muchiei se află strict sub rază, iar celălalt capăt este deasupra sau se află pe rază.

Algoritmul rulează în timp O( N ) pentru un N - gon.

Contabilizarea numărului de rotații

Se consideră numărul de rotații pe care limita orientată a poligonului le face în jurul unui punct dat P . În topologia algebrică, acest număr se numește indicele punctului în raport cu curba . [2] Poate fi calculat după cum urmează. Ca și înainte, să tragem o rază din P într-o direcție arbitrară și să luăm în considerare marginile pe care le intersectează. Atribuim un număr de +1 sau -1 fiecărei intersecții, în funcție de modul în care marginea intersectează raza - în sensul acelor de ceasornic (de la stânga la dreapta) sau în sens invers acelor de ceasornic (de la dreapta la stânga). Aceste două cazuri pot fi distinse prin semnul produsului scalar dintre vectorul direcției marginii și normala vectorului direcției razei. [3] Suma valorilor obținute este indicele punctului relativ la curbă . Suma va fi pozitivă sau negativă, în funcție de orientarea graniței. Dacă nu este egal cu zero, atunci vom presupune că punctul se află în interiorul poligonului, în caz contrar - în exterior.

Un astfel de algoritm este cunoscut sub numele de regula de înfășurare diferită de zero . [3]

Pentru poligoane simple, această metodă funcționează în același mod ca metoda bazată pe numărarea numărului de intersecții. Diferența dintre ele devine evidentă atunci când se consideră poligoane cu o limită care se intersectează.

Metoda sumei unghiurilor

Se poate determina că punctul P se află în interiorul unui poligon cu vârfurile V 0 , V 1 , ..., V n = V 0 prin calculul sumei:

unde  este unghiul (în radiani și cu semn) dintre razele PV i − 1 și PV i , adică:

Se poate demonstra că această sumă nu este altceva decât numărul de înfășurare al punctului P față de limita poligonului, până la un factor constant . Prin urmare, putem presupune că punctul se află în afara poligonului dacă suma este egală cu zero (sau suficient de aproape de acesta, dacă se utilizează aritmetica aproximativă). Cu toate acestea, această metodă este foarte nepractică, deoarece necesită calcularea operațiilor costisitoare pentru fiecare muchie (funcții trigonometrice inverse, rădăcini pătrate) și chiar a fost numită „cel mai prost algoritm din lume” pentru această problemă [1] .

K. Weiler a propus o versiune practică a acestei metode, evitând operațiile costisitoare și calculele aproximative. [4] S-a arătat că suma unghiurilor poate fi calculată folosind doar operația de clasificare a unui punct poligon în cadrane în raport cu punctul P . Algoritmul lui Weiler și unele îmbunătățiri ale acestuia sunt descrise în [5] .

Algoritmi cu preprocesare

Poligoane convexe și stelare

Dacă un punct aparține unui N - gon convex sau stea poate fi determinat folosind căutarea binară în timp O(log N ), memorie O( N ) și timp de preprocesare O( N ). [6]

Poligon arbitrar

Problema dacă un punct aparține unui poligon simplu arbitrar poate fi considerată ca un caz special al problemei de localizare a unui punct într-o subdiviziune plană. Pentru un N -gon, această problemă poate fi rezolvată în timp O(log 2 N ) folosind memoria O( N ) și timpul de preprocesare O( N log N ) . [7]

Note

  1. ↑ 1 2 Eric Haines. Point in Polygon Strategies Arhivat pe 25 septembrie 2011 la Wayback Machine
  2. ↑ Poate fi tradus în rusă ca „indice de curbă relativ la un punct”, „număr de torsiune”, „număr de înfășurare”, „număr șurub” și altele asemenea.
  3. ↑ 1 2 Foley JD, et al. Grafică pe computer: principii și practică. Addison Wesley. 1990. P. 965.
  4. ↑ K. Weiler. An incremental angle point in polygon test, în: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. Problema punctului în poligon pentru poligoane arbitrare   // Calcul . Geom. Theory Appl.. - 2001. - Vol. 20 . - P. 131-144 .
  6. ↑ Preparata, Sheimos. Pagină 60-61.
  7. ↑ Preparata, Sheimos. Pagină 74. Teorema 2.6.

Literatură

Link -uri