How to find the pixel that is farthest from another in the same pixel group

Question

By "Group", I mean a set of pixels such that every pixel at least have one adjacent pixel in the same set, the drawing shows an example of a group.

I would like to find the pixel which is having the greatest straight line distance from a designated pixel (for example, the green pixel). And the straight line connecting the two pixels (the red line) must not leave the group.

My solution is looping through the degrees and simulating the progress of the lines starting from the green pixel with the degree and see which line travelled the farthest distance.

longestDist = 0
bestDegree = -1
farthestX = -1
farthestY = -1
FOR EACH degree from 0 to 360
    dx=longestDist * cos(degree);
    dy=longestDist * sin(degree);
    IF Point(x+dx , y+dy) does not belong to the group
        Continue with next degree
        //Because it must not be the longest line, so skip it
    END IF
    (farthestX , farthestY) = simulate(x,y,degree)
    d = findDistance(x , y , farthestX , farthestY)
    IF d > longestDist
        longestDist = d
        bestDegree = degree
    END IF
END FOR

It is obviously not the best algorithm. Thus I am asking for help here.

Thank you and sorry for my poor English.

Answer 1

Treat your region as a polygon instead of a collection of pixels. From this you can get a list of line segments (the edges of your polygon).

Draw a line from your start pixel to each pixel you are checking. The longest line that does not intersect any of the line segments of your polygon indicates your most distant pixel that is reachable by a straight line from your pixel.

There are various optimizations you can make to this and a few edges cases to check, but let me know if you understand the idea before i post those... in particular, do you understand what I mean by treating as a polygon instead of a collection of pixels?

To add, this approach will be significantly faster than any angle based approach or approach that requires "walking" for all but the smallest collections of pixels. You can further optimize because your problem is equivalent to finding the most distant endpoint of a polygon edge that can be reached via an unintersected straight line from your start point. This can be done in O(N^2), where N is the number of edges. Note that N will be much much smaller than the number of pixels, and many of the algorithms proposed that use angles an/or pixel iteration are be going to instead depend on the number of pixels.

Answer 2

Use a double data-structure:

• One that contains the pixels sorted by angle.
• The second one sorted by distance (for fast access, this should also contain "pointers" for the first data structure).

Walk through the angle sorted one, and check for each pixel that the line is within the region. Some pixels will have the same angle, so you can walk from the origin along the line, and go till you go out from the region. You can eliminate all the pixels which are beyond that point. Also, if the maximum distance increased, remove all pixels which have a shorter distance.

Answer 3

I wouldn't work with angles. But I'm pretty sure the largest distance will always be between two pixels at the edge of the set, thus I'd trace the outline: From any pixel in the set go to any direction until you reach the edge of the set. Then move (couter)clockwise along the edge. Do this with any pixel as starting point and you'll be able to find the largest distance. It's still pretty greedy, but I thought it might give you an alternative starting point to improve upon.

Edit: What just came to my mind: When you have a start pixel s and the end pixel e. In the first iteration using s the corresponding e will be adjacent (the next one along the edge in clockwise direction). As you iterate along the edge the case might occur, that there is no straight line through the set between s and e. In that case the line will hit another part of the set-edge (the pixel p) though. You can continue iteration of the edge at that pixel (e = p)

Edit2: And if you hit a p you'll know that there can be no longer distance between s and e so in the next iteration of s you can skip that whole part of the edge (between s and p) and start at p again.

Edit3: Use the above method to find the first p. Take that p as next s and continue. Repeat until you reach your first p again. The max distance will be between two of those p unless the edge of the set is convex in which case you wont find a p.

Disclaimer: This is untested and are just ideas from the top of my head, no drawings have been made to substantiate my claims and everything might be wrong (i.e. think about it for yourself before you implement it ;D)

Answer 4

Search for pixel, not for slope. Pseudocode.

bestLength = 0
for each pixel in pixels
  currentLength = findDistance(x, y, pixel.x, pixel.y)
  if currentLength > bestLength
    if goodLine(x, y, pixel.x, pixel.y)
      bestLength = currentLength
      bestX = pixel.x
      bestY = pixel.y
    end
  end
end

You might want to sort pixels descending by |dx| + |dy| before that.

Answer 5

First, note that the angle discretization in your algorithm may depend on the size of the grid. If the step is too large, you can miss certain cells, if it is too small, you will end up visiting the same cell again and again.

I would suggest that you enumerate the cells in the region and test the condition for each one individually instead. The enumeration can be done using breadth-first or depth-first search (I think the latter would be preferable, since it will allow one to establish a lower bound quickly and do some pruning).

One can maintain the farthest point X found so far and for each new point in the region, check whether (a) the point is further away than the one found so far and (b) it's connected to the origin by a straight line passing through the cells of the region only. If both conditions are satisfied, update the X, else go on with the search. If condition (a) is not satisfied, condition (b) doesn't have to be checked.

The complexity of this solution would be O(N*M), where N is the number of cells in the region and M is the larger dimension of the region (max(width,height)). If performance is of essence, more sophisticated heuristics can be applied, but for a reasonably sized grid this should work fine.