用於確定兩個凹多邊形之間的成對可見邊的算法

假設我們有兩個不相交的凹2d多邊形（A，B）。問題是要找到一組邊緣對（每對包含多邊形A的一條邊和多邊形B的邊），它們具有以下屬性：成對中的每個項必須彼此可見。如果沒有任何障礙物（圖中有三個案例，標有紅色十字，這條規則被打破時），則一條邊對另一條邊是可見的。用於確定兩個凹多邊形之間的成對可見邊的算法

enter image description here

我知道如何使用光線和邊緣的頂點爲O解決這個問題（N^2）。但它太慢了。

2012-03-15 innochenti

每對邊形成一個四邊形。本質上，你需要找出是否有其他邊緣與四邊形相交。 – 2012-03-15 13:37:59

蠻力算法將是O（n^3）：對於每一對，再次通過邊緣來查看該邊緣是否阻塞。你是如何得到O（n^2）的？ – 2012-03-15 14:11:11

這看起來像是美術館問題的變體，http://en.wikipedia.org/wiki/Art_gallery_problem可能會給你一些指示。 – 2012-03-15 14:12:23

我不認爲它可以做得比O（n^2）更快。

請看下圖。有一個雙曲線和兩個多邊形。每個多邊形的頂點位於雙曲線的分支上。

Two polygons. One on each branch of a hyperbola.

在這種情況下，兩個多邊形的邊緣成對可見（後面的兩個邊緣除外）。然後結果集將包含O（n^2）對邊。

2012-03-15 13:59:22 wks

嗯。也許可以做一些事前準備。就像遊戲中的BSP去除隱藏表面一樣。 – innochenti 2012-03-15 15:41:49

@innochenti這並不改變輸出的大小，這是真正的瓶頸。但是，如果您修改了問題/要求/期望的輸出，則可能會有更快的解決方案。 – wks 2012-03-16 05:51:45

回答