Punt al polígon

De Viquipèdia
Salta a la navegació Salta a la cerca
Un exemple de polígon simple

En geometria computacional, el problema del punt al polígon (PIP, de point-in-polygon) demana si un punt donat roman a dins, a fora, o als límits d'un polígon. És un cas especial dels problemes de localització de punts i té aplicacions en les àrees que tracten el processament de dades geomètriques, com ara la infografia, la visió artificial, els sistemes d'informació geogràfica (SIG), la planificació de moviment i el disseny assistit per ordinador.

Una descripció primerenca del problema en gràfics computacionals mostra dos enfocaments comuns (traçament de raigs i suma d'angles) que s'empraven ja el 1974.[1]

Un intent dels entesos en gràfics computacionals per trobar la història del problema i alguns trucs per resoldre'l es pot trobar en un exemplar de Ray Tracing News.[2]

Referències[modifica]

  1. Sutherland, Ivan «A Characterization of Ten Hidden-Surface Algorithms». ACM Computing Surveys, vol. 6, núm. 1, 1974.
  2. «Point in Polygon, One More Time...». Ray Tracing News, vol. 3, núm. 4, 01-10-1990.