兩個多邊形之間的重疊檢查

Question

我有一個使用HTML5畫布（GWT）的兩個多邊形形狀繪製。我有兩個多邊形形狀的所有點。意味着我有繪製這種類型的多邊形的點列表。

下圖顯示兩個多邊形相互交叉或重疊。現在我正在尋找一個解決方案如何使用java找到兩個「相交或不相交」多邊形？我使用純Java編程而不使用任何第三個庫。

我有另外一個問題。爲了解釋這個問題，我在下面附上另一張圖片。

這是另一種情況下，當另一多邊形的內部的一個多邊形。在這種情況下如何計算兩個多邊形之間的最小距離爲負？

Answer 1

使用Postgis Api使用您可以獲得兩個多邊形相交或不相交的信息。查找以下鏈接作爲參考 http://www.postgis.net/docs/ST_Intersection.html

Answer 2

您可以使用sweepline範例。

考慮水平線穿過任一多邊形的頂點。連續兩行切出厚片（梯形）。

由於板坯是簡單的，凸多邊形，檢查它們交集是直接的：它足以檢測鹼基（在那裏它們形成X橫介意的情況下）的重疊。

現在整個過程可以分解爲

• 通過增加座標排序兩個多邊形的頂點;對於每個頂點，請記住它屬於哪個多邊形，以及它的鄰居有多少個縱座標（無，一個或兩個）;

• 通過增加縱座標，同時保持相交邊緣的列表掃描頂點（它被稱爲活動列表）。每次移動到另一個頂點時，更新活動列表;

• 相交測試的板坯。