Generación de polígonos con coordenadas enteras que delimitan un círculo

Question

He estado tratando de encontrar un algoritmo para generar polígonos con coordenadas enteras que delimiten un círculo por dentro y por fuera. He buscado por todas partes y no he encontrado nada parecido. Por ejemplo en la imagen de abajo tenemos el círculo rojo con un radio determinado, y pedimos polígonos con 8 puntos, y entonces el algoritmo debería generar los polígonos azules y verdes.

Estos polígonos no son exactamente regulares, y tampoco creo que estos polígonos estén definidos de forma única, ya que probablemente haya diferentes formas de ajustar "mejor" el círculo. En realidad no estoy buscando la mejor solución absoluta, por ejemplo, podría intentar minimizar el error máximo, pero eso podría complicar mucho el problema. En realidad, he intentado expresar esto como un problema de programación entera con desigualdades cuadráticas de Diofantino, pero parece que es excesivo.

¿Se trata de un problema que ya ha sido estudiado o resuelto anteriormente? ¿Me falta un método sencillo?

Answer 1

A continuación se ofrece una respuesta sencilla de fuerza bruta. Se basa en pensar en la Algoritmo del círculo del punto medio pero no lo requiere. En resumen:

• Para el polígono interior, encuentre todos los puntos enteros que están dentro del círculo, luego tome su casco convexo.

• Para el polígono exterior, genere un conjunto de puntos enteros que estén fuera del círculo tal que se garantice que su casco convexo también esté fuera del círculo.

Demostraré la respuesta con código MATLAB (versión R2016a, sin cajas de herramientas). En primer lugar, configure una figura con el círculo.

%% Circle

r = 2.7; % Change this to try different radii.

figure
rectangle('Position', [-r -r 2*r 2*r], 'Curvature', [1 1], ...
      'LineWidth', 2, 'EdgeColor','r')
hold on
grid on
axis equal

Ahora configure una malla con puntos enteros $(X,Y)$

rIntegerRange = -ceil(r):ceil(r);
[X,Y] = meshgrid(rIntegerRange,rIntegerRange);

Polígono interior : Casco convexo de los puntos enteros adjuntos.

%% Inner Polygon - Convex hull of the enclosed integer points.

R = sqrt(X.^2 + Y.^2);
Iinside = R < r;
Xinside = X(Iinside);
Yinside = Y(Iinside);

KInnerPolygon = convhull(Xinside,Yinside);
XInnerPolygon = Xinside(KInnerPolygon);
YInnerPolygon = Yinside(KInnerPolygon);

plot(Xinside,       Yinside,       'g.',  'MarkerSize', 12);
plot(XInnerPolygon, YInnerPolygon, 'g.-', 'LineWidth',  2)

Polígono exterior : Es bonito utilizar cascos convexos, pero tenemos que asegurarnos de que cuando obtenemos el casco convexo no recortamos el círculo. La solución en este caso se puede imaginar de la siguiente manera - en el primer octante, poner alfileres en el círculo donde se cruza una línea $x=k$ para los enteros $k$ . A continuación, empuje esas clavijas hacia arriba hasta que lleguen a una línea entera para $y$ . Se garantizará que el casco convexo alrededor de esos puntos quede fuera del círculo. Por último, duplica el octante en un conjunto completo de puntos alrededor del círculo.

%% Outer Polygon - Convex hull of roundups.

% First octant: Round up the y coordinate.
X1 = 0 : floor(r);
Y1 = ceil(sqrt(r^2 - X1.^2));

% Duplicate into the first quadrant ...
Xq = [X1, Y1(end:-1:1)];
Yq = [Y1, X1(end:-1:1)];

% ... and then into the full set of points.
Xoutside = [Xq,  Xq, -Xq, -Xq];
Youtside = [Yq, -Yq, -Yq,  Yq];

% Now obtain the convex hull.
KOuterPolygon = convhull(Xoutside,Youtside);
XOuterPolygon = Xoutside(KOuterPolygon);
YOuterPolygon = Youtside(KOuterPolygon);

plot(Xoutside,      Youtside,      'b.',  'MarkerSize', 12);
plot(XOuterPolygon, YOuterPolygon, 'b.-', 'LineWidth',  2)

