algorithm - diametro - perimetro de un circulo

Número mínimo de círculos con radio r para cubrir n puntos (9)

Del documento "Sobre el problema de la cubierta del disco de la unidad discreta" por Gautam K. Das et. Alabama.:

Cubierta de disco geométrica mínima . En el problema de la cubierta de disco geométrica mínima, la entrada consiste en un conjunto de puntos en el plano, y el problema es encontrar un conjunto de discos de unidad de cardinalidad mínima cuya unión cubra los puntos. A diferencia de DUDC, los centros de disco no están restringidos para ser seleccionados de un conjunto discreto dado, sino que pueden estar centrados en puntos arbitrarios en el plano. De nuevo, este problema es NP-duro [9] y tiene una solución PTAS [11, 12].

Referencias:

R. Fowler, M. Paterson y S. Tanimoto, el embalaje y la cobertura óptimos en el avión son NP-completos, Information Processing Letters, vol 12, pp. 133-137, 1981.
G. Frederickson, algoritmos rápidos para trayectos más cortos en gráficos planos, con aplicaciones, SIAM J. on Computing, vol 16, pp. 1004-1022, 1987.
T. Gonzalez, Cubriendo un conjunto de puntos en el espacio multidimensional, Information Processing Letters, vol 40, pp. 181-188, 1991.
D. Hochbaum y W. Maass, Esquemas de aproximación para cubrir y empaquetar problemas en el procesamiento de imágenes y VLSI, J. ACM, vol. 32, pp. 130-136, 1985.

¿Cuál es el número mínimo de círculos con radio r necesario para cubrir todos los n puntos? r y n se darán como entrada, seguidos de n pares de números enteros que representan las coordenadas xy de los n puntos. r es un número real y mayor que 0. n es <20.

Un círculo cubre un punto si el punto se encuentra dentro del círculo. Un punto se encuentra dentro de un círculo si la distancia entre el punto y el centro del círculo es menor o igual que r.

Esta es mi primera respuesta, la cual dejaré como se menciona en otra respuesta. Pero vea mi respuesta posterior que considera círculos entre dos puntos en lugar de esto. Aquí hay un algoritmo codicioso codificado en Python que encontrará un mínimo, pero no sé si es la solución mínima.

dbg = False if not dbg: r, n = (int(s) for s in input(''r n: '').split()) points = p = [ tuple(int(s) for s in input(''x%i y%i: '' % (i, i)).split()) for i in range(n) ] else: r, n, points = 3, 5, [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]; p = points # What a circle at each point can cover coverage = { i: frozenset(j for j in range(i, n) if (p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2 <= r**2) for i in range(n)} # Greedy coverage choice chosen, covered = [], set() while len(covered) < n: # Choose the circle at the point that can cover the most ADDITIONAL points. _, nxt_point, nxt_cov = max((len(pts - covered), i, pts) for i, pts in coverage.items()) covered |= nxt_cov chosen.append(nxt_point) print(''Cover these points:/n %s'' % ''/n ''.join(''%s, %s'' % p[i] for i in chosen))

Y aquí hay una muestra de ejecución:

r n: 3 5 x0 y0: 1 3 x1 y1: 0 2 x2 y2: 4 5 x3 y3: 2 4 x4 y4: 0 3 Cover these points: 1, 3 4, 5

Nota: los datos de entrada / salida son rudimentarios, pero el algoritmo debe ser claro.

Esta no es la mejor solución, pero probablemente intente optimizarla.

El algoritmo se basa en el muestreo aleatorio:

Generar N círculos en el mapa
Eliminar todos los círculos que no estén cubriendo ningún punto.
Ordenar círculos descendientes por número de puntos cubiertos
Foreach circle (sorted): marca los puntos que están cubiertos por un círculo como cubiertos. Si el círculo no cubre ningún punto nuevo, elimínelo de la lista.

Aquí está el código para verlo en vivo: http://jsfiddle.net/rpr8qq4t/ Ejemplo de resultado (13 círculos por 30 puntos):

