如何在同一像素组中找到距离另一个像素最远的像素

Question

"组"是指一组像素,使得每个像素至少在同一组中具有一个相邻像素,该图示出了组的示例.

我想找到与指定像素(例如,绿色像素)具有最大直线距离的像素.并且连接两个像素的直线(红线)不得离开该组.

我的解决方案是循环度数并模拟从绿色像素开始的线条的进度,并查看哪条线走过最远的距离.

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

它显然不是最好的算法.因此,我在这里寻求帮助.

谢谢你,对不起我的英语不好.

Answer 1

首先，请注意，算法中的角度离散可能取决于网格的大小。如果步长太大，您可能会错过某些单元格，如果太小，您最终将一次又一次访问同一个单元格。

我建议您枚举该区域中的单元格并单独测试每个单元格的条件。枚举可以使用广度优先或深度优先搜索来完成（我认为后者更好，因为它允许快速建立下界并进行一些修剪）。

人们可以维护迄今为止找到的最远点 X，并且对于该区域中的每个新点，检查 (a) 该点是否比迄今为止找到的点更远，以及 (b) 它通过一条穿过的直线连接到原点仅该区域的单元格。如果两个条件都满足，则更新 X，否则继续搜索。如果不满足条件(a)，则不必检查条件(b)。

该解决方案的复杂度为O(N*M)，其中N是该区域中的单元数量，M是该区域的较大尺寸 ( max(width,height))。如果性能至关重要，则可以应用更复杂的启发式方法，但对于合理大小的网格，这应该可以正常工作。