Observando los resultados, es evidente que el polígono exterior es conservador.

Como refinamiento para eliminar puntos (que no he explorado) : Obsérvese que para tres puntos sucesivos cualesquiera $(x_1,y_1)$ , $(x_2,y_2)$ , $(x_3,y_3)$ en el polígono exterior, el punto medio podría ser eliminado si $\bigl(t x_3 + (1-t)x_1, t y_3 + (1-t)y_1 \bigr)$ está fuera del círculo para todo $0 \leq t \leq 1$ . Además, esto será cierto si y sólo si $$\bigl( t x_3 + (1-t)x_1 \bigr)^2 + \bigl( t y_3 + (1-t)y_1 \bigr)^2 \geq r^2$$ para todos $0 \leq t \leq 1$ . Intenta resolver la igualdad (ecuación cuadrática) y elimina el punto si no existe solución.

Answer 2

Sigue un script de MATHEMATICA que basándose en el casco convexo para un conjunto de puntos en el plano, dibuja polígonos externos e internos aproximados sobre un círculo situado aleatoriamente en la red de enteros. Este script puede ser optimizado pero se dejó en lo básico para una mejor comprensión del algoritmo.

grids[min_, max_] := Table[If[EvenQ[i], {i, Black}, {i, Black}], {i, Ceiling[min], Floor[max], 1}]
InternalCH[p0_List, r_] := Module[{xmin = Floor[p0[[1]] - r - 5],
    xmax = Ceiling[p0[[1]] + r + 5],
    ymin = Floor[p0[[2]] - r - 5],
    ymax = Ceiling[p0[[2]] + r + 5], xsup = -10^9, xinf, ysup, yinf,i,j, p,pts = {}},
    xinf = -xsup;
    ysup = xsup;
    yinf = xinf;
    For[i = xmin, i <= xmax, i++, 
       For[j = ymin, j <= ymax, j++, p = {i, j}; 
          If[(p - p0).(p - p0) < r^2, AppendTo[pts, p]; 
            xinf = Min[xinf, i];
            xsup = Max[xsup, i]; 
            yinf = Min[yinf, j]; 
            ysup = Max[ysup, j]]]]; 
    Return[{{xinf, xsup, yinf, ysup}, pts}]
]
p0 = RandomReal[{-30, 30}, 2];
r = RandomReal[{4, 10}];
{{xinf, xsup, yinf, ysup}, pts} = InternalCH[p0, r];
{{xinfe, xsupe, yinfe, ysupe}, ptse} = InternalCH[p0, r + 1 0.9];
gr1 = ContourPlot[(x - p0[[1]])^2 + (y - p0[[2]])^2 == r^2, {x, 
xinf - 1, xsup + 1}, {y, yinf - 1, ysup + 1}, ContourStyle -> {Thick, Black}];
gr2 = RegionBoundary[ConvexHullMesh[pts, MeshCellStyle -> {Thick,Blue, Dotted}]];
re = r + 1;
gr1e = ContourPlot[(x - p0[[1]])^2 + (y - p0[[2]])^2 == re^2, {x, 
xinf - re/4, xsup + re/4}, {y, yinfe - re/4, ysupe + re/4},ContourStyle -> {Thick, Red}];
gr2e = RegionBoundary[ConvexHullMesh[ptse, MeshCellStyle -> {Thick, Red, Dotted}]];
Show[gr2e, gr2, gr1, AspectRatio -> 1, GridLines -> grids]

Answer 3

Esto no responde a su pregunta exacta, pero quizás sus resultados pueden adaptarse aproximando círculos un poco más grandes y un poco más pequeños círculos.

Bhowmick, Partha, y Bhargab B. Bhattacharya. "Aproximación de círculos digitales mediante polígonos regulares". En Internat. Conf. Reconocimiento de Patrones y Análisis de Imágenes , pp. 257-267. Springer, Berlín, Heidelberg, 2005. Enlace a la revista .

---

         

Obsérvese también la considerable bibliografía sobre el tema citada por B&B.

Answer 4

Una respuesta podría ser un incluido y un incluido Círculos de Schinzel . Puede que no sean la mejor solución para las áreas poligonales máximas y mínimas, pero son muy fáciles de encontrar a partir del número $n$ de los vértices deseados.