Vecinos de un punto en un círculo usando el algoritmo de Bresenham

Dado un centro de un círculo y su radio. nuestra tarea es encontrar los vecinos de cualquier punto en el círculo discreto. 
Ejemplos: 
 

Input :  Center = (0, 0), 
         Radius = 3 
         Point for determining neighbors = (2, 2)
Output : Neighbors of given point are : (1, 3), (3, 1)

Input : Center = (2, 2) 
        Radius 2
        Point of determining neighbors = (0, 2)
Output : Neighbors of given point are : (1, 4), (3, 4)

Los vecinos de cualquier punto en el círculo discreto son aquellos puntos que tienen una coordenada x menos o una coordenada x más de su coordenada x original. 
 

Usamos el algoritmo de generación de círculos de Bresenham para extraer los puntos enteros necesarios para dibujar un círculo en la pantalla de la computadora de píxeles.
 

Los círculos tienen la propiedad de ser altamente simétricos, lo cual es necesario cuando se trata de dibujarlos en la pantalla de la computadora de píxeles. El algoritmo circular de Bresenham calcula las ubicaciones de los píxeles en los primeros 45 grados y los píxeles restantes en la periferia de un círculo que está centrado en el origen se calculan utilizando la propiedad de simetría de 8 vías del círculo.
 

Derivación: Considere un arco de círculo continuo infinitesimalmente pequeño como se muestra en la figura a continuación. Supongamos que queremos movernos a lo largo de un arco circular en el sentido de las agujas del reloj con centro en el origen, con radio r y nuestro movimiento se encuentra en el primer octante. octante, por lo que nuestros límites son de (0, r) a (r/ , r/ ) donde x = y. como sabemos que, en este octante en particular, la disminución en la coordenada y es menor que el aumento en la coordenada x o puede decir que el movimiento a lo largo del eje x es mayor que el movimiento a lo largo del eje y, por lo tanto, la coordenada x siempre aumenta en primer octante. ahora, queremos saber si y cambiará con x o no. Para conocer la variación de y con x, bresenham introdujo una variable llamada parámetro de decisión que actualizará su valor a medida que se ejecuta el bucle.
Ahora, debemos entender cómo elegiremos el siguiente píxel. En la figura, f (N) y f (S) son errores involucrados en el cálculo de las distancias desde el origen hasta el píxel N y S respectivamente y cualquiera que resulte ser menos elegiremos ese píxel. El parámetro de decisión se define como d = f(N)+f(S), si d <= 0, entonces N será el siguiente píxel; de lo contrario, S será el siguiente píxel. Seguiremos haciendo este procedimiento hasta que se cumpla la condición x<y y tomando todos los puntos simétricos terminaremos con todos los puntos enteros necesarios para mostrar un círculo de píxeles en la pantalla de la computadora.
Este artículo no se centra predominantemente en el algoritmo de Bresenham, por lo tanto, omitiré la derivación del parámetro de decisión, pero si desea comprender la derivación del parámetro de decisión, vaya a los enlaces de referencia.
Nota:los vecinos de un punto pueden ser de cualquier número y la coordenada y de los vecinos debe tener el mismo signo que su píxel de entrada y para aquellos píxeles que tienen la coordenada y cero imprimiremos todos los vecinos independientemente de sus signos.
Un objeto geométrico discreto consta de un conjunto finito de puntos enteros. Este conjunto suele ser muy escaso. Por lo tanto, una representación de array no es del todo eficiente en el espacio para almacenar. Usaremos un mapa hash que tiene un valor de datos que es una lista vinculada de la coordenada y y el valor clave como coordenada x. podemos acceder fácilmente a ellos usando el valor clave y también es un espacio eficiente.
A continuación se muestra el programa stl de C++ para determinar los vecinos de un punto dado.
 

// C++ program to find neighbors of a given point on circle
#include <bits/stdc++.h>
using namespace std;
 
// map to store all the pixels of circle
map<int, list<int> > mymap;
map<int, list<int> >::iterator it;
 
// This program will print all the stored pixels.
void showallpoints(map<int, list<int> >& mymap)
{
    // To print out all the stored pixels,
    // we will traverse the map using iterator
    for (it = mymap.begin(); it != mymap.end(); it++) {
 
        // List contains all the y-coordinate.
        list<int> temp = it->second;
 
        for (auto p = temp.begin(); p != temp.end(); p++) {
            cout << "(" << it->first << ", " << *p << ")\n";
        }
    }
}
 
