0

是否有一种算法可以找到彼此之间具有一定距离的所有点？还是所有接触的矩形？

我将平面（在纬度/经度坐标系中，具有一定的限制）划分为 nxn 的样本矩形，每个矩形得到一个从 0 到 7 的值。我需要能够为每个值显示岛屿。n > 100 - 可能是 15000。

我写了一些非常蛮力的代码，但我只设法得到了一些非常粗糙的矩形......

我的输入示例：

111111111111111122222111
111221122222111122211111
111222222222111112211111
111222222111111112211111
111221111113311112111111
111111111113311111111111

以上，使用矩形中的点定义（每个 1 和 2 以及其他是我通过一些采样获得的矩形......） - 我最终有几千个 - 可能是十万个小矩形，我想得到每种区域。

我发现我可以使用凸包算法获得区域 - 如果我可以正确地将矩形（或它们的中心点）分成区域。

在我的函数的输入中，我只会得到具有相同度量的矩形。

例子：

1111111111111111     111
111  11     1111   11111
111         11111  11111
111      11111111  11111
111  111111  1111 111111
11111111111  11111111111


                22222
   22  22222    222
   222222222     22
   222222        22
   22            2

我想找到一些算法，这样我就可以在单独的集合中获得正在接触的矩形，或者彼此相距一定距离的点（它们具有绝对坐标），这样我就可以在结果集。

由于矩形是通过采样创建的，因此它们的宽度/高度相同。

有这样的事吗？

我的代码在 VB.NET 中，但 C# 或任何语言或伪代码都会有所帮助。

非常感谢你。

编辑：

我有各种各样的测试，比如

Public Function AreTwoRectanglesNearEachOther(ByRef one As RectangleF, ByRef two As RectangleF) As Integer
        If Math.Abs(one.Right - two.Left) <= distance_lat Then
            Return 1    ' one is before two
        ElseIf Math.Abs(two.Right - one.Left) <= distance_lat Then
            Return -1   ' one is after two
        ElseIf Math.Abs(two.Top - one.Bottom) <= distance_lon AndAlso one.Right - two.Left > 0 Then
            Return 2    ' one is above two
        ElseIf Math.Abs(one.Top - two.Bottom) <= distance_lon AndAlso one.Right - two.Left > 0 Then
            Return -2   ' one is below two
        Else
            Return 0    ' they are not next to each other
        End If
    End Function

其中 distance_lat 和 distance_lon 是 dim_lat/10，分别是 dim_lon/10

4

1 回答 1

0

谢谢 mmgp - 我确实实现了连接组件标记算法 - 这是一个绝妙的主意。

于 2013-03-28T16:35:31.833 回答