Algorithm for finding minimum distance between pixel and groups of pixles

I need algorithm(preferably in c++ though pseudo code is ok too) to find a group among groups of pixels that have minimum distance to one particular pixel.

Th开发者_如何学Goe distance is defined as sum of distances of each pixel of the group to the particular pixel while each distance is equal |x|+|y| coordinates.

If its not clear enough I will try to clarify you

Thank you

It sounds like you already know how to calculate the distance.

Is a for-loop too slow for you? Would your loop be N^2?

If so, you might look into using a BSP, or a Quadtree. The only trouble I see is that you're trying to do a proximity test, where those are mostly designed for collision tests. It might still allow you to eliminate sets of groups more quickly.

Something that would definitely work (though its effectiveness in lowering your number of calculations is highly dependent on the distribution of your groups) is to simply split up the world into an evenly spaced, sparsely-populated grid. If a group falls into multiple sections of your grid, just add it to both grid entries. When you run your comparison, you pick the nearest grid entry, and only run your point-to-group algorithm on the groups in that grid entry.

Updated

The first draft of this solution computed geometric (euclidean) distances when the questian referred to Manhattan distances

This makes it simpler to optimise.

1. For each group of pixels choose one pixel as the primary pixel. It doesn't matter which one.

2. For each other pixel in the group, compute its offset (x and y) from the primary pixel. Unlike a Manhattan distance, keep the sign of this offset.

3. Sum all of the offsets (both x and y offsets) into a single number, call this total_offsets.

4. When you need the distance from a specified pixel, compute the (Manhattan) distance for the primary pixel. Multiply this by the number of pixels and add the total_offsets to get the total Manhattan distance.

Steps 1 - 3 need only be done once for each group and then step 4 can be performed as needed.

e.g.

  Area A consists of 4 pixels: (8, 8), (8, 9), (9, 8) and (9, 9).  

  Declare (8, 9) as primary pixel.  Offsets are   
      (8, 9) --> (8, 8) = (0, -1)  
      (8, 9) --> (9, 8) = (1, -1)  
      (8, 9) --> (9, 9) = (1, 0)  
  total_offset = 0 + -1 + 1 + -1 + 1 + 0   
               = 0  
  num_pixels = 4  

To compute Manhattan distance from pixel (2, 4)

  distance to primary pixel  
  (2, 4) --> (8, 9) = (6, 5)   
                    = 11  
  dist * num_pixels + total_offsets = 11 * 4 + 0
                                    = 44

To check this, we can compute it the long way:

      (2, 4) --> (8, 8) = (6, 4)   
      (2, 4) --> (8, 9) = (6, 5)   
      (2, 4) --> (9, 8) = (7, 4)   
      (2, 4) --> (9, 9) = (7, 5)   

  distance = 6 + 4 + 6 + 5 + 7 + 4 + 7 + 5 
           = 44

The following is a simplified example. You'll need a function "int distance(Point p1, Point p2)" to calculate the distance (using whatever algorithm).

Point pxTest = ... // the single pixel to use for distance checking
List<Point> pxGroup = ... // the group of pixels to check

Point pxMin = null; // the pixel with the minimum distance
int iMin = int.MAX; // the minimum distance so far

foreach(Point pxOther in pxGroup)
    if(iMin > distance(pxTest, pxOther))
    {
        iMin = distance(pxTest, pxOther); // this could be cached in the line before as well to save this call
        pxMin = pxOther;
    }

// now pxMin will include the closest point, iMin the distance