Estoy tratando de implementar una versión más simple de este algoritmo, pero que funciona mejor que el algoritmo cuadrático. Mi idea básicamente es ordenar los puntos solo por coordenadas x e intentar resolverlos desde allí. Una vez que ordeno mi matriz de puntos por coordenadas x, quiero iterar sobre la matriz y, básicamente, omitir los puntos cuya distancia es mayor que los dos primeros puntos que tomé.Más cercano par de algoritmo de puntos
Por ejemplo, my currentminDist = x;
Si los dos pares de puntos que estoy viendo tienen distancia> x (solo por su x coord dist), ignoro el punto y lo paso en la matriz.
Tengo la idea, pero estoy algo atrapado en cómo implementar esto (especialmente la parte de la condición). Tengo una función que me devuelve la distancia entre dos puntos en función de su coordenada x.
Estoy confundido sobre cómo escribir mis condiciones para mi ciclo ya que quiero ignorar un punto si la distancia está demasiado lejos y aún así completar mi matriz que contendrá las respuestas para los puntos más cercanos para cada i (siendo el punto actual que estoy viendo).
Cualquier sugerencia o dirección sería muy apreciada. No conozco muy bien los algoritmos de codificación, así que es bastante frustrante.
aquí es parte de mi código:
for (i = 0; i < numofmypoints; i++)
{
for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++)
{
currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
}
distbyX es mi función que sólo devuelve la distancia entre dos puntos.
Gracias!
@ Pablo: Qué se necesita para hacer esto a menudo? ¿No almacenaría sus puntos en una ayuda "quadtree"? http://en.wikipedia.org/wiki/Quadtree – TacticalCoder
Tenga en cuenta que puede obtener un mejor rendimiento que con el algoritmo ingenuo, pero igual será 'O (n^2)'. – ARRG
¿Por qué hay 'currbest' y' bestdist' en tu código? ¿Cuál es la diferencia? – Ishtar