Ex 2 lista 5

Ex 2 lista 5

por Alexandre Albano -
Número de respostas: 16
não to conseguindo fazer o exercício 2 da lista 5
realmente só se tem um vetor com os pontos de P ordenados por Y-coordenada?

seria muito útil se eu tivesse dois vetores ordenados, digamos v_e , v_d, sendo que v_e contém os pontos da cadeia esquerda ordenados por Y-coordenada, e v_d contém os pontos da cadeia direita ordenados por Y-coordenada ..

Help ? pensativo
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Cristina Gomes Fernandes -
De fato, seria mais fácil se você tivesse v_e e v_d. Mas, já que não tem, vamos tentar nos virar sem eles?

Leia com atenção o que você tem no exercício. Você tem o P, que é o vetor dos vértices do polígono em ordem anti-horária, começando de um vértice arbitrário do polígono, e você tem adicionalmente o vetor v. De posse de P e v, acho que você pode sim viver sem o v_e e o v_d, ainda que de um jeito mais complicado (ou melhor, menos direto).

Espero ter ajudado.

Cris
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
Eu acho que se não existirem dois pontos de P com mesma Y-coordenada, ou seja, se o polígono for estritamente monótono, temos primeiro que encontrar o índice do vértice do polígono que está logo acima do ponto q, e o índice do vértice do polígono que está logo abaixo do ponto q, usando busca binária.
(Talvez seja necessário tratar os casos em que
q.y > P[v[0]].y ou q.y < P[v[n-1]].y separadamente.)

Para isso basta encontrar um índice i tal que
P[v[i]].y >= q.y && P[v[i+1]].y <= q.y ,
e teremos dois índices a e b, onde a = v[i] e b = v[i+1].

Após isso, considerando que o polígono P está representado no sentido
anti-horário, e que temos os índices a e b encontrados acima, basta verificar se q está à esquerda das 4 seguintes arestas de P:
(P[a-1], P[a]) , (P[a], P[a+1]), (P[b-1], P[b]), (P[b], P[b+1]).

Se o ponto q estiver à direita de uma das arestas, então q não pertence ao polígono, caso contrário, q pertence ao polígono.


Funciona?
Em resposta à Atol Fortin de Oliveira

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
hummm... acho que fazendo uma modificação na verificação final, dá para adaptar o que eu tinha feito antes.

Primeiro, acho que quando |a-b| > 1, então os vértices não são adjacentes em P,
e então, se o ponto q estiver a esquerda de pelo menos 3 das 4 arestas citadas anteriormente, então q pertence ao polígono.

Senão, se |a-b| == 1, então podemos fazer uma outra busca binária para encontrar
o primeiro vértice que pertence à curva poligonal oposta que está acima do vértice P[b] (talvez tenha que tratar um caso especial quando a == v[0]).

Sobrescrevendo o valor de a, fazemos a = nova_busca(0,n-1,P[b].y, sinal),
onde sinal vale 1 quando P[a].y > P[b].y, e -1 caso contrário.

nova_busca(ini , fim, yy, sinal ) {
int meio = (ini+fim) / 2;
se (P[v[meio]].y < yy) devolva nova_busca(ini, meio-1, yy);
senão se (P[ v[meio] + 1*sinal].y > yy) devolva nova_busca(meio+1,fim,yy);
devolva v[meio];
}

Parece melhor?
Em resposta à Atol Fortin de Oliveira

Re: Ex 2 lista 5

por Alexandre Albano -
e pra esse polígono e esse q ? funciona?
(pelo que entendi cai no caso |a-b| > 1)


Anexo ex5.png
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
Bom, esse polígono não é y-monótono.

Mas mesmo assim, acho que tem que seperar em alguns casos após achar os vértices P[a] e P[b] do polígono. Sabemos que P[a] e P[b] estão em curva poligonais opostas (exceto pelos casos em que um deles é o ponto mais acima ou mais abaixo do polígono, mas também dá pra tratar esses casos). Além disso, se P[a] está acima de q, então P[b] está abaixo de q, e vice versa. Também vale que se P[a] está acima/abaixo de q, então não existe nenhum vértice de P que está acima/abaixo de q com Y-coordenada menor/maior que a de P[a], na curva poligonal de P[a]. O mesmo vale para P[b]. (Acredito que isso seja realmente verdadeiro, pela maneira que foram encontrados os vértices P[a] e P[b]).

Os casos que eu pensei que devem ser tratados são:
1 - P[a] e P[b] são vértices reflexo.
2 - P[a] e P[b] não são vértice reflexo.
3 - P[a] ou P[b] são vértices reflexo.

