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

Question

我的意思是"Group"是指一组像素，使得每个像素至少在同一组中有一个相邻像素。下图展示了一个组的例子。 我想找到距离指定像素（例如绿色像素）最远的像素。连接两个像素的直线（红线）不能离开该组。

我的解决方案是遍历角度并模拟从绿色像素开始沿着该角度的直线的进程，看哪条直线行进的距离最远。

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

显然这不是最好的算法。因此我在这里请求帮助。

谢谢，对我的英语表示歉意。

- Raytheon

---

请注意，您可以放弃所有内部像素的计算。 - dfens

你不需要使用角度，只需要使用勾股定理就可以了;) - dfens

@dfens: “内部像素” - 为什么？其中一个可能是解决方案。 - Karoly Horvath

@Karoly Horvath：我理解问题是我们正在寻找两个最远的像素？所以内部像素不是解决方案？ - dfens

Answer 1

我不会使用角度。但我很确定最大距离总是在集合边缘的两个像素之间，因此我会追踪轮廓：从集合中的任何像素开始，沿着任意方向前进，直到达到集合的边缘。然后顺时针（或逆时针）沿着边缘移动。以任何像素为起点重复此过程，您将能够找到最大距离。这仍然相当贪婪，但我认为它可能会给您提供一个改进的替代起点。

编辑：我想到了一件事：当您有一个起始像素s和结束像素e时。在使用s进行第一次迭代时，相应的e将是相邻的（沿顺时针方向的下一个）。随着您沿着边缘迭代，可能会出现这种情况，即在s和e之间没有直线穿过集合。在这种情况下，该线将击中集合边缘的另一部分（像素p）。您可以在该像素处继续迭代边缘（e = p）

编辑2：如果你碰到p，你就会知道s和e之间的距离不能再长了，所以下一次s的迭代中，你可以跳过整个边缘（s和p之间）并从p重新开始。

编辑3：使用上述方法找到第一个p。将该p作为下一个s并继续。重复直到再次到达您的第一个p。最大距离将在这些p之间的两个位置之间，除非集合的边缘是凸面的，在这种情况下，您将找不到p。

免责声明：这是未经测试的，仅是我脑海中的想法，没有进行任何绘图来证实我的说法，一切可能都是错误的（即在您实施之前，请自己考虑）;D）

- Mene

Answer 2

寻找像素，而不是斜率。伪代码。

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

在此之前，您可能希望按|dx| + |dy|对像素进行降序排序。

- iced

---

这并不处理连接线必须保持在区域内的要求。 - davec

Answer 3

将您的区域视为多边形而不是像素集合。从这里，您可以获得线段列表（多边形的边缘）。

从起始像素到每个要检查的像素绘制一条线。最长的线不与多边形的任何线段相交，表示您可以通过直线从您的像素到达的最远像素。

有各种优化可以应用于此，并且需要检查一些边缘情况，但在我发布这些内容之前，请让我知道您是否理解了这个想法...特别是，您是否理解我所说的将其视为多边形而不是像素集合的含义？

此外，除了最小的像素集合外，此方法将比任何基于角度或需要“行走”的方法快得多。您可以进一步优化，因为您的问题等效于找到可以通过未相交的直线从起点到达的多边形边缘的最远端点。这可以在O（N ^ 2）中完成，其中N是边数。请注意，N将比像素数量小得多，提出的许多使用角度和/或像素迭代的算法将取决于像素数量。

- davec

Answer 4

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

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

可以维护到目前为止找到的最远点X，并针对该区域中的每个新点检查以下内容：（a）该点是否比迄今为止找到的点更远，以及（b）它是否通过仅穿过该区域的单元格与原点相连。如果两个条件都满足，则更新X，否则继续搜索。如果未满足条件（a），则无需检查条件（b）。

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

- Qnan

Answer 5

使用双重数据结构：

• 一个按角度排序的像素数据结构。
• 第二个按距离排序的数据结构（为了快速访问，它还应该包含指向第一个数据结构的“指针”）。

遍历按角度排序的数据结构，并检查每个像素是否在区域内。有些像素会有相同的角度，因此您可以沿着线从原点开始走，直到超出区域为止。您可以消除所有超过该点的像素。同时，如果最大距离增加，则删除所有距离更短的像素。

- Karoly Horvath