境界は

Question

が、私はこの問題を解決するための効率的な方法を知りたいの長方形：

、左上と右下の隅を与えられたN個の長方形を考えると、の周囲を見つけてくださいN個の矩形の和集合。

私はO(N^2)アルゴリズムを持っており、それはあまりにも遅いですので、より効率的なアルゴリズムを見つけてください。

あなたはその座標値は正の整数未満100000

EDITされると仮定することができる。例えば、この場合には、周囲が30

アンO（N あります^ 2）アルゴリズム：

for x=0 to maxx 
    for i=0 to N 
     if lowx[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]++ 
      if d[j] = 1 then ret++ 
     if highy[i] = x 
     for j=lowy[i] to highy[i] 
      d[j]-- 
      if d[j] = 0 then ret++ 
    for y=0 to maxy 
     if d[y] = 0 && d[y + 1] >= 1 then ret++ 
     if d[y] >= 1 && d[y + 1] = 0 then ret++ 

最後のretが答えです。

Answer 1

一方、この問題の古典的な解決法は、元の形でこれらの矩形の和集合を構築する、すなわち結果の多角形境界を構築するスイープラインベースの「ブールマージ」アルゴリズムである。このアルゴリズムは、物理的に構築することなく、結果として生じる境界の周囲を計算するように容易に修正することができる。

一方、掃引線ベースの「ブールマージ」は、任意のポリゴン入力に対してこれを行うことができます。あなたのケースでは、入力がはるかに制限されている（単純化されている）ことを考えれば、より多くの軽量で賢明なソリューションが存在する可能性は非常に高いです。

このような矩形の和集合は、実際には複数の接続されたポリゴン、つまりその中に穴がある領域である可能性があります。

Answer 2

これはあなたの問題のいくつかのケースで役立つかもしれない：

_________ 
|   | 
|   | 
|   | 
|   | 
|   | 
|_________| 

Answer 3

ありOだ（N Nを記録：

は、この、

_______ 
|  |_ 
|   | 
|  _| 
|___ | 
    | | 
    |___| 

は、これと同じ周囲長を持つことを考えてみましょう）タイムスイープラインアルゴリズム。形状の垂直周囲を計算するには、次の手順を実行します。入力を転置して再度適用し、水平周囲を計算します。

各矩形に対して、値がy間隔である左のx座標と、その値がy間隔である右のx座標でキーされる停止イベントとをキーとする開始イベントを準備する。これらのイベントをx座標でソートし、順番に処理します。常に、境界線がスイープラインと交差する点の数を報告できるデータ構造を維持しています。イベントポイント間の2n - 1の間隔で、この数を間隔の幅と周囲の長さの積として加算します。

私たちが必要とするデータ構造は、時間O（log n）において以下の操作をサポートします。

insert(ymin, ymax) -- inserts the interval [ymin, ymax] into the data structure 
delete(ymin, ymax) -- deletes the interval [ymin, ymax] from the data structure 
perimeter() -- returns the perimeter of the 1D union of the contained intervals 

入力座標は有界の整数なので、考えられる実装の1つはsegment treeです。 （入力のy座標をソートし、小さい整数にそれらを再マッピングすることを含む実際の入力への拡張があります。）各セグメントは、いくつかの関連するデータを有する

そのスコープセグメントの組合であることがそれから下降さ

struct { 
    int covers_segment; 
    bool covers_lower; 
    int interior_perimeter; 
    bool covers_upper; 
}; 

入力間隔に存在する。 （非常に長いセグメントがツリーの最下位レベルに影響を与えないことに注意してください。）

covers_segmentの意味は、このセグメントが分解に含まれる間隔の数です。 covers_lowerの意味は、同じ下端点を持つこのセグメントの下位のセグメントの1つがある区間の分解に属する場合は真です。 interior_perimeterの意味は、（上記のように）範囲内のセグメントの1D境界です。 covers_upperの意味は、covers_lowerに似ていますが、上位のエンドポイントがあります。

例を示します。

0 1 2 3 4 5 6 7 8 9 

[---A---] 
    [---B---] [-D-] 
     [-C-] 

間隔はA ([0, 4])とB ([2, 4], [4, 6])とC [3, 4] [4, 5]とD [7, 8] [8, 9]です。 （デクリメント）covers_segmentを増分することによって、その構成セグメント（削除）（削除）インターバルを挿入する挿入する

   c_s c_l i_p c_u 
[0, 1]   0 F 0 F 
    [0, 2]  0 F 0 F 
[1, 2]   0 F 0 F 
    [0, 4]  1 T 0 T 
[2, 3]   0 F 0 F 
    [2, 4]  1 T 1 T 
[3, 4]   1 T 0 T 
     [0, 8] 0 T 2 F 
[4, 5]   1 T 0 T 
    [4, 6]  1 T 1 T 
[5, 6]   0 F 0 F 
    [4, 8]  0 T 2 F 
[6, 7]   0 F 0 F 
    [6, 8]  0 F 1 F 
[7, 8]   1 T 0 T 
     [0, 9] 0 T 2 T 
[8, 9]   1 T 0 T 

。次に、影響を受けたセグメントのすべての祖先について、以下のように他のフィールドを再計算します。

if s.covers_segment == 0: 
    s.covers_lower = s.lower_child.covers_lower 
    s.interior_perimeter = 
     s.lower_child.interior_perimeter + 
     (1 if s.lower_child.covers_upper != s.upper_child.covers_lower else 0) + 
     s.upper_child.interior_perimeter 
    s.covers_upper = s.upper_child.covers_upper 
else: 
    s.covers_lower = true 
    s.interior_perimeter = 0 
    s.covers_upper = true 

rootは、セグメントツリーのルートである

(1 if root.covers_lower else 0) + 
root.interior_perimeter + 
(1 if root.covers_upper else 0) 

を返す、perimeterを実装すること。