c++ - solicitar - Algoritmo para cubrir el número máximo de puntos con un círculo de radio dado
saldo de puntos dgt (10)
Imaginemos que tenemos un avión con algunos puntos. También tenemos un círculo de radio dado.
Necesito un algoritmo que determine la posición del círculo que cubre la mayor cantidad posible de puntos. Por supuesto, hay muchas posiciones, por lo que el algoritmo debería devolver una de ellas.
La precisión no es importante y el algoritmo puede cometer pequeños errores.
Aquí hay una imagen de ejemplo:
Entrada:
int n (n <= 50) - número de puntos;
float x[n] y float y[n] - matrices con coordenadas X e Y de puntos;
float r - radio del círculo.
Salida:
float cx y float cy - coordenadas del centro del círculo
La velocidad del algoritmo no es necesaria, pero no debe ser demasiado lenta (porque conozco algunas soluciones lentas para esta situación).
Se prefiere el código C ++, pero no es obligatorio.
¿Puedo sugerir un mapa de densidad? Encuentra los límites mínimo y máximo para el x y el y. Divida el rango de los límites xey en compartimientos que tengan anchos iguales al diámetro de su círculo. Cuente el número de puntos en cada contenedor para la xey por separado. Ahora encuentre la intersección en su mapa de densidad entre el bin más alto de x con el bin más alto y clasificado.
Este es un algoritmo MUY rápido para generalizar rápidamente grandes conjuntos de datos, pero no siempre es preciso; para mejorar la precisión, puede dividir los contenedores en piezas cada vez más pequeñas o cambiar las posiciones del contenedor a la izquierda o derecha y usar un sistema de votación para seleccione la respuesta que ocurre más a menudo entre los ensayos.
A primera vista, diría una solución quad tree.
Además, hay un método de visualización de información / minería de datos llamado K-means que crea grupos de datos dados. Se puede usar con funcionalidad adicional al final para adaptarse a su propósito.
El algoritmo básico para K-Means es:
- Coloque puntos K en el espacio representado por los elementos que se agrupan. Estos puntos representan los centroides iniciales del grupo.
- Asignar cada elemento de datos al grupo que tiene el centroide más cercano
- Cuando se hayan asignado todos los elementos, vuelva a calcular las posiciones de los centroides K calculando la posición media de los puntos
- Repita los pasos 2 y 3 hasta que los centroides ya no se muevan o mueva muy poco
La funcionalidad agregada sería entonces:
- Calcule la cantidad de puntos dentro de su círculo posicionados en los centroides K
- Elija el que más le convenga;)
Fuentes:
Algoritmo K-means - Universidad de Linköping
Quadtree - en.wikipedia.org/wiki/Quadtree
Una búsqueda rápida en wikipedia y usted encuentra el código fuente: en.wikipedia.org/wiki/K-means_clustering
Aquí hay dos ideas: un algoritmo de aproximación O (n) y un algoritmo O (n ^ 2 log n) exacto (no aproximado):
Aproximación rápida
Usa hashing sensible a las localidades. Básicamente, hash cada punto a un cubo de hash que contiene todos los puntos cercanos. Los cubos están configurados de modo que las colisiones solo sucedan entre puntos cercanos; a diferencia de las tablas hash de nombre similar, las colisiones son útiles aquí. Mantenga una cuenta corriente de la cantidad de colisiones en una cubeta, y luego use el centro de esa cubeta como el centro de su círculo.
Admito que esta es una explicación rápida de un concepto que no es muy obvio la primera vez que lo escuchas. Una analogía sería preguntar a mucha gente cuál es su código postal y usar el código postal más común para determinar el círculo más poblado. No es perfecto, pero es una buena heurística rápida.
Básicamente es tiempo lineal en términos de cantidad de puntos, y puede actualizar su conjunto de datos sobre la marcha para obtener incrementalmente nuevas respuestas en tiempo constante por punto (constante con respecto a n = número de puntos).
Más sobre los hashes sensibles a la localidad en general o sobre mi versión favorita personal que funcionaría en este caso .
Enfoque determinista de la fuerza mejor que la fuerza bruta
La idea es: para cada punto, coloque el borde de un círculo en ese punto y barra el círculo para ver qué dirección contiene la mayor cantidad de puntos. Haga esto para todos los puntos y encontramos el máximo global.
El barrido alrededor de un punto p se puede hacer en n log n tiempo al: (a) encontrar el intervalo de ángulo por otro punto q de manera que cuando colocamos el círculo en el ángulo theta, entonces contiene q; y (b) ordenando los intervalos para que podamos marchar / barrer alrededor de p en tiempo lineal.
Entonces, toma el tiempo O (n log n) para encontrar el mejor círculo que toca un punto fijo p, y luego lo multiplica por O (n) para realizar la verificación de todos los puntos. El tiempo total es O (n ^ 2 log n).
Editado para una mejor redacción, como se sugiere:
Observaciones básicas:
- Supongo que el radio es uno, ya que no cambia nada.
- dados dos puntos, existen como mucho dos círculos de unidades en los que se encuentran.
- dado un círculo de solución a su problema, puede moverlo hasta que contenga dos puntos de su conjunto mientras mantiene la misma cantidad de puntos dentro de su conjunto.
El algoritmo es entonces:
- Para cada par de puntos, si su distancia es <2, calcule los dos círculos unitarios C1 y C2 que pasan a través de ellos.
- Calcule el número de puntos de su conjunto dentro de C1 y C2
- Toma el máximo.
El problema vuelve a encontrar el óptimo global de una función f :R x R -> N La entrada para f es el punto central del círculo, y el valor, por supuesto, es la cantidad de puntos incluidos en el conjunto. El gráfico de la función será discontinuo, similar a una escalera.
Puede comenzar probando la función en cada punto correspondiente a un punto en el conjunto, ordenar los puntos disminuyendo los valores de f , luego intensificar la búsqueda alrededor de esos puntos (por ejemplo, moverse a lo largo de una espiral).
Otra opción es considerar todos los puntos de intersección de los segmentos que conectan cualquier par de puntos en el conjunto. Creo que su punto óptimo será en una de estas intersecciones, pero probablemente su número sea demasiado grande como para considerarlo.
También puede hibridar las opciones 1 y 2, y considerar las intersecciones de los segmentos generados a partir de puntos alrededor de "buenos puntos de ajuste".
De todos modos, a menos que el número de puntos de ajuste sea bajo (lo que le permite verificar todas las intersecciones), no creo que pueda garantizar el encontrar el óptimo (solo una buena solución).
Este es el "problema de cobertura parcial del disco" en la literatura, que debería darle un buen lugar para comenzar a buscar en Google. Aquí hay un documento 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, esto cae en el área llamada geometría computacional, que es fascinante, pero puede ser difícil de encontrar. Hay una buena visión general de deBerg en varios algoritmos relacionados con el tema.
Este es el famoso algoritmo de punto K-más cercano. Descrito aquí: http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
Podrías pixelar todo el área, luego ir a cada punto y aumentar el valor de todos los píxeles dentro del círculo del radio alrededor de ese punto. Los píxeles con la suma más alta son buenos candidatos.
Por supuesto, puede perder algunas áreas buenas o "alucinar" áreas buenas debido a errores de redondeo. Tal vez podrías tratar de hacer una pixellación aproximada primero, luego refinar las áreas prometedoras.
Si es cierto que la precisión no es importante y el algoritmo puede cometer pequeños errores, entonces creo que lo siguiente.
Sea f(x,y) una función que tenga un máximo en el punto (0,0) y solo sea significativa en los puntos dentro del círculo de radio R. Por ejemplo, f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)} .
Let (x_i,y_i) son puntos y E_i(x,y) = f(x - x_i, y - y_i) .
Tu problema es encontrar el máximo de /sum_i E_i(x,y) .
Puede usar un descenso de gradiente empezando desde cada punto.
Si quiere algo simple, tome la posición aleatoria (x, y), calcule el número de puntos dentro del círculo y compárelos con la posición anterior. Toma el máximo. Repita la operación cuando lo desee.
¿Por qué diablos downvote? ¿Has oído hablar de los métodos de Monte Carlo? En realidad, para una gran cantidad de puntos, el algoritmo determinista puede no terminar en un tiempo razonable.