Jump to content

Visibilidade máxima num polígono


fran.aubry
 Share

Recommended Posts

Resolver o problema com o "segmento emissor" é semelhante a resolver o problema com um "raio".

Consideras um intervalo, que inicialmente começa [y1-1, y1] e um vector director, (x1, y1) -> (x2, y2), constante. Pode dar jeito obter só o declive da recta, mas não li o problema com o detalhe suficiente para perceber se pode ser infinito (depende se os pontos podem estar em qualquer localização ou se os X se podem repetir). Vou assumir que não, mas tanto o declive como o vector normalizado servem.

Tendo este intervalo inicial e o vector, vais intersectar o intervalo com o intervalo [y2-1, y2], após projectar o intervalo [y1-1, y1] x2-x1 unidades segundo o vector. A intersecção dos dois intervalo é o novo intervalo que deves considerar.

Repetes este procedimento para todos os pares de pontos, até que a intersecção falhe. Quando falhar, necessitas de calcular o X máximo, sabendo os segmentos que queres considerar. É um problema de intersecção de rectas.

Costumas participar em concursos de programação?

Edit: a projecção não é bem x2-x1 unidades segundo o vector, isso dava a distância errada. Se fizeres o desenho facilmente percebes ao que me estou a referir.

Link to comment
Share on other sites

Sim. Faço parte da equipa javastrip. Ainda não entandi bem o que explicaste mas vou ainda ver melhor. É que pelo que percebi, como a altura do intervalo 2 é a mesma que a do 1 então a intersecção é o segundo intervalo todo, ou então estou a perceber mal.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.