6

“组”是指一组像素，使得每个像素在同一组中至少有一个相邻的像素，该图显示了组的示例。

组的一个例子

我想找到与指定像素（例如绿色像素）具有最大直线距离的像素。并且连接两个像素的直线（红线）不能离开该组。

我的解决方案是循环遍历度数并模拟从带有度数的绿色像素开始的线条的进度，并查看哪条线行进的距离最远。

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

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

谢谢你，对我糟糕的英语感到抱歉。

4

5 回答 5

1

我不会使用角度。但我很确定最大的距离总是在集合边缘的两个像素之间，因此我会追踪轮廓：从集合中的任何像素到任何方向，直到到达集合的边缘。然后沿边缘顺时针移动（向外）。以任何像素为起点执行此操作，您将能够找到最大距离。它仍然很贪婪，但我认为它可能会给你一个可供改进的替代起点。

编辑：我刚想到什么：当你有一个 start pixels和 end pixel e。在第一次迭代中使用s相应的e将是相邻的（下一个沿顺时针方向的边缘）。s当您沿边缘迭代时，可能会发生这种情况，即和之间的集合没有直线e。在这种情况下，这条线会碰到设置边缘的另一部分（像素p）。您可以在该像素处继续迭代边缘 ( e = p)

编辑2：如果你击中 ap你会知道和之间不再有距离s，e所以在下一次迭代中s你可以跳过边缘的整个部分（在s和之间p）并重新开始p。

Edit3：使用上面的方法找到第一个p. 将其p作为下一步s并继续。重复直到你p再次达到你的第一个。最大距离将在其中两个之间，p除非集合的边缘是凸的，在这种情况下你不会找到p.

免责声明：这是未经测试的，只是我头脑中的想法，没有绘制任何图纸来证实我的主张，一切都可能是错误的（即在实施之前自己考虑一下；D）

于 2012-09-20T10:13:24.070 回答
0

搜索像素，而不是坡度。伪代码。

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| 在那之前。

于 2012-09-20T10:11:52.510 回答
0

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

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

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

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

于 2012-09-20T10:05:24.573 回答
0

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.

于 2012-11-07T18:32:18.747 回答
0

使用双重数据结构：

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

遍历排序为 1 的角度，并检查线在该区域内的每个像素。一些像素将具有相同的角度，因此您可以从原点沿着线走，直到您离开该区域。您可以消除超出该点的所有像素。此外，如果最大距离增加，则删除所有距离较短的像素。

于 2012-09-20T10:49:12.307 回答