Considerando as 4 arestas incidentes nos vértices P[a] e P[b], temos:

No caso 1, acho que se q estiver a esquerda de pelo menos 2 das 4 arestas,
sendo uma delas incidente em P[a], e outra incidente em P[b], q pertence ao polígono.

No caso 2, acho que se q estiver a esquerda de todas as 4 arestas, q pertence ao polígono.

No caso 3, acho que se q estiver a esquerda de pelo menos uma aresta incidente no vértice reflexo, e q estiver a esquerda das duas arestas do vértice não reflexo, entao q pertence ao polígono.

Não sei se compliquei demais o problema, e também não tenho certeza se funciona, principalmente a verificação final.
Em resposta à Atol Fortin de Oliveira

Re: Ex 2 lista 5

por Alexandre Albano -
Qdo vc diz que eles estão em cadeias (acho que é cadeias e nao curvas) poligonais opostas vc está considerando o subcaso de a e b nao adjacentes né ? (|a-b| > 1)


Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
Sim, se na primeira busca binária já encontramos dois vértices que estão em cadeias poligonais opostas, já dá pra tentar "encurralar" o ponto q. Senão, deve ser feita uma segunda busca binária para encontrar um vértice "bom" que está na outra cadeia poligonal, e sempre teremos |a-b| > 1. (exceto nos casos especiais quando o vértice P[a] é o vértice com maior y-coordenada, ou quando P[b] é o vértice com menos y-coordenada. Nesses casos, podemos ignorar a segunda busca binária e partir direto para as verificações de esquerda)
Em resposta à Atol Fortin de Oliveira

Re: Ex 2 lista 5

por Alexandre Albano -
entendi. Legal sorriso
Testei o caso 3 aqui do encurralamento e me pareceu funcionar!

Mas, casos a parte, como seria essa segunda busca binária, e como eu sei que vou achar um vértice bom sem comprometer a promessa de O(lgn) do processo todo?
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
Eu coloquei um pseudo-código da "nova_busca". Se os dois vértices mais próximos do ponto q estiverem na cadeia poligonal da direita, por exemplo, temos que encontrar um vértice que esteja na cadeia poligonal da esquerda.

Então, no lugar de pegarmos o vértice P[a] inicial, queremos um P[a'] que esteja acima de P[a], e também queremos que o vizinho dele no polígono original esteja abaixo de P[b]. Ou seja, P[a'].y > P[a].y, e P[a' + 1].y <= P[b].y (esse "+1" funciona neste caso, pois o polígono é dado no sentido anti-horário. Se P[a] e P[b] estam na cadeira poligonal da direita, entao deve ser "-1"). Aí dá pra aplicar a nova busca binária para encontrar esse vértice P[a'].
Em resposta à Atol Fortin de Oliveira

Re: Ex 2 lista 5

por Murilo Santos de Lima -
Você não precisa testar cada caso assim, basta ver que as retas y = y_a e y = y_b formam junto com P um trapézio, então basta testar esquerda/direita para as duas arestas do trapézio que estão no polígono.
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Alexandre Albano -
Ops.
O polígono de cima (edição: o primeiro polígono) não é y-monotono nem aqui nem na China
o certo é esse


Anexo ex5.png
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Atol Fortin de Oliveira -
Nesse caso a primeira busca binária encontra P[a] = v0 e P[b] = v2, que não são adjacentes.

No outro post eu tentei corrigir as verificações finais para decidir se q pertence ou não a P. Essas últimas alterações parecem dar certo para esse caso.
Em resposta à Alexandre Albano

Re: Ex 2 lista 5

por Alvaro Junio Pereira Franco -
Pessoal, lembrem do que a Cris falou. É dado $P$ que possui os vértices do polígono no sentido anti-horário. Com $P$ e com $v$ não dá pra obter $v_e$ e $v_d$, sem construí-los?
Em resposta à Alvaro Junio Pereira Franco

Re: Ex 2 lista 5

por Alexandre Albano -
Ah !
como v contém os índices dos vértices ordenados..

ficou fácil

divida em 2 subproblemas: (aqui, P e v indexados de 1 ate n)

P[v[1]] ... P[v[n]] é o subproblema da cadeia a esquerda
P[v[n]+1] ... P[n] é o subproblema da cadeia a direita

cada um dos dois subproblemas é resolvido c/ busca binária, e encontramos dois pares de vértices, cada par em uma cadeia, que ensanduicham a Y-coordenada de q sorriso