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

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)