5

Point というオブジェクトの配列があるとします。
Point オブジェクトには x 値と y 値があります。

さらに難しくするために、最初の境界がないとします。これは、見つけたい長方形の領域が Point オブジェクトによって囲まれていることを意味します。したがって、少なくとも 4 つの Point オブジェクトがあります。

したがって、配列に Point オブジェクトが 4 つしかない場合: Point(0,0)、Point(100,0)、Point(0,100)、および Point(100,100) の場合、長方形の領域である 100*100 を返します。

これは簡単な部分です。しかし、4 つ以上の Point オブジェクトがある状況を考えてみてください。長方形の最大面積を求めるにはどうすればよいですか? 

public int maxArea(Point[] points)
{
    int area;
    //do algo
    return area;
}

編集: y と x の最小値と最大値を見るだけでは保証されません。なぜなら、私は Point オブジェクトのない長方形の領域を探しているからです。したがって、その最大の長方形領域内には何もありません

4

5 に答える 5

3

最初に問題を定式化させてください。

  • 検出される長方形には、水平 (定数 y) と垂直 (定数 x) の境界線があります。つまり、「回転」はありません。

  • 長方形には、各辺の「内部」(「開いた」) 部分、つまり角ではない部分に少なくとも 1 つの点があります。(任意のエッジに複数のポイントがあり、そのコーナーにもポイントがある場合があります。) すべてのポイントが有限の x、y を持つため、これは「無限」の解を除外します。また、TopLeft と BottomRight のポイントおよび類似の構造のみによって長方形を定義することを意図している場合も除外されます。

  • 上記の条件を満たすすべての長方形の中で最大の面積を持つ長方形を探します。

上記が問題の正しい（再）定式化であると仮定すると、それは潜在的に多くの「ローカル」最適化を伴う2次元最適化問題であると私は信じています。「何かから始めて徐々に改善する」タイプのアプローチは、局所的な最適を見つけるだけで、必ずしも全体的な最適を見つけるとは限りません。

私は、O(N^2) アプローチよりも優れたものを思いつくことができませんでした。大まかに言えば、各ローカル最適化が O(N) である N 回のローカル最適化を含みます。ローカル最適化の本質的な部分について、いくつかのコード スニペット (部分的に疑似コードまたは注釈) を使用してメソッドをスケッチします。残りは「ほぼ同じ」であり、記入するのは難しくありません。

不正確になることなく言葉遣いを減らすために、今後、「(長方形の) エッジ上の点」とは、角ではなく、エッジの「内側」部分にある点を意味します。同様に、「長方形」とは、「適格な」反応角を意味します。つまり、内部に点がなく、各端に少なくとも 1 つの点があるという基本的な条件を満たすものです。

現在、LOCAL 最適化は、{Left, Top, Right, Bottom} の特定の「border-type」と組み合わせて、ポイント セットの特定のポイントによって「定義」されています。点 L と境界タイプ「左」を選択したと仮定します。局所的に最適な解は、左端に L を持つ「最良の」(最大面積) 長方形として定義されます。

すべての (L,Left) 長方形を作成し、途中で見つけた最大のものを追跡します。

観察: 右の境界線に点 R を持つ任意の (L,Left)-長方形は、その上の境界線に点 T とその下の境界線に点 B を持たなければなりません。ここで、

L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y

ここで、L の後に開始して x 順序でポイントをスキャンすることをイメージしてください。

一方では、R を見つける前に、上記の条件は、最初に T と B に遭遇する必要があることを示しています。

一方、その間に遭遇した y > Ly のすべてのポイントから R を見つけるとすぐに、y が最小のポイントに制限されます。下枠についても同様です。

N をポイント {P} の数として、i がj未満。

さらに、x ソートされた配列内の L のインデックスを iL とします: P[index_X[iL]] = L.