Parametrizaciones:

var POINTS_NUMBER = 30; var RADIUS = 50; var SAMPLE_COUNT = 400;

Se le pueden agregar algunas optimizaciones (por ejemplo, algunos círculos se pueden excluir de la lista demasiado pronto)

Editar :

El cambio en el paso 1 trae mejores resultados: genere N círculos para cada punto (círculos que cubren al menos en el punto) Nueva versión: http://jsfiddle.net/nwvao72r/3/

Edición 2 (algoritmo final)

Finalmente:

Para cada punto, genere N = 10 círculos en una distancia aleatoria menor que R desde el punto (radio del círculo, de modo que estamos seguros de que para cada círculo al menos un punto le pertenece y cada punto pertenece a al menos un círculo)
Repita hasta que todos los puntos estén cubiertos:
- obtener el círculo que cubre el número máximo de puntos descubiertos. Marque los puntos como cubiertos.

Aquí está la versión que me brinda mejores resultados, puede consultarla aquí http://jsfiddle.net/nwvao72r/4/ en promedio 12 círculos por 30 puntos aquí.

Estoy seguro de que este problema es NP-difícil, aunque no voy a intentar demostrarlo aquí.

Si es NP-difícil, entonces, para encontrar una solución óptima garantizada, recomiendo el siguiente enfoque:

Encuentre todas las colocaciones "buenas" en el círculo, y para cada registro qué puntos están contenidos en él.
Resuelve el problema de la cubierta del conjunto con estos conjuntos de puntos. (Este problema es NP-duro.)

Buenas colocaciones circulares

Dado que hay 2 puntos menos que 2r aparte, hay exactamente dos círculos de radio r que pasan por estos puntos:

[EDIT: Mi descripción original de los círculos "mejor posible" estaba equivocada, aunque esto no lleva a problemas, gracias al comentarista Jorge por describir la forma correcta de pensar sobre esto.]

Si un círculo cubre un conjunto máximo de puntos (lo que significa que el círculo no puede ser reposicionado para cubrir el mismo conjunto de puntos más al menos 1 más), ese círculo se puede deslizar hasta que su límite toque exactamente dos de los puntos que cubre: - digamos, deslizándolo hacia la izquierda hasta que toque un punto ya cubierto, y luego girándolo hacia la derecha alrededor de este punto tocado hasta que toque otro punto ya cubierto. Este círculo movido cubrirá exactamente el conjunto de puntos que cubrió el círculo original. Además, nunca debemos considerar círculos que cubran conjuntos de puntos no máximos, porque un círculo máximo que cubra estos puntos y más es al menos tan útil y no cuesta más. Esto significa que solo debemos considerar círculos que toquen dos puntos. Siempre que generemos ambos círculos para cada par de puntos suficientemente cercanos en la entrada, habremos generado todos los círculos que podríamos necesitar.

Así que nuestro grupo de círculos potenciales contiene como máximo 2 círculos por par de puntos, para un máximo de n * (n-1) círculos potenciales en general. (Por lo general, habrá menos, porque algunos pares de puntos generalmente estarán más separados que 2r y, por lo tanto, no pueden cubrirse con un solo círculo de radio r). Además, necesitamos un círculo adicional para cada punto que esté más alejado de 2r de cualquier otro punto: estos círculos también podrían estar centrados en esos puntos remotos.

Establecer cubierta

Todo lo que realmente nos importa es el conjunto de puntos cubiertos por cada círculo potencial. Entonces, para cada círculo potencial, encuentra los puntos que cubre. Esto se puede hacer en tiempo O (n ^ 3) en general, utilizando un pase O (n) para cada círculo potencial. Para acelerar un poco las cosas, si encontramos que dos círculos diferentes cubren exactamente el mismo conjunto de puntos, solo necesitamos mantener uno de estos círculos (conjuntos de puntos cubiertos). También podemos descartar cualquier conjunto de puntos cubiertos que sea un subconjunto de algún otro conjunto de puntos cubiertos; siempre es preferible elegir el conjunto de puntos cubiertos más grandes en este caso.

