Ponto em polígono

Um exemplo de um simples polígono

Em geometria computacional, o problema ponto em polígono (PIP) pergunta se um dado ponto no plano repousa dentro, fora ou na borda do polígono. É um caso especial de problemas de localização de pontos e encontra aplicações em áreas que lidam com o processamento de dados geométricos, tais como computação gráfica, visão computacional e sistemas de informação geográfica (SIG) e CAD.

Uma descrição precoce do problema em computação gráfica mostra duas abordagens comuns (ray casting e o soma de ângulo) em uso no começo de 1974.[1]

Uma tentativa de gráficos de computador veteranos para rastrear o histórico do problema e alguns truques para a sua solução pode ser encontrada em um problema do Ray Tracing News.[2]

Referências

  1. Ivan Sutherland et al.,"A Characterization of Ten Hidden-Surface Algorithms" 1974, ACM Computing Surveys vol. 6 no. 1.
  2. "Point in Polygon, One More Time...", Ray Tracing News, vol. 3 no. 4, October 1, 1990.