Como faço para determinar se uma série de pontos (ou polígono) está dentro de uma região retangular?

Question

Eu tenho visto os posts sobre determinar se um ponto está dentro de um polígono ou não e as respostas são muito vagas, abstratas ou complexas para mim. Então eu vou tentar fazer a minha pergunta específica do que preciso fazer.

Eu tenho um conjunto de pontos que descrevem uma linha não reta (às vezes um polígono fechado). Eu tenho uma região de "visão" retangular. Eu preciso determinar de forma tão eficiente possível se qualquer um dos segmentos de linha (ou fronteiras de polígono) passa pela região de visualização.

Eu não posso simplesmente testar cada ponto para ver se está dentro da região de exibição. É possível que um segmento passe pela região sem qualquer ponto na verdade dentro da região (ou seja, a linha é desenhada através da região).

Aqui está um exemplo do que quero determinar (vermelho significa que a função deve retornar true para o conjunto de pontos, azul significa que deve retornar false, exemplo usa linhas retas e retângulos porque eu não sou um artista). .

Outra condição que eu quero ser capaz de explicar (embora o método / função possa ser um separado), é determinar não apenas se a fronteira de um polígono passa pela região retangular, mas se a região é inteiramente abrangida pelo polígono. A nuance aqui é que na situação descrita pela primeira vez, se eu estiver preocupado apenas com fronteiras de desenho, o método deve retornar falso. Mas na situação descrita aqui, se eu precisar preencher a região do polígono , então eu preciso da função para retornar TRUE. Atualmente não preciso me preocupar em testar polígonos em forma de "donut" (graças a Deus!).

Aqui está um exemplo que ilustra a nuance (o retângulo vermelho não tem um único vertex ou segmento de borda passando pela região na tela, mas ainda deve ser considerado na tela):

Para o "qualquer segmento de linha ou fronteira de polígono passa ou deita na tela?" Problema Eu sei que posso inventar uma solução (embora talvez não seja eficiente). Mesmo que seja mais detalhado, as condições são claras para mim. Mas a segunda "é a região do polígono na tela?" O problema é um pouco mais difícil. Eu espero que alguém possa ter uma boa sugestão para fazer isso. E se uma solução for facilmente implementada em cima do outro, bem, booya.

Como sempre, obrigado antecipadamente por qualquer ajuda ou sugestões.

ps Eu tenho uma função para determinar a interseção de linha, mas parece um exagero para usá-lo para comparar cada segmento para cada lado da região na tela, porque a região na tela é sempre uma planície [0, 0, largura , altura] retângulo. Não há algum tipo de corte curto?

Answer 1

.

ps eu tenho uma função para determinar interseção de linha, mas parece Overkill para usá-lo para comparar cada segmento para cada lado da tela na tela região porque a região na tela é Sempre uma planície [0, 0, largura, altura] retângulo.Não há algum tipo de Corte de curta?

Não é um exagero, é necessário aqui.O único tipo de atalho Eu posso pensar é para valores de códigos de acesso [0, 0, largura, altura] nessa função e simplificá-lo um pouco.

Answer 2

O que você está procurando é nomeado um algoritmo de detecção de colisão Uma pesquisa no Google te levarápara muitas implementações em vários idiomas, bem como muita teoria

Há uma abundância de teoria geométrica para trás, desde o mais simples cálculo do bissector a triangulações de Delaunay restritas e diagramas Voronoi (que são apenas exemplos).Depende da forma do objeto, do número de dimensões e com certeza a relação entre exatidão necessária e o tempo de computação oferecida; -)

Bom leitura