Editar: el algoritmo de clasificación rápida en realidad no funciona ... 😳
SITUACIÓN
Tengo una cadena de línea con hasta 2000 puntos. Estoy tratando de encontrar el punto más cercano en la línea desde la ubicación del usuario. Esta operación se ejecuta aproximadamente cada 5 segundos y, si no se optimiza, se agotará innecesariamente la batería de los usuarios.
El código fuente muestra que la operación de distance se realiza en cada punto de la cadena de líneas, lo que no es bueno para mis usuarios.
Me gustaría implementar un algoritmo de estilo de clasificación rápida para obtener el punto más cercano y reducir el número de operaciones. El siguiente ejemplo funciona bastante bien y produce un punto en la línea con muchas menos operaciones (para una lista de 1700 puntos, se necesitan 14 operaciones para ubicar el punto más cercano).
PROBLEMA
No puedo determinar una forma elegante de rastrear el índice del resultado. Una vez que tengo el punto más cercano, no quiero tener que buscar de nuevo en la lista original para encontrar su índice.
primera operación - 0 | mediana
segundo - fHalf (0 | mediana de fHalf) | sHalf (mediana de la lista | mediana de sHalf)
tercero: en este punto se vuelve un desastre rastrear
Lo que tengo hasta ahora:
import distance from "@turf/distance"; import { point } from "@turf/helpers"; const user = point([-77.037076, 38.884017]); function getMedian(list) { return Math.ceil(list.length / 2); } function getHalves(list) { const median = getMedian(list); const firstHalf = list.slice(0, median); const secondHalf = list.slice(-median); return { firstHalf, secondHalf }; } function getClosest(list) { const to = point(list[0]); const meters = distance(user, to, { units: "meters" }); return meters; } let operations = 0; // used in development to track operations function selectHalf(list) { operations += 1; const { firstHalf, secondHalf } = getHalves(list); const firstDistance = getClosest(firstHalf); const secondDistance = getClosest(secondHalf); const nextList = firstDistance < secondDistance ? firstHalf : secondHalf; if (list.length === 1) console.log("operations:", operations, "closest point:", nextList); else selectHalf(nextList); } const morePoints = `-37.0467378013181,145.1634433308106 -37.04674949407303,145.1634394751351 -37.04676521014147,145.1634369605642 -37.04678021374815,145.1634352003645 -37.04679207414114,145.1634343621742 -37.04680510800057,145.1634334401648 // Full list is available in the codesandbox link below ` .split("\n") .map((p) => p.split(",").map((n) => parseFloat(n))); selectHalf(morePoints);