Finalmente, tenemos una colección de conjuntos de puntos cubiertos, y queremos encontrar el subconjunto mínimo de estos conjuntos que cubra cada punto. Este es el problema de la cubierta de conjunto . No conozco un algoritmo específico para resolver esto, pero ramificación y límite es el enfoque estándar para tales problemas: a menudo es mucho más rápido que una búsqueda exhaustiva de retroceso más simple. Primero cebaría la búsqueda encontrando primero una (o más) soluciones heurísticas, con suerte obteniendo un buen límite superior que reduzca el tiempo de búsqueda de ramificación y límite. Creo que incluso los mejores algoritmos para este tiempo exponencial toman en el peor de los casos, aunque creo que será manejable para n <20 ya que hay como máximo 19 * 18 = 342 conjuntos de puntos diferentes.

Me doy cuenta de que los círculos no tienen que estar centrados en los puntos y, por lo tanto, calculan todos los círculos que pasan por cualquier combinación de dos puntos, incluidos los círculos centrados en cada punto. Luego encuentro qué puntos cubre cada círculo y uso un algoritmo voraz para encontrar un conjunto mínimo de círculos que cubran todos los puntos, pero, de nuevo, puede que no sea el conjunto mínimo de círculos, pero es bastante fácil de calcular.

from collections import namedtuple from itertools import product from math import sqrt from pprint import pprint as pp Pt = namedtuple(''Pt'', ''x, y'') Cir = namedtuple(''Cir'', ''x, y, r'') def circles_from_p1p2r(p1, p2, r): ''Following explanation at http://mathforum.org/library/drmath/view/53027.html'' (x1, y1), (x2, y2) = p1, p2 if p1 == p2: #raise ValueError(''coincident points gives infinite number of Circles'') return None, None # delta x, delta y between points dx, dy = x2 - x1, y2 - y1 # dist between points q = sqrt(dx**2 + dy**2) if q > 2.0*r: #raise ValueError(''separation of points > diameter'') return None, None # halfway point x3, y3 = (x1+x2)/2, (y1+y2)/2 # distance along the mirror line d = sqrt(r**2-(q/2)**2) # One answer c1 = Cir(x = x3 - d*dy/q, y = y3 + d*dx/q, r = abs(r)) # The other answer c2 = Cir(x = x3 + d*dy/q, y = y3 - d*dx/q, r = abs(r)) return c1, c2 def covers(c, pt): return (c.x - pt.x)**2 + (c.y - pt.y)**2 <= c.r**2 if __name__ == ''__main__'': for r, points in [(3, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]), (2, [Pt(*i) for i in [(1, 3), (0, 2), (4, 5), (2, 4), (0, 3)]]), (3, [Pt(*i) for i in [(-5, 5), (-4, 4), (3, 2), (1, -1), (-3, 2), (4, -2), (6, -6)]])]: n, p = len(points), points # All circles between two points (which can both be the same point) circles = set(sum([[c1, c2] for c1, c2 in [circles_from_p1p2r(p1, p2, r) for p1, p2 in product(p, p)] if c1 is not None], [])) # points covered by each circle coverage = {c: {pt for pt in points if covers(c, pt)} for c in circles} # Ignore all but one of circles covering points covered in whole by other circles #print(''/nwas considering %i circles'' % len(coverage)) items = sorted(coverage.items(), key=lambda keyval:len(keyval[1])) for i, (ci, coveri) in enumerate(items): for j in range(i+1, len(items)): cj, coverj = items[j] if not coverj - coveri: coverage[cj] = {} coverage = {key: val for key, val in coverage.items() if val} #print(''Reduced to %i circles for consideration'' % len(coverage)) # Greedy coverage choice chosen, covered = [], set() while len(covered) < n: _, nxt_circle, nxt_cov = max((len(pts - covered), c, pts) for c, pts in coverage.items()) delta = nxt_cov - covered covered |= nxt_cov chosen.append([nxt_circle, delta]) # Output print(''/n%i points'' % n) pp(points) print(''A minimum of circles of radius %g to cover the points (And the extra points they covered)'' % r) pp(chosen)

