Problema punctului aparținând unui poligon

În calculul geometriei, este cunoscută problema stabilirii dacă un punct aparține unui poligon. Un poligon și un punct sunt date pe plan. Este necesară rezolvarea problemei apartenenței unui punct la un poligon.

Un poligon poate fi convex. și nu convex. Se presupune, de obicei, că poligonul este simplu, adică fără auto-intersecții, dar problema este, de asemenea, luată în considerare pentru poligoane non-simple. În acest din urmă caz, diferite moduri de a determina dacă un punct aparține unui poligon poate duce la rezultate diferite. Distingerea algoritmilor fără procesare preliminară și algoritmi cu procesare preliminară, în timpul căruia sunt create anumite structuri de date, permițând în viitor să răspundă mai repede la setul de cereri de apartenență a punctelor la același poligon.

Metoda Ray de urmărire [editați] edita wiki-text]

Contabilitatea numărului de intersecții [edit] edita wiki-text]

Metodele funcționează diferit pentru poligoane cu o limită de auto-intersecție. Stânga: regula par să fiu. Dreapta: regula de lichidare nonzero.

Una dintre metodele standard pentru a determina dacă un punct aparține unui poligon simplu arbitrar constă din următoarele. Am lăsat o rază dintr-un anumit punct într-o direcție arbitrară (de exemplu, în direcția pozitivă a axei orizontale) și numărăm de câte ori raza intersectează marginile poligonului. Pentru a face acest lucru, este suficient să mergeți prin buclă de-a lungul marginilor poligonului și să determinați dacă fiecare rază intersectează raza. Dacă numărul de intersecții este ciudat, atunci se declară că punctul se află în interiorul poligonului, dacă acesta este chiar în afara. Aceasta se bazează pe simpla observație că atunci când se deplasează de-a lungul unei raze cu fiecare intersecție a limitei, punctul se rotește alternativ în interiorul sau în afara poligonului. Algoritmul este cunoscut prin nume precum algoritmul de numărare (numărătoare) sau regula par ială.

Algoritmul Dificultatea apare în cazul degenerat, atunci când fasciculul traversează vârful poligonului. Una dintre tehnicile de a depăși este de presupus că aceste vârfuri ale poligonului se află deasupra infinitezimal (sau mai jos) fasciculul direct și, prin urmare, intersecția nu este de fapt. [1] Astfel, intersecția fasciculului cu muchia este luată în calcul atunci când unul dintre capetele nervurilor se află strict sub grinda, iar celălalt capăt - deasupra sau sprijină pe grinda.

Algoritmul funcționează în timp O (N) pentru N-gon.

Numărarea numărului de revoluții [edit] edita wiki-text]

Curba face două rotiri în jurul acestui punct.

Luați în considerare numărul de revoluții pe care linia de poligon orientată face în jurul unui anumit punct P. În topologia algebrică, acest număr se numește indicele unui punct relativ la o curbă. [2] Se poate calcula după cum urmează. Ca și înainte, eliberarea fasciculului P într-o direcție arbitrară și ia în considerare coaste, pe care le traversează. Fiecărei intersecții li se atribuie un număr de +1 sau -1, în funcție de modul în care raza traversează fasciculul - î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 între nervura de ghidare și vectorul normal la vectorul direcția fasciculului. [3] Suma cantităților obținute este indicele punctului relativ la curbă. Suma va fi pozitivă sau negativă, în funcție de orientarea frontierei. Dacă nu este egal cu zero, atunci vom presupune că punctul se află în interiorul poligonului, altfel - în afară.

Un astfel de algoritm este cunoscut ca regula non-winding. [3]

Pentru poligoane simple, această metodă funcționează în același mod ca o metodă bazată pe numărarea numărului de intersecții. Diferența dintre ele se manifestă atunci când luăm în considerare poligoane cu o limită de auto-intersectare.

Metoda de însumare a unghiurilor [edit] edita wiki-text]

Se poate determina că punctul P se află în interiorul poligonului cu vârfurile V0. V1. Vn = V0. calcularea sumei:

Se poate demonstra că această sumă nu este altceva decât un număr înfășurător al punctului P față de limita poligonului, până la un factor constant de 2 # x03C0; . Prin urmare, putem presupune că punctul se află în afara poligonului, în cazul în care suma este zero (sau destul de aproape de ea, în cazul în care se utilizează aritmetică aproximativă). Totuși, această metodă este foarte nepractic, deoarece necesită operații de calcul costisitoare pentru fiecare muchie (funcții trigonometrice inverse, rădăcini pătrate), și „cel mai rău în algoritmul mondial“ a fost numit chiar și pentru această sarcină. [1]

K. Weyler a propus o versiune practică a acestei metode care să evite operațiile costisitoare și calculele aproximative. [4] S-a arătat că suma unghiurilor poate fi calculată doar prin operația de clasificare a unui punct al unui poligon de-a lungul cadranilor în raport cu algoritmul punctului P. Weyler și unele îmbunătățiri ale acestuia sunt descrise în [5].

Algoritmi c preprocesare [edita] edita wiki-text]

Poligoane convexe și stele [edita] edita wiki-text]

Puncte accesorii pe -gon N convexe sau stelare pot fi determinate utilizând o căutare binară în timp O (log N), investiția O (N) și memorie O (N) timp pentru preprocesare. [6]

Poligon polarizator [edita] edita wiki-text]

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

Note [editați] edita wiki-text]

Literatură [editați] edita wiki-text]

• Pregătirea F. Sheimos M. Secțiunea 2.2: Probleme de localizare a punctelor. // Geometria computațională: introducere. - Moscova: Lumea, 1989.

Link-uri [edita] edita wiki-text]

Trimiteți-le prietenilor: