Pitteway Triangulation

În geometria de calcul , o triunghi Pitteway este o triangulație a unui set de puncte în care cel mai apropiat vecin al oricărui punct p din interiorul triangulației este unul dintre vârfurile triunghiului care conține p .

Istorie

Conceptul a fost introdus de Michael Pitteway în 1973 . McLain a menționat-o și în 1976. Denumirea „Pitteway triangulation” datează de la Okabe și colab., În 2000 .

Set de puncte fără triangulare Pitteway

Gold, în 1978 , a subliniat că nu toate seturile de puncte admit în mod necesar triangulația Pitteway. De exemplu, orice triunghi al unui pentagon regulat are un triunghi isoscel astfel încât un punct p lângă punctul mediu al unei laturi a triunghiului isoscel va fi mai aproape de un vârf în afara triunghiului decât de vârfurile triunghiului.

Relația cu alte grafice geometrice

Când există o triangulație Pitteway, punctul mediu al fiecărei muchii din interiorul triangulației trebuie să aibă cele două vârfuri ale marginii ca vecini apropiați, deoarece altfel proprietatea Pitteway ar fi încălcată pentru punctele din apropierea acelui punct mediu din l 'unul dintre cele două triunghiuri adiacente. Astfel, un cerc având ca diametru această margine nu trebuie să conțină un vârf, astfel încât triangulația Pitteway să corespundă graficului Gabriel mărit de învelișul convex al setului de puncte. În schimb, atunci când un grafic Gabriel și un plic convex formează o triangulație, este o triangulație Pitteway.

Deoarece graficul Gabriel și carena convexă sunt părți ale triangulației Delaunay , aceasta înseamnă că o triangulație Pitteway, atunci când există, este unică pentru un set de puncte în poziție generală și coincide cu triangulația Delaunay.

Într-o triangulație Pitteway, fiecare margine pq fie aparține învelișului convex, fie taie una dintre marginile diagramei Voronoi separând celulele care conțin punctele p și q , adică dualitatea triangulației. Pentru unele surse, această proprietate este utilizată pentru a defini o triangulație Pitteway ca o triangulație Delaunay în care toate muchiile interne își intersectează muchia duală în diagrama Voronoi. Este posibil ca marginile exterioare să nu-și intersecteze dualii.

Vezi și tu

Articole similare

• Triangularea unui set de puncte
• Graficul lui Gabriel
• Triangularea Delaunay

Referințe

1. MLV Pitteway, „Cercetare grafică computerizată într-un mediu academic”, Datafair '73, 1973
2. (în) DH McLain, „  Interpolare bidimensională din date aleatorii.  ” , The Computer Journal , vol.  19, n o  2Mai 1976, p.  178–181 ( DOI  10.1093 / comjnl / 19.2.178 )
3. Okabe, Atsuyuki; Ghete, Barry N.; Chiu, Sung Nok; Sugihara, Kokichi (2000), Teselări spațiale: concepte și aplicații ale diagramelor Voronoi , Wiley.
4. Gold, CM (1978), „ generarea practică și utilizarea structurilor de date ale elementelor triunghiulare geografice ”, în Dutton, G., Proceedings First International Advanced Study Symposium on Topological Data Structures for Geographic Information Systems. Harvard Papers on Geographic Information Systems , vol. 5 - Structuri de date: superficiale și multidimensionale., Boston: Laborator pentru grafică computerizată și analiză spațială, Universitatea Harvard, pp. 1-18.

Dobrin, Adam (2005), Review of Properties and Variations of Voronoi Diagrams , Whitman College