すべての矩形の面積を求めるアルゴリズム

-1

四点の形で四角形を得るとしましょう：その（x1、y1）、...、（x4、y4）私たちはそれらがカバーする総面積を計算したいと思います。総面積を数えたいと思っていますが、矩形が重なっている場合は、このエリアを1回だけカウントします。すべての矩形の面積を求めるアルゴリズム

私は実際に完成した解決策、擬似コード、またはアルゴリズムとデータ構造へのリンクを探していません。ここで役に立つと思います。

矩形の形式は、左の位置、右の位置と高さの3つの整数で与えられます。例えば：

L：0 R：2 H 2

L：1 R：3 H：3

L：-1 R：4 H：1

総面積希望x軸の最大値は-1e9から1e9まで、x = Lから始まりx = Rで終わり yは0より小さくなることはできず、常にy = 0から始まり、y = 0で終わります。 H

出典

2017-11-12 Raxume

。 –

あなたの質問は明確ではない、四角形の離散化または何について話していますか？一般に、矩形R1が** x11、y11、x12、y12およびR2x21、y21、x22、y22の座標を有する場合、それらが重複する場合（x21

すべての長方形が軸に整列していますか（y1 = y2; y3 = y4; x2 = x3およびx1 = x4）？多くの長方形がありますか？次に、座標圧縮による簡単なブロック充填が有用な場合があります。 –

これらの長方形は、y = 0の底辺を持ちますか？私はそれが本当であると仮定しています。したがって、これらは遠くから見た都市の建物のようです。あなたはスカイラインをトレースしようとしています。

配列インデックスを一意のIDとして使用できるように、矩形を1つの配列に格納します。それぞれの左と右の長方形のエッジを、それが属する矩形のIDと対応するエッジのx座標を含む「イベント」として表現します。すべてのイベントをリストELに入れ、x座標で並べ替えます。最後に、対応する四角形の高さが降順でソートされた矩形IDの動的にソートされたセット（Java TreeSetなど）が必要です。それはSLと呼ばれ、「スイープライン」です。 SL.firstはソートされているため、常にSLによって現在参照されている最も高い矩形のIDです。

次のように今、あなたは、長方形のコレクションの輪郭を描くことができます：

SL = <empty> // sweep line 
x0 = EL.first.left // leftmost x among all rectangle edges 
lastX = x0 
for each event E in EL // process events left-to-right 
    Let y0 = if SL.isEmpty then 0 else SL.first.height // current y 
    if E.ID in SL // event in SL means sweep line is at rectangle's right edge 
    remove E.ID from SL 
    else // event means sweep line is a new rectangle's left edge 
    add E.ID to SL 
    Let y1 = if SL.isEmpty then 0 else SL.first.height // new y 
    if y1 != y0 
    output line seg (lastX, y0) -> (E.x, y0) 
    output line seg (E.x, y0) -> (E.x, y1) 
    lastX = E.x 
output final line seg (lastX, 0) -> (x0, 0)

を、これは宿題または多分面接の質問のように聞こえるので、私はあなたがの面積を提供するために、このアルゴリズムを修正してもらおうそのエッジを描くのではなく、掃き出された形になります。

楽しみのためだけに

追加：この質問は[**数学StackExchange **]（https://math.stackexchange.com/）のためのより適切かもしれ

import java.util.ArrayList; 
import static java.lang.Integer.compare; 
import static java.util.Arrays.stream; 
import static java.util.Collections.sort; 
import java.util.Comparator; 
import java.util.List; 
import java.util.SortedSet; 
import java.util.TreeSet; 

class SkyLine { 
    static class Rectangle { 
    final int left; 
    final int right; 
    final int height; 
    Rectangle(int left, int right, int height) { 
     this.left = left; 
     this.right = right; 
     this.height = height; 
    } 
    } 
    static class Event implements Comparable<Event> { 
    final int x; 
    final int id; 
    public Event(int x, int id) { 
     this.x = x; 
     this.id = id; 
    } 
    @Override 
    public int compareTo(Event e) { return compare(x, e.x); } 
    } 

    final List<Rectangle> rectangles = new ArrayList<>(); 
    final Comparator byHeightDescending = 
     (Comparator<Integer>) (Integer a, Integer b) -> 
      compare(rectangles.get(b).height, rectangles.get(a).height); 
    final SortedSet<Integer> scanLine = new TreeSet<>(byHeightDescending); 
    final List<Event> events = new ArrayList<>(); 

    SkyLine(Rectangle [] data) { 
    stream(data).forEach(rectangles::add); 
    int id = 0; 
    for (Rectangle r : rectangles) { 
     events.add(new Event(r.left, id)); 
     events.add(new Event(r.right, id)); 
     ++id; 
    } 
    sort(events); 
    } 

    int area() { 
    int area = 0; 
    Event ePrev = null; 
    for (Event e : events) { 
     if (ePrev != null) area += (e.x - ePrev.x) * rectangles.get(scanLine.first()).height; 
     if (!scanLine.remove(e.id)) scanLine.add(e.id); 
     ePrev = e; 
    } 
    return area; 
    } 

    public static void main(String [] args) { 
    Rectangle [] data = { 
     new Rectangle(0, 2, 2), 
     new Rectangle(1, 3, 3), 
     new Rectangle(-1, 4, 1), 
    }; 
    int area = new SkyLine(data).area(); 
    System.out.println(area); 
    } 
}

出典

2017-11-12 21:30:03 Gene

あなたは正しいです、私はスカイラインをトレースしようとしていると言っても十分でした。ありがとうございました！ – Raxume