Asignar puntos con radios variables a los lugares centrales de reunión

Question

Tengo un conjunto de puntos en una ciudad, cada uno con un radio de distancia máximo de 0,5 - 1,5 millas. A partir de este conjunto de puntos, me gustaría crear un pequeño número de "puntos de encuentro", es decir, ubicaciones que estén en el centro de un conjunto de puntos sin violar la restricción de <= distancia máxima raidus). Aquellos puntos alejados de los demás tendrán un punto de encuentro de 1.

Mi primer intento consistió en amortiguar cada punto y encontrar la intersección con el mayor número de solapamientos, pero resultó muy costoso desde el punto de vista computacional porque comparé cada nueva intersección con todas las demás intersecciones cercanas para determinar los puntos alcanzables dentro del área.

Mi segundo intento fue llenar cada búfer con posibles puntos de encuentro cada 100 metros y ejecutar un cálculo de la distancia en cada uno para determinar qué puntos podrían alcanzar, pero de nuevo, computacionalmente caro y propenso a perder casos de borde.

Ahora estoy pensando en crear un centroide de todos los puntos donde al menos 1 punto está dentro de radius(p1)+radius(p2) de todos los demás puntos, que funcionaría tal cual, si todos tuvieran el mismo radio. Como los radios varían, he pensado que podría ajustar el centroide acercándolo a la media de los puntos que no alcanza hasta que encaje o no.

¿Estoy complicando demasiado esto? Parece que debería haber una solución más elegante, pero no se me ocurre. Cualquier indicación en la dirección correcta sería muy bienvenida.

Answer 1

Para los futuros lectores, he resuelto esto utilizando mi segundo enfoque, creando una "red de pesca" modificada, como creo que se llama en términos de SIG. He optado por no utilizar topes e intersecciones debido a la explosión exponencial "n elige k" del número de intersecciones. Más de 32 puntos cercanos y podría colapsar un navegador.

Para cada punto, he calculado la distancia a todos los demás puntos. Si era menor que la suma de los 2 radios, la sumaba a un closePoint matriz. El coste: O(nlog(n)) usando la distancia equirectangular, que es SUPER barata, sólo 1 coseno y 1 sqrt.

Si el punto tenía al menos 1 closePoint En el caso de la distribución de semillas de girasol (proporción áurea), empecé a trazar puntos a su alrededor cada 200 metros. Costo O(n) con 2 sqrts.

Para cada "semilla" de girasol, calculé la distancia a los puntos de la closePoint matriz. Si la semilla alcanzó todos los puntos posibles, tengo una solución óptima y dejo de crear semillas para ese punto.

Para cada punto futuro, compruebo si su solución óptima ya ha sido creada y la omitimos si es así.

Con esa lista, elimino las intersecciones más cortas, dejándome con unos cuantos puntos que tienen un montón de intersecciones. Para los solapamientos restantes, asigné cada punto al primer punto de encuentro en el que aparece, aunque lo óptimo sería tratar esto como un problema de cobertura de conjuntos para reducir aún más el recuento.

Espero que ayude a alguien que se enfrente a este problema aparentemente común.