// This function will stored the pixels.
void putpixelone(int m, int n, map<int, list<int> >& mymap)
{
    // check if the given pixel is present already in the
    // map then discard that pixel and return the function.
    map<int, list<int> >::iterator it;
 
    // if x-coordinate of the pixel is present in the map then
    // it will give iterator pointing to list of those pixels
    // which are having same x-coordinate as the input pixel
    if (mymap.find(m) != mymap.end()) {
 
        it = mymap.find(m);
        list<int> temp = it->second;
        list<int>::iterator p;
 
        // Checking for y coordinate
        for (p = temp.begin(); p != temp.end(); p++)
            if (*p == n)
                return;
 
        // if map doesn't contain pixels having same y-
        // coordinate then pixel are different and store
        // the pixel
        mymap[m].push_back(n);
    } else
 
        // Neither x nor y coordinate are same.
        // put the pixel into the map
        mymap[m].push_back(n);
 
    return;
}
 
// generate all the pixels using 8 way-symmetry of circle
void putpixelall(int p, int q, int x1, int y1)
{
    putpixelone(p + x1, q + y1, mymap);
    putpixelone(q + x1, p + y1, mymap);
    putpixelone(q + x1, -p + y1, mymap);
    putpixelone(p + x1, -q + y1, mymap);
    putpixelone(-p + x1, -q + y1, mymap);
    putpixelone(-q + x1, -p + y1, mymap);
    putpixelone(-q + x1, p + y1, mymap);
    putpixelone(-p + x1, q + y1, mymap);
    return;
}
 
// Brensenham's circle algorithm
void circle(int centerx, int centery, int r)
{
    // initial coordinate will be (0, radius) and we
    // will move counter-clockwise from this coordinate
    int x = 0;
    int y = r;
 
    // decision parameter for initial coordinate
    float decision_para = 3 - 2 * (r);
    putpixelall(x, y, centerx, centery);
 
    while (x < y) {
 
        // x will always increase by 1 unit
        x = x + 1;
        if (decision_para <= 0) {
 
            // if decision parameter is negative then N
            // will be next pixel N(x+1, y)
            decision_para = decision_para + 4 * x + 6;
        } else {
 
            // if decision parameter is positive then N
            // will be next pixel S(x+1, y-1)
            y = y - 1;
            decision_para = decision_para + 4 * (x - y) + 10;
        }
 
        // Function call to generate all the pixels by symmetry
        putpixelall(x, y, centerx, centery);
    }
    return;
}
// this program will find the neighbors of a given point`
void neighbours(map<int, list<int> >& mymap, int given_pointx,
                                             int given_pointy)
{
    for (it = mymap.begin(); it != mymap.end(); ++it) {
        if (it->first == given_pointx + 1 ||
            it->first == given_pointx - 1) {
            list<int> temp1 = it->second;
            list<int>::iterator itr1;
            for (itr1 = temp1.begin(); itr1 != temp1.end(); ++itr1) {
 
                // Checking for same-sign.
                if (given_pointy >= 0 && *itr1 >= 0)
                    cout << "(" << it->first << ", " << *itr1 << ")\n";
                else if (given_pointy <= 0 && *itr1 <= 0)
                    cout << "(" << it->first << ", " << *itr1 << ")\n";
                else
                    continue;
            }
        }
    }
}
 
// Driver code
int main()
{
    int center_x = 0, center_y = 0;
    float r = 3.0;
    circle(center_x, center_y, r);
    showallpoints(mymap);
    int nx = 3, ny = 0;
    neighbours(mymap, nx, ny);
    cout << endl;
    return 0;
}

Producción: 
 

(-3, 0), (-3, -1), (-3, 1), (-2, -2), (-2, 2), (-1, -3), (-1, 3), (0, 3)
(0, -3), (1, 3), (1, -3), (2, 2), (2, -2), (3, 0), (3, 1), (3, -1)
 Neighbours of given point are : (2, 2), (2, -2)

Referencias: 
https://www.slideshare.net/tahersb/bresenham-circle
Este artículo es una contribución de Harsh Kumar Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.