Encontrei alguns probleminhas no algoritmo dos slides.
No caso 3, se só há um trapézio contendo v, claramente v é vizinho de x, logo não deveria adicionar diagonal (nesse caso o algoritmo produz uma saída errada).
No caso 1, acho que também não precisa adicionar a diagonal pois, se x é ponta para baixo, pelo caso 2 alguma diagonal para cima contendo x foi adicionada anteriormente, logo x não atrapalha mais o subpolígono contendo v de ser y-monótono.
Murilo
Em resposta à Murilo Santos de Lima
Re: algoritmo de partição em monótonos
por Murilo Santos de Lima -
Esquece o segundo item, agora vi que tava confundindo ponta pra cima e ponta pra baixo.
eu acho que pode acontecer isso:
(obs: o segmento vx esta no poligono, isto e', o vértice v é convexo)
obs2: nesse caso, j = v e l = v também.
Mas eu to achando uma (outra) coisa estranha no caso 3 .... pra mim a linha 4 não faz sentido, a segunda verificação (k != v) não faz sentido pra mim... pra mim faria sentido verificar l != v ....
(obs: o segmento vx esta no poligono, isto e', o vértice v é convexo)
obs2: nesse caso, j = v e l = v também.
Mas eu to achando uma (outra) coisa estranha no caso 3 .... pra mim a linha 4 não faz sentido, a segunda verificação (k != v) não faz sentido pra mim... pra mim faria sentido verificar l != v ....
Bem lembrado... Descobri agora que a dúvida nesse caso também é fruto da minha confusão: como x é ponta para baixo, nunca pode ser vizinho de v, já que os vizinhos de v estão acima dele.
Esse problema do k != v eu também tinha visto, mas nem dei muita atenção.
Esse problema do k != v eu também tinha visto, mas nem dei muita atenção.