[ACM 題目] 障礙物轉換

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Sample Input
  4. 4. Sample Output
  5. 5. Hint
  6. 6. Solution

Problem

在計算幾何領域中,機器人規劃路線是一個實用的議題, 由於機器人是一個有體積的物體,要避開其他的障礙物,障礙物碰撞計算會變得相當複雜。由於某 M 沒有學好這一部分,知道一種方法可以將地圖轉換,把機器人轉換成一個點,計算得到新的障礙物,如此一來就不用處理障礙物碰撞。

從上圖中,一個箭頭型機器人要從左下角移動到右上角,假設不考慮物體可以旋轉,請問是否能移動過去。若把機器人當作一點看待,則必須將物體邊緣增加,變成中間那張圖 configuration space,只剩下一個點和數個多邊形障礙物。接著可以轉換成 visibility graph,把剩下的白色空間進行梯形剖分或者三角剖分,將區域表示成一個點,相鄰區域拉一條邊,就成 dual graph,就能套用一般的最短路徑算法,來協助機器人行走。

處理這問題對於某 M 過於困難,於是將問題更簡化些,只需要把中間那一張圖其中一個障礙物變化求出即可。

現在給定一個凸多邊形障礙物以及移動凸多邊形,假設定位點在深黑色點方形部分,藉由貼著障礙物可以構出新的障礙物,請問新的障礙物為何?

Input

第一行會有一個整數 $T$,表示有多少組測資。

每一組測資會包含兩個凸多邊形。第一行有一個整數 $N$ 表示移動凸多邊形的頂點數量,接下來會有 $N$ 行,每一行會有兩個整數 $x, y$ 表示頂點座標。在 $N+1$ 行之後,會有一個整數 $M$ 表示障礙物凸多邊形的頂點數量,接下來會有 $M$ 行,每一行會有兩個整數 $x, y$ 表示頂點座標。

  • $2 < N, M < 512$
  • $-32767 < x, y < 32767$
  • 假設定位點 (深黑色點方形部分) 都設在原點 (0, 0)。
  • 輸入順序會按照順時針或逆時針給定。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
5
-1 -1
-1 1
0 3
1 1
1 -1
4
1 1
8 2
12 -1
6 -4
3
-1 -4
-1 1
1 1
5
1 0
6 5
10 5
10 -3
1 -3

Sample Output

1
2
Case #1: 89.0
Case #2: 115.5

Hint

Solution

可以用 $O(nm \log nm)$ 來完成此題,方法很簡單,先將機器人的圖形按照原點旋轉 180 度,接著將障礙物每一個頂點座標加上機器人的座標,總共會得到 $nm$ 的頂點,套用凸包算法求一次即可。

這一題應用 Minkowski Sum 來完成,對於兩個凸多邊形的 Minkowski Sum,可以在 $O(n+m)$ 時間內完成,將兩個凸包採用逆時針儲存,挑選最左,等價時抓下方 y 座標的點,可以知道新凸包的頂點一定是由兩個凸包的頂點$A_i, B_j$ 疊加而成,一開始抓到的左下方頂點疊加可以得到第一個頂點,接著要按照凸包順序求出,則比較$(A_i, A_{i+1})$$(B_j, B_{j+1})$ 哪一個偏的角度小,就挑選哪一個往前推動 i = i+1 或者是 j = j+1。最後就能在 $O(n+m)$ 時間內完成。

假設不是凸多邊形,兩個簡單多邊形最慘會到 $O(n^2 m^2)$

1