Tengo una serie de puntos, que representan móviles.Dispositivos dentro de una habitación. Anteriormente, he emitido sistemáticamente un ping de cada uno y registrado el momento en que llega a los demás para calcular las distancias.
Aquí hay un diagrama simple de una red de ejemplo.
El nodo inferior A debería haber sido una D en su lugar
Después de registrar las distancias tengo la información de la distancia en hashes.
A = {B: 2, C: 1, D: 3}
B = {A: 2, C: 2, D: 2}
C = {A: 1, B: 2, D: 2}
D = {A: 3, B: 2, C: 2}
Mi matemática está oxidada, pero siento que debería poder dibujar círculos usando estos valores como los respectivos y luego intersectar los círculos para calcular una gráfica relativa de los nodos.
Cada vez que trato de hacerlo, comienzo con una serie de círculos dibujados alrededor del nodo raíz (en este caso A) que se parece a esto:
Sé que los otros nodos deben estar en las líneas.que he dibujado alrededor de A, pero sin poder posicionarlos, ¿cómo dibujas sus distancias para que puedas intersectar los círculos y crear la gráfica?
Respuestas
7 para la respuesta № 1Comience con cualquier punto, diga A. Ahora tome el segundo punto, diga B, y trace una gráfica en algún lugar del círculo con el centro en A y el radio como distancia entre A y B. Ahora tome otro punto C. Deja la distancia (A,C)=x y (B,C)=y. Encuentra el punto de intersección de los círculos. (A,x) y (B,y). Marcarlo como C.
donde circulo (P,q) especifica el centro en P y radio q.
Si no existe tal punto, entonces los datos dados son incorrectos.
Ahora toma el 4th punto y de forma similar encontrar el punto deIntersección de círculos con centros en los primeros tres puntos y radios como distancia entre el cuarto y otros tres puntos respectivamente. Aplica este método hasta que todos los puntos estén trazados.
Tenga en cuenta que puede haber infinitas soluciones como señaló RobH. Como solo necesita una representación virtual, supongo que cualquiera de las soluciones válidas es suficiente.
El algoritmo anterior tiene un orden de O(N^2). Puede ser ineficiente si el número de puntos es mayor que 10000.
También tenga en cuenta que, para encontrar el punto de intersección de k círculos, primero debe encontrar el punto de intersección de cualquiera de los dos círculos y validar estos puntos en los círculos restantes. Esto es porque k Los círculos pueden, como máximo, intersectarse en dos puntos, suponiendo que todos tengan centros distintos.
EDITAR: En cualquier etapa, si hay dos gráficos válidos para un punto, podemos elegir cualquiera de ellos y, sin embargo, llegamos a una de las soluciones válidas.