次のコード スニペット (VB 構文。使用する言語に翻訳するのはそれほど難しくないはずです) では、最初に「いくつかの」T (上端の点) と「いくつかの」B (下端の点) を決定します。エッジポイント)。次に、スキャンを続け、長方形を完成させる点 R を見つけるたびに、次のことを行います。(b) T または B を見つかった R で置き換え (R が L の上か下かに応じて)、R の検索を繰り返します。

    Dim indx As Integer = iL + 1 'first point to consider on the right of L
    Dim T As PointF = Nothing
    Dim B As PointF = Nothing
    ' find T,B
    While (indx < N AndAlso (T = Nothing OrElse B = Nothing))

      Dim Q As PointF = Pts(indx_X(indx))

      If (Q.Y > L.Y) Then
        ' a candidate for T
        If (T = Nothing) OrElse (Q.Y < T.Y) Then
          T = Q
        End If

      ElseIf (Q.Y < L.Y) Then
        ' a candidate for B
        If (B = Nothing) OrElse (Q.Y > B.Y) Then
          B = Q
        End If

      Else
        Return -1 'Failure for L altogether: Q has exactly the same y-value as L and we didn't find yet both T and B.
      End If

      indx += 1
    End While

    If (T = Nothing OrElse B = Nothing) Then
      Return -1  'Failure for L: we have exhausted all points on the right without finding both T and B.
    End If

    ' we have "some" T and B, now proceed to find all (L,Left) rectangles
    ' intialize result (= max area from (L,Left)-rectangles).
    Dim result As Double = -1
    ' the next point to consider
    indx += 1
    ' find successive rectangles, by searching for R, given L (fixed) and T,B (occasionally updated). 
    While (indx < N)

      Dim R As PointF = Pts(indx_X(indx)) 'candidate

      If (R.Y = L.Y) Then
        ' rectangle found, process it.
        Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
        If area > result Then
          result = area
        End If
        ' it all stops here: no further rectangles {L,Left) are possible as they would have this R inside.
        Exit While
      End If

      If (R.Y > L.Y) Then
        ' a point with y > L.Y:
        ' if it is above T we can ignore it.
        ' if is below T, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y < T.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the upperbound.
          T = R
        End If

      Else 'R.Y < L.Y
        ' a point with y < L.Y
        ' if it is below B we can ignore it.
        ' if it is above B, it is the R-bound for the rectangle bounded by L,T,B
        If (R.Y > B.Y) Then
          ' process the rectangle
          Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
          If area > result Then
            result = area
          End If
          ' move on, understanding that for any NEXT rectangle this R must be the lowerbound.
          B = R
        End If

      End If

      indx += 1
    End While

    Return result

もちろん、全体的な解決策は次のとおりです。各点 P について、opt(P,Left)、opt(P,Right)、opt(P,Top)、opt(P,Bottom) の中から最適なものを見つけ、次に最大値を見つけます。 Right、Top、Bottom のバリエーションは、もちろん、上でスケッチした opt(Left) と非常によく似ています。事前ソート (x オーダーと y オーダー ((P,Top) および (P,Bottom) ケースを処理するための) のインデックスを取得するため) は O(nLogn) であり、ローカル最適化はそれぞれ O(n) です。 - コードを見る 全体的な複雑さは O(n^2) です。

注が追加されました-元の定式化は私には完全に明確ではなかったので: IF 長方形は CORNER-points によっても囲まれる可能性があるため、上記はいくつかの小さな調整 (主に不等式条件に等号を追加する) が必要ですが、本質的にアルゴリズム。

于 2012-10-20T19:50:47.907 に答える
2

私はでこれを行うことができますO(N^2*Log(N))。

最初にすべてのポイントをセットに入れて、ポイントが に存在するかどうかを確認できるようにしO(Log(N))ます。

対角線上の 2 点を列挙し、それが必要O(N^2)な場合は長方形を決定し、他の 2 点が存在するかどうかを確認し、それを取得できるかどうかを確認します。取得した場合は、答えを更新します。

于 2012-10-20T16:14:43.280 に答える
1

4点は絶対に必要です。
長方形を形成する topLeft と bottomRight のポイントを見つけます。
配列をループして、これらの 2 つのポイントを追跡/更新します。
ループから抜けたら、(topLeft.x - bottomRight-x)*(topLeft.y - bottomRight-y); を返します。

どうぞ

于 2012-10-20T04:51:55.497 に答える
0

これを行う最も簡単な方法は、while ループですべての可能な領域を計算し、最後に最大のものを取得することです。

于 2012-10-20T04:37:49.803 に答える