Quadtree Nearest Neighbor Algorithm

geolocation nearest-neighbor

Question

He implementado una estructura quadtree para n puntos, así como un método para devolver una matriz de puntos dentro de un rectángulo dado. Parece que no puedo encontrar un algoritmo para encontrar eficientemente el punto que está más cerca de otro punto dado. ¿Me estoy perdiendo algo obvio? ¿Supongo que una solución recursiva es el enfoque correcto?

Estoy trabajando en Objective C pero el pseudo código estaría bien. Además, en realidad estoy almacenando latitud, datos largos y la distancia entre puntos es a lo largo de un gran círculo.

EDITAR: Este es mi inserto de árbol y el código de subdivisión

- (BOOL)insert:(id<PASQuadTreeDataPoint>)dataPoint {

    BOOL pointAdded = false;

    // If the point lies within the region
    if(CGRectContainsPoint(self.region, dataPoint.point)) {

        // If there are less than 4 points then add this point
        if(self.dataPoints.count < kMaxPointsPerNode) {
            [self.dataPoints addObject:dataPoint];
            pointAdded = true;
        }
        else {

            // Subdivide into 4 quadrants if not already subdivided
            if(northEast == nil) [self subdivide];

            // Attempt to add the point to one of the 4 subdivided quadrants
            if([northEast insert:dataPoint]) return true;
            if([southEast insert:dataPoint]) return true;
            if([southWest insert:dataPoint]) return true;
            if([northWest insert:dataPoint]) return true;
        }
    }

    return pointAdded;
}

- (void)subdivide {

    // Compute the half width and the origin
    CGFloat width = self.region.size.width * 0.5f;
    CGFloat height = self.region.size.height * 0.5f;
    CGFloat x = self.region.origin.x;
    CGFloat y = self.region.origin.y;

    // Create a new child quadtree with the region divided into quarters
    self.northEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y, width, height)];
    self.southEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y + height, width, height)];
    self.southWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y + height, width, height)];
    self.northWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y, width, height)];
}

EDITAR: Han escrito este código para encontrar el nodo más pequeño (hoja) que contendría el punto:

-(PASQuadTree *)nodeThatWouldContainPoint:(CGPoint)point {

    PASQuadTree *node = nil;

    // If the point is within the region
    if (CGRectContainsPoint(self.region, point)) {

        // Set the node to this node
        node = self;

        // If the node has children
        if (self.northEast != nil) {

            // Recursively check each child to see if it would contain the point
            PASQuadTree *childNode = [self.northEast nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.southEast nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.southWest nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.northWest nodeThatWouldContainPoint:point];
            if (childNode) node = childNode;
        }
    }

    return node;
}

Más cerca pero sin cigarro!

Answer 1

Encuentra el cuadrado más pequeño con tu punto de búsqueda en el centro y exactamente otro punto dentro de ese rectángulo (necesitas hacer un número de búsquedas aproximado).

Deje x sea la distancia al otro punto.

Luego encuentra todos los puntos dentro de un cuadrado cuyo lado es 2x y centrado alrededor de tu primer punto. Para cada punto dentro de este cuadrado, calcule la distancia desde el punto de búsqueda y encuentre el más cercano.

ACTUALIZACIÓN: ¿Cómo encontrar un cuadrado centrado alrededor del punto de búsqueda que contiene exactamente otro punto más?

Encuentra un punto aleatorio. Deje que la distancia a ese punto aleatorio sea x. Encuentre todos los puntos dentro del cuadrado de tamaño x centrado alrededor del punto de búsqueda. Si hay un número no nulo de puntos dentro de este cuadrado, entonces seleccione un punto al azar y repita. Si no hay puntos, aumente el tamaño del cuadrado de búsqueda a (2-0.5) * x (en el siguiente paso (2-0.25) * x y así sucesivamente.