La salida que muestra las tres carreras es:

5 points [Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)] A minimum of circles of radius 3 to cover the points (And the extra points they covered) [[Cir(x=2.958039891549808, y=2.5, r=3), {Pt(x=4, y=5), Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}]] 5 points [Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=4, y=5), Pt(x=2, y=4), Pt(x=0, y=3)] A minimum of circles of radius 2 to cover the points (And the extra points they covered) [[Cir(x=1.9364916731037085, y=2.5, r=2), {Pt(x=0, y=3), Pt(x=1, y=3), Pt(x=0, y=2), Pt(x=2, y=4)}], [Cir(x=4, y=5, r=2), {Pt(x=4, y=5)}]] 7 points [Pt(x=-5, y=5), Pt(x=-4, y=4), Pt(x=3, y=2), Pt(x=1, y=-1), Pt(x=-3, y=2), Pt(x=4, y=-2), Pt(x=6, y=-6)] A minimum of circles of radius 3 to cover the points (And the extra points they covered) [[Cir(x=3.9951865152835286, y=-0.8301243435223524, r=3), {Pt(x=3, y=2), Pt(x=1, y=-1), Pt(x=4, y=-2)}], [Cir(x=-2.0048134847164714, y=4.830124343522352, r=3), {Pt(x=-4, y=4), Pt(x=-3, y=2), Pt(x=-5, y=5)}], [Cir(x=6.7888543819998315, y=-3.1055728090000843, r=3), {Pt(x=6, y=-6)}]]

No estoy seguro de si esto es correcto, pero si no necesitamos las ubicaciones exactas de los círculos de solución, me parece que podemos resolverlo mirando los grupos de puntos: en cualquiera de las soluciones En los círculos, la distancia entre cualquiera de los dos puntos debe ser menor o igual a 2 * r.

Algoritmo:

1. j_random_hacker indicated that any solution-circle could be shifted so that two of its covered-points lay on its circumference without changing the original covered-points. Since the solution-circle radius is given, for each point: (a) calculate potential circle-centers using the point, radius, and each other point that is at a distance of 2*r or less, (b) for each circle, list the cluster of points that it could cover. Sort each cluster and, for each point, remove duplicate clusters. 2. For each cluster group in 1., choose the cluster that has the greatest point- count, that is, the cluster that is most shared. 3. Remove duplicates and clusters that are sub-sequences of other clusters from 2., and present the resulting size of 2. (perhaps together with the chosen clusters) as the solution.

Salida para el triángulo equilátero, r = 3, [(0,0), (5.196152422706632,3), (5.196152422706632, -3)]

*Main> solve (2,[[(0.0,0.0),(5.196152422706632,3.0)],[(0.0,0.0),(5.196152422706632,-3.0)]])

Salida para el ejemplo de Paddy3118, r = 3, [(1,3), (0,2), (4,5), (2,4), (0,3)]:

*Main> solve (1,[[(0.0,2.0),(0.0,3.0),(1.0,3.0),(2.0,4.0),(4.0,5.0)]])

Salida para r = 3, [(-5,5), (- 4,4), (3,2), (1, -1), (- 3,2), (4, -2), (6 , -6)]:

*Main> solve (3,[[(-5.0,5.0),(-4.0,4.0),(-3.0,2.0)],[(1.0,-1.0),(3.0,2.0),(4.0,-2.0)], [(4.0,-2.0),(6.0,-6.0)]])

Código Haskell:

