32 votos

Algoritmo para cubrir el máximo número de puntos con un círculo de radio dado.

Imaginemos que tenemos un plano con algunos puntos en ella. También tenemos un círculo de radio dado.

Necesito un algoritmo que determina la posición del círculo que cubra el máximo número posible de puntos. Por supuesto, hay muchas de esas posiciones, de manera que el algoritmo debe devolver uno de ellos.
La precisión no es importante y el algoritmo puede hacer pequeños errores.

Aquí está un ejemplo de una foto:
Example

Entrada:
  int n (n<=50) – número de puntos;
  float x[n] y float y[n] – matrices con puntos de coordenadas X e y;
  float r – radio del círculo.

Salida:
  float cx y float cy – las coordenadas del centro del círculo

La velocidad de un rayo del algoritmo no es necesario, pero no debe ser demasiado lento (porque conozco a un par de lentos soluciones para esta situación).

El código de C++ es mejor, pero no es obligatorio.

17voto

Alexandre C. Puntos 31758

Editado para una mejor redacción, como se sugiere :

Observaciones básicas :

  • Supongo que la radio es uno, ya que no cambia nada.
  • dados dos puntos cualesquiera, existe en la mayoría de los dos círculos de unidad en la que se encuentran.
  • dada una solución círculo a su problema, puede moverse hasta que se contiene a dos puntos de su conjunto, manteniendo el mismo número de puntos de su conjunto en su interior.

El algoritmo es entonces:

  • Para cada par de puntos, si su distancia es de < 2, calcular los dos círculos de unidad C1 y C2 que pasar a través de ellos.
  • Calcular el número de puntos de su conjunto en el interior de C1 y C2
  • Tomar el max.

6voto

Joel Puntos 3899

Este es el "disco parcial que cubre problema" en la literatura-que debe dar un buen lugar para empezar a buscar en google. He aquí un papel que cubre una posible solución, pero es un poco intenso matemáticamente: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

Como cuestión de hecho, esta cae en la zona denominada geometría computacional, que es fascinante, pero puede ser difícil obtener un punto de apoyo. Hay una buena vista general del deBerg en diversos algoritmos relacionados con el tema.

5voto

doc Puntos 2294

Si quieres algo simple, tomar posición aleatoria (x,y), calcular el número de puntos dentro del círculo, y compararla con la posición anterior. Aprovechar al máximo. Repetir la operación todas las veces que desee.

Por qué el infierno downvote? Nunca ha oído hablar de métodos de Monte Carlo? En realidad para una gran cantidad de puntos, algoritmo determinista no puede terminar en un tiempo razonable.

2voto

Mau Puntos 6480

El problema vuelve a encontrar el mundial óptimo de una función f :R x R -> N. La entrada de f es el punto central del círculo, y el valor, por supuesto, es el número de puntos del conjunto. La gráfica de la función será discontinua, la escalera de acceso.

Usted podría empezar con las pruebas de la función en cada punto correspondiente a un punto en el conjunto, orden de los puntos de la disminución de los valores de f, entonces intensificar la búsqueda en torno a esos puntos (por ejemplo mover a cabo a lo largo de una espiral).

Otra opción es considerar todos los puntos de intersección de los segmentos de la conexión de cualquier pares de puntos en el juego. Su óptimo punto será en una de estas intersecciones creo, pero su número es probablemente demasiado grande para tener en cuenta.

Usted también puede hibridar las opciones 1 y 2, y considerar las intersecciones de los segmentos generados a partir de los puntos alrededor de la 'buen conjunto de puntos.

De todos modos, a menos que el número de puntos de ajuste es bajo (lo que te permite controlar todas las intersecciones), yo no creo que pueda garantizar a encontrar el óptimo (sólo una buena solución).

1voto

user389609 Puntos 11

A primera vista, yo diría que un quad árbol de solución.

También, hay una visualización de información de minería de Datos y método llamado K-means que hace que los clústeres de datos determinado. Puede ser utilizado con mayor funcionalidad en el final para adaptarse a su propósito.

El algoritmo básico para K-means es:

  1. Lugar K puntos en el espacio representado por los elementos que se están agrupadas Estos puntos representan el grupo inicial de los centroides de
  2. Asignar a cada elemento de datos en el grupo que más centroide
  3. Cuando todos los elementos han sido asignados, volver a calcular el las posiciones de los K centroides por el cálculo de la media de la posición de sus puntos
  4. Repita los Pasos 2 y 3 hasta que los centroides ya no se mueven o se mueven muy poco

La funcionalidad añadida sería:

  1. Calcular el número de puntos dentro de su círculo colocado en la K centroides
  2. Elija el que se adapte a usted el mejor ;)

Fuentes:
K-means el algoritmo - Universidad de Linköping
Quadtree - en.wikipedia.org/wiki/Quadtree

Una búsqueda rápida en wikipedia y te encuentras con el código fuente: en.wikipedia.org/wiki/K-means_clustering

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X