在計算幾何領域中,機器人規劃路線是一個實用的議題, 由於機器人是一個有體積的物體,要避開其他的障礙物,障礙物碰撞計算會變得相當複雜。由於某 M 沒有學好這一部分,知道一種方法可以將地圖轉換,把機器人轉換成一個點,計算得到新的障礙物,如此一來就不用處理障礙物碰撞。
從上圖中,一個箭頭型機器人要從左下角移動到右上角,假設不考慮物體可以旋轉,請問是否能移動過去。若把機器人當作一點看待,則必須將物體邊緣增加,變成中間那張圖 configuration space,只剩下一個點和數個多邊形障礙物。接著可以轉換成 visibility graph,把剩下的白色空間進行梯形剖分或者三角剖分,將區域表示成一個點,相鄰區域拉一條邊,就成 dual graph,就能套用一般的最短路徑算法,來協助機器人行走。
處理這問題對於某 M 過於困難,於是將問題更簡化些,只需要把中間那一張圖其中一個障礙物變化求出即可。
現在給定一個凸多邊形障礙物以及移動凸多邊形,假設定位點在深黑色點方形部分,藉由貼著障礙物可以構出新的障礙物,請問新的障礙物為何?
第一行會有一個整數 T,表示有多少組測資。
每一組測資會包含兩個凸多邊形。第一行有一個整數 N 表示移動凸多邊形的頂點數量,接下來會有 N 行,每一行會有兩個整數 x, y 表示頂點座標。在 N+1 行之後,會有一個整數 M 表示障礙物凸多邊形的頂點數量,接下來會有 M 行,每一行會有兩個整數 x, y 表示頂點座標。
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
Case #1: 89.0 Case #2: 115.5
所求面積為橘色部分為 89。
關鍵字搜索: Minkowski Sum
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|