Diagramas de Voronoi .


24 views
Uploaded on:
Description
Diagramas de Voronoi. Clasificación de objetos (reconocedor de voz). Clasificación de objetos (reconocedor de voz). Dado un conjunto de n puntos S y un nuevo punto q, encontrar el punto de S más cercano a q. Región de Voronoi. ¿Cómo calcular la región de Voronoi de un punto?.
Transcripts
Slide 1

Diagramas de Voronoi

Slide 3

Clasificación de objetos (reconocedor de voz)

Slide 4

Clasificación de objetos (reconocedor de voz) Dado un conjunto de n puntos S y un nuevo punto q, encontrar el punto de S más cercano a q.

Slide 5

Región de Voronoi ¿Cómo calcular la región de Voronoi de un punto? La región de Voronoi del punto rojo es el lugar geométrico de los puntos que están más cerca del punto rojo que de los puntos azules. P = {p1,...,pn} a cada pj le asociamos aquellos puntos del plano que están más cerca o igual suya que de cualquier otro de los pi con i distinto de j.

Slide 6

¿Cómo calcular la región de Voronoi de un punto? La región de Voronoi del punto rojo es el lugar geométrico de los puntos que están más cerca del punto rojo que de los puntos azules.

Slide 7

¿Cómo calcular la región de Voronoi de un punto? Los puntos que están en la región de Voronoi del punto rojo, deben estar más cerca de él que del punto amarillo ¿Cuáles child los puntos más cercanos al rojo que al amarillo?

Slide 8

¿Cómo calcular la región de Voronoi de un punto? Los puntos que están en la región de Voronoi del punto rojo, deben estar más cerca de él que del punto amarillo y del marrón

Slide 9

¿Cómo calcular la región de Voronoi de un punto? Los puntos del plano pertenecientes a h(pi,pj) child aquellos que están más próximos a pi que a pj. Lema: La intersección de los semiplanos h(p1,pj) es Vor(p1). Corolario: Vor(p1) es un convexo .

Slide 10

¿Cómo calcular la región de Voronoi de un punto? Los puntos del plano pertenecientes a h(pi,pj) child aquellos que están más próximos a pi que a pj. Lema: La intersección de los semiplanos h(p1,pj) es Vor(p1). Corolario: Vor(p1) es un convexo .

Slide 11

vértices aristas Diagrama de Voronoi Lema: La intersección de los semiplanos h(p1,pj) es Vor(p1). Teorema: La intersección de N semiplanos se puede calcular en tiempo óptimo O(N log N) . Corolario: Vor(p1) se puede calcular en tiempo óptimo O(N log N). Corolario: El diagrama de Voronoi de una nube de N puntos se puede calcular en tiempo óptimo O(N 2 log N).

Slide 12

Dado un punto q llamaremos círculo máximo vacío al chairman círculo centrado en q que no contiene a ningún generador del diagrama en su inside. La bisectriz entre dos generadores characterize un borde de Vor(P) si y sólo si existe un punto q sobre dicha bisectriz tal que el círculo máximo vacío centrado en q contiene solamente an estos dos generadores en su frontera. Un punto q es vértice de Vor(P) si y sólo si el círculo máximo vacío centrado en q contiene tres o (en el caso de tratarse de un diagrama degenerado) más generadores en su frontera

Slide 13

¿Cómo calcular el diagrama de Voronoi de S?

Slide 14

¿Cómo calcular el diagrama de Voronoi de S?

Slide 15

¿Cómo calcular el diagrama de Voronoi de S?

Slide 16

¿Cómo calcular el diagrama de Voronoi de S?

Slide 17

¿Cómo calcular el diagrama de Voronoi de S?

Slide 18

¿Cómo calcular el diagrama de Voronoi de S? Paradigma de isolate y vencerás Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 19

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 20

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 21

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 22

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 23

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 24

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S). ¿cómo?

Slide 25

¿Cómo calcular el diagrama de Voronoi de S? Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S).

Slide 26

Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S). ¿Cómo calcular el diagrama de Voronoi de S? Lema: Si dos subconjuntos están separados por una línea vertical (S1 a la izquierda y S2 a la derecha), existe una línea poligonal monótona creciente c tal que todo punto q situado a la izquierda (derecha) de dicha poligonal está en la región de Voronoi de un punto de S1 (S2).

Slide 27

Dividir S en dos subconjuntos S1 y S2 de aproximadamente el mismo tamaño. Calcular recursivamente Vor(S1) y Vor(S2). Unir la información obtenida en 2 para obtener Vor(S). ¿Cómo calcular el diagrama de Voronoi de S? ¿cómo? Calcular la poligonal c. Eliminar las líneas de Vor(S1) (Vor(S2)) a la derecha (izquierda) de c Lema: Si dos subconjuntos están separados por una línea vertical (S1 a la izquierda y S2 a la derecha), existe una línea poligonal monótona creciente c tal que todo punto q situado a la izquierda (derecha) de dicha poligonal está en la región de Voronoi de un punto de S1 (S2).

Slide 28

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c.

Slide 29

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. Se encuentra un punto muy alto sobre la línea divisoria.

Slide 30

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. q p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto.

Slide 31

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. q p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q

Slide 32

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. q p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3.

Slide 33

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. q p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3.

Slide 34

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3. q

Slide 35

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. p Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3. q

Slide 36

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3. q p

Slide 37

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. Se encuentra un punto muy alto sobre la línea divisoria. Se determina en la región de qué punto p de S1 y en la región de qué punto q de S2 está el punto. Mientras esté en la región de p y en la región de q , calcular la mediatriz entre p y q Si toco an una línea de verde , actualizar el punto q, si toco una línea marrón actualizar p . Volver a 3. q p

Slide 38

¿Cómo calcular el diagrama de Voronoi de S? Calcular la poligonal c. Se encuentra un punto muy alto sobre la línea divisoria. Se determina en

Recommended
View more...