import Data.List (delete, nub, nubBy, isInfixOf, sort, sortBy, maximumBy) points = [(0,0),(5.196152422706632,3),(5.196152422706632,-3)]--[(1,3),(0,2),(4,5),(2,4),(0,3)]--[(-5,5),(-4,4),(3,2),(1,-1),(-3,2),(4,-2),(6,-6)] r = 3 twoR = 2*r circleCenters (x1,y1) (x2,y2) = let q = sqrt $ (x2-x1)^2 + (y2-y1)^2 (x3, y3) = ((x1+x2)/2,(y1+y2)/2) first = (x3 + sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 + sqrt(r^2-(q/2)^2)*(x2-x1)/q) second = (x3 - sqrt(r^2-(q/2)^2)*(y1-y2)/q, y3 - sqrt(r^2-(q/2)^2)*(x2-x1)/q) in [first,second] isInCircle (center_x,center_y) (x,y) = (x-center_x)^2 + (y - center_y)^2 <= r^2 findClusters (px,py) = nub [sort $ [(px,py)] ++ filter (isInCircle a) potentialPoints | a <- potentialCircleCenters] where potentialPoints = filter (/(x,y) -> (x-px)^2 + (y-py)^2 <= twoR^2) (delete (px,py) points) potentialCircleCenters = concatMap (circleCenters (px,py)) potentialPoints solve = (length bestClusters, bestClusters) where clusters = map findClusters points uniqueClusters = nub . concat $ clusters bestClusterForEachPoint = map (maximumBy (/a b -> compare (length a) (length b))) clusters bestClusters = nub . nubBy (/a b -> isInfixOf a b) . sortBy (/a b -> compare (length b) (length a)) $ bestClusterForEachPoint

Si coloca n círculos (de radio r ) todos centrados en cada punto, busque las regiones / puntos de superposición máxima y coloque nuevos círculos (de radio r ) centrados en esa región. No estoy seguro de si esta es la mejor manera de resolver la solución (si es una manera de resolverla, además de la forma de fuerza bruta), estoy seguro de que puede implementarla con una cantidad bastante buena de matemáticas, y disminuyendo así la complejidad en tiempo de ejecución de su solución. Espero que esto ayude. Por favor, dar su opinión.

Si el círculo con el centro C(cx, cy) cubre el punto P(px, py) entonces la distancia |CP| < r |CP| < r ( r - radio). Entonces, la región donde podría estar el centro del círculo que cubre el punto P es un círculo con el centro en P y el radio r . Ahora dibujemos todos los círculos con centros en puntos dados y radio r . Si algunos círculos se intersecan, podemos dibujar un nuevo círculo con el centro en tal intersección que cubra los puntos correspondientes. Así que para cada par de puntos de entrada verificamos si los círculos se intersecan.

Supongamos que los puntos de entrada son vértices y la intersección obtiene un borde entre ellos. Ahora tenemos un borde conocido del problema del gráfico que cubre http://en.wikipedia.org/wiki/Edge_cover que podría resolverse en tiempo polinomial (aunque con una limitación n < 20 la fuerza bruta probablemente sería aceptable)

ACTUALIZAR. Eso no es cubierta de borde. Mi error.

Azulejo luego jiggle

TILE: Encuentra el rectángulo que encierra todos los puntos.
Coloque en mosaico el área rectangular con círculos espaciados r * sqrt (2) separados.
Para cada punto, calcula qué círculos son y qué puntos hay en cada círculo.
Eliminar cualquier círculo sin puntos.
Quite cualquier círculo que contenga solo puntos que estén contenidos en más de un círculo.
Repite 5 hasta que no haya más.
Jiggle: Para cada círculo: intente moverlo para ver si puede cubrir sus puntos originales más un máximo de nuevos puntos y hacerlo.
Haz 4 y 5 otra vez.
Repita 7 hasta que el movimiento no cambie los puntos de los círculos o el tiempo agotado.

Paso 2, el mosaico se podría optimizar al pasar por cada punto y calcular / mantener solo aquellos círculos que contendrían un punto si el mosaico fuera muy escaso.