Autor Tema: Distancias en espacio 3D

0 Usuarios y 1 Visitante están viendo este tema.

07 Julio, 2014, 09:46 am
Leído 1959 veces

HarryBananas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola,
imaginaros que tenemos 6 puntos en el espacio(3 dimensiones) p1, p2, p3, p4, p5, p6
Cada punto se se situa de forma aleatoria en el espacio
y queremos que al final la distancia entre los puntos sea:
p1-p2 6
p1-p3 9
p1-p4 5
p1-p5 12
p1-p6 3
p2-p3 1
p2-p4 7
p2-p5 8
p2-p6 9
p3-p4 3
p3-p5 7
p3-p6 8
p4-p5 1
p4-p6 6
p5-p6 2

¿Como lo hariais? La solución no debe ser exacta, se busca una aproximación tras varias iteraciones y mejor si es paralela(se mueven todos los puntos tras cada iteración).

Mi idea es que se muevan todos los puntos tras cada iteración y poco a poco vayan acercandose hasta un margen de error determinado, pero aún no tengo claro que formula usar.

Saludos.

07 Julio, 2014, 11:56 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas del mismo así como el tutorial del LaTeX para escribir las fórmulas matemáticas correctamente.

imaginaros que tenemos 6 puntos en el espacio(3 dimensiones) p1, p2, p3, p4, p5, p6
Cada punto se se situa de forma aleatoria en el espacio
y queremos que al final la distancia entre los puntos sea:
p1-p2 6
p1-p3 9
p1-p4 5
p1-p5 12
p1-p6 3
p2-p3 1
p2-p4 7
p2-p5 8
p2-p6 9
p3-p4 3
p3-p5 7
p3-p6 8
p4-p5 1
p4-p6 6
p5-p6 2

¿Como lo hariais? La solución no debe ser exacta, se busca una aproximación tras varias iteraciones y mejor si es paralela(se mueven todos los puntos tras cada iteración).

Mi idea es que se muevan todos los puntos tras cada iteración y poco a poco vayan acercandose hasta un margen de error determinado, pero aún no tengo claro que formula usar.

 Antes de nada, tienes demasiados datos, es decir, si tienes seis puntos e impones las distancias entre cada par de ellos, lo más probable es que no sea posible una configuración de ese tipo.

 Para que entiendas lo que quiero decir, si fijas cuatro de ellos tenemos un tetraedro. Ahora para un quinto punto fijada la distancia a tres de los puntos iniciales, estará en la intersección de tres esferas que será (salvo casos muy particulares) a lo sumo cuatro puntos. Por tanto la distancia al cuarto punto del tetraedro ya no puede ser cualquierta.

 En tu caso, por ejemplo las distancias:

\( d(p_1,p_4)=5,\quad d(p_4,p_5)=1,\quad d(p_1,p_5)=12 \)

no son compatibles, porque debería de cumplirse que:

\( d(p_1,p_5)\leq d(p_1,p_4)+d(p_4,p_5) \)

Saludos.

07 Julio, 2014, 12:15 pm
Respuesta #2

HarryBananas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola,
   ante todo muchas gracias por molestarte en responderme.
   Soy consciente de que las distancias no son compatibles y por eso intento buscar una solución iterativa (hay infinitas soluciones) con un margen de error en las distancias que sea el mínimo posible.
   
   He cogido un ejemplo sencillo para intentar explicar el caso correctamente, pero en el caso real se usan más de 100 puntos, tal vez esto no tenga ni solución aproximada.
Saludos y gracias.

07 Julio, 2014, 01:45 pm
Respuesta #3

Fallen Angel

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 340
  • Karma: +0/-0
  • Sexo: Masculino
Hola!

A ver si puedo ayudarte, si quieres encontrar \( n \) puntos que "minimicen el error" lo que tienes es un problema de optimización.

LLamemos a los puntos buscados \( \{p_{i}=(x_{1}^{i},x_{2}^{i},x_{3}^{i}) \in \mathbb {R}^{3} \ : \ 1\leq i \leq n\} \)

Y llamemos \( d_{i,j}=d(p_{i},p_{j}) \) (La que tu quieres imponer si está en las condiciones)

Tu problema entonces es minimizar la función \( f(\vec{x})=\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n} |(x_{1}^{i}-x_{1}^{j})^2+(x_{2}^{i}-x_{2}^{j})^2+(x_{3}^{i}-x_{3}^{j})^2-d_{i,j}| \)
(Por supuesto en la formula no apareceran aquellos términos para los que no se tenga condición si los hubiese, pero no quería incluir demasiada notación)

El problema es que esta función no es diferenciable, parece ser subdiferenciable (así a ojo) así que lo que haría sería calcular el subgradiente e igualar a 0

Un saludo!
La Geometría es el arte de pensar bien, y dibujar mal.- H.Poincaré

07 Julio, 2014, 04:04 pm
Respuesta #4

HarryBananas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola Fallen Angel,
    muchas gracias por tu respuesta, creo que has dado en el clavo.
    Ahora buscaré información sobre el metodo subgradiente e intentaré aplicarlo con esta formula y un algoritmo paralelo a ver si resuelve mi problema.
    De todas formas creo que no me he explicado bien el principio, esta fórmula que has puesto creo que calcula las distancias finales y a mi lo que me interesa es como calcular los sucesivos desplazamientos de los puntos. Osea, las coordenadas finales de cada punto.
Saludos y gracias.

07 Julio, 2014, 05:53 pm
Respuesta #5

Fallen Angel

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 340
  • Karma: +0/-0
  • Sexo: Masculino
De este modo si tienes un mínimo en que se anula el subgradiente ta da los puntos en que se minimiza la función.


Fíjate que \( f:\mathbb{R}^{\color{red}3n}\color{black} \longrightarrow \mathbb{R} \) tiene como argumentos las coordenadas ordenadas de tus \( n \) puntos.


Un saludo!
La Geometría es el arte de pensar bien, y dibujar mal.- H.Poincaré