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

Question

By “Group” I mean a set of pixels, so that each pixel has at least one adjacent pixel in one set, the drawing shows an example of a group.

I would like to find the pixel that has the largest direct distance from the specified pixel (e.g. green pixel). And the straight line connecting the two pixels (red line) should not leave the group.

My solution is looped in degrees and simulates the course of lines, starting with a green pixel with a degree and seeing which line passed over a long 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 

This is obviously not the best algorithm. So I ask for help here.

Thank you and sorry for the bad English.

Answer 1

I would not work with corners. But I'm sure that the greatest distance will always be between two pixels on the edge of the set, so I would follow the pattern: from any pixel in the set, go in any direction until you reach the edge of the set. Then move (offset) clockwise along the edge. Do this with any pixel as a starting point, and you can find the greatest distance. This is still pretty greedy, but I thought it might give you an alternative starting point for improvement.

Edit: what occurred to me: when you have the starting pixel s and the ending pixel e . In the first iteration using s corresponding e will be adjacent (next clockwise along the edge). When repeating along the edge, a case may arise that there is no straight line through the set between s and e . In this case, the line will hit another part of the set point (pixel p ). You can continue the iteration of the edge in this pixel ( e = p )

Edit2: If you press p , you will find out that the distance between s and e cannot be greater, so in the next iteration s you can skip all this part of the edge (between s and p ) and start again with p .

Edit3: Use the above method to find the first p . Take this p as the next s and continue. Repeat until you reach your first p again. The maximum distance will be between two of them p , unless the edge of the set is convex, in which case you will not find p .

Disclaimer: this is untested and it’s just ideas from the head, no drawings were made to justify my statements, and everything may be wrong (i.e. think about it for yourself before implementing it; D)

Answer 2

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

I would suggest that you list the cells in the region and check the condition for each separately. Enumeration can be done using a search by width or depth (I think the latter would be preferable, since this will allow you to quickly set the lower border and do some cropping).

You can maintain the farthest point X found so far, and for each new point in the region, check (a) a point farther than the one that has been found so far, and (b) it is connected with the beginning of a straight line passing through cells only areas. If both conditions are met, update X, otherwise continue the search. If condition (a) is not satisfied, condition (b) does not need to be checked.

The complexity of this solution will be O(N*M) , where N is the number of cells in the region, and M is the larger size of the region ( max(width,height) ). If performance is an entity, more complex heuristics can be applied, but for a grid with a reasonable size this should work fine.

Answer 3

Search for a pixel, not for tilt. 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 can sort the pixels descending | dx | + | dy | before.

Answer 4

Use a double data structure:

• One that contains pixels sorted by angle.
• Second sorting by distance (for quick access, this should also contain “pointers” for the first data structure).

Go through sorted by angle and check each pixel that the line is inside the area. Some pixels will have the same angle, so you can go from the beginning along the line and go until you exit the region. You can exclude all pixels that are outside this point. In addition, if the maximum distance is increased, delete all pixels with a shorter distance.

Answer 5

Think of your region as a polygon, not a set of pixels. From this you can get a list of line segments (the edges of your polygon).

Draw a line from your starting pixel to each pixel that you are checking. The longest line that does not intersect any of the line segments of your polygon indicates your farthest pixel, accessible in a straight line from your pixel.

There are various optimizations you can do for this, and a few cases for checking the edges, but let me know if you understand the idea before I publish them ... in particular, you understand what I mean by considering how is a polygon instead of a set of pixels?

To add, this approach will be significantly faster than any angle-based approach that requires a “walk” for all but the smallest sets of pixels. You can further optimize, because your problem is equivalent to finding the farthest endpoint of the edge of the polygon, which can be achieved with a disjoint straight line from your starting point. This can be done in O (N ^ 2), where N is the number of edges. Please note: N will be much smaller than the number of pixels, and many of the proposed algorithms that use pixel iteration angles will depend on the number of pixels.