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 に答える