2次元平面上の凸多角形の共通部分

2つの凸多角形同士の共通部分は、存在すれば必ず1つの凸多角形になる。
(凹多角形だと複数に分かれることがある)

凸多角形を $P,Q$ とし、$((x_{p1},y_{p1}),...,(x_{pN},y_{pN}))$ のように反時計回りの点列で与えられるとする。
$P$ の点の個数を $N$、$Q$ の点の個数を $M$ とする。

共通部分の凸多角形を、同様に点列で求めたい。

アルゴリズム

$O(NM)$ アルゴリズム

共通部分の頂点を蓄積する集合 $Rset$ を用意する。

  • $P$ の各点につき、$Q$ に内包されている(または辺上にある)点を $Rset$ に入れる
  • $Q$ の各点につき、$P$ に内包されている(または辺上にある)点を $Rset$ に入れる
  • $P$ と $Q$ の各辺ペアにつき、交わるなら交点の座標を求め、$Rset$ に入れる
    • 端点で交わる(一方の頂点が他方の辺上にある)場合は含めなくてよい
    • 2辺が同一線上にある場合は含めない

それぞれ $O(NM)$ ずつかかる。
これで、$Rset$ には共通部分の全頂点が入った。

これをちゃんと順番通りに並べる。
まず重心を求める。
凸多角形の重心は必ず多角形内にあるので、重心からの偏角でソートすれば、順番通りになる。

$O(N+M)$ アルゴリズム

以下、点同士の比較は $(x,y)$ 基準でおこなうものとする。($x$ 優先、$x$ が同じなら $y$ で比較)

凸包を求めるアルゴリズムの1つMonotone Chainのように、上辺と下辺に分けて考える。

$P$ を最小の頂点 $p_{min}$ から最大の頂点 $p_{max}$ まで、 $P$ の上側を伝う頂点列と下側を使う頂点列に分ける。
ただし $p_{min}$ と $p_{max}$ は両方の最初・最後に重複して入っているとする。

$Q$ も同じようにし、共通部分も上と下に分けて求めるとすると、それらを構成する頂点は以下のいずれかになる。

  • 共通部分の上の頂点列:
    • $P$ の上側頂点のうち、その $x$ 座標において $Q$ の上辺と下辺の間にある頂点
    • $Q$ の上側頂点のうち、その $x$ 座標において $P$ の上辺と下辺の間にある頂点
    • 辺同士の交点
  • 共通部分の下の頂点列:
    • $P$ の下側頂点のうち、その $x$ 座標において $Q$ の上辺と下辺の間にある頂点
    • $Q$ の下側頂点のうち、その $x$ 座標において $P$ の上辺と下辺の間にある頂点
    • 辺同士の交点

実装上は、たとえば以下で管理する。

  • $plo,phi,qlo,qhi$: それぞれ $P,Q$ の下頂点列、上頂点列
  • $i,j,k,l$: 上に対応して、それぞれどこまで見たかの4つのindex
  • $rlo,rhi$: 共通部分の下頂点列、上頂点列
  • 4つのそれぞれ次の頂点 $plo_{i+1},phi_{j+1},qlo_{k+1},qhi_{l+1}$ のうち、最も小さい頂点を求める
    • 仮に、$plo_{i+1}$ が選ばれたとし、これが共通部分に含まれるかチェックする
      • 以下の $y$ 座標を求める
        • $plo_{i+1}$ の $x$ 座標における、線分 $qlo_{k}→qlo_{k+1}$ の $y$ 座標
        • $plo_{i+1}$ の $x$ 座標における、線分 $qhi_{l}→qhi_{l+1}$ の $y$ 座標
        • ただし線分が垂直な場合、後の方の $y$ 座標
      • $plo_{i+1}$ の $y$ 座標が両者の間(境界含む)なら、$plo_{i+1}$ は共有部分の頂点
    • 含まれる場合、選ばれたのが $plo,qlo$ なら$rlo$ に追加、$phi,qhi$ なら $rhi$ に追加
  • 次の辺の交点を求める
    • 仮に $plo_i$ を $plo_{i+1}$ に進めたとする
    • 次の点 $plo_{i+2}$ が存在するなら、以下の2つをチェックする
      • 線分 $plo_{i+1}→plo_{i+2}$ と $qlo_{k}→qlo_{k+1}$ の交点
      • 線分 $plo_{i+1}→plo_{i+2}$ と $qhi_{l}→qhi_{l+1}$ の交点
    • 交点が存在すれば、以下のように $rlo,rhi$ に追加する
      • lo同士の交点なら、$rlo$ に追加
      • hi同士の交点なら、$rhi$ に追加
      • それ以外なら、両方に追加(必ず最初または最後の点)
    • この時、線分の交点を計算する順番によって、$rlo,rhi$ に大きい点が先に追加されないように注意する
  • 繰り返す

どちらかのlo,hiがともに $p_{max}$ または $q_{max}$ に到達すれば終了。

最初は $i,j,k,l=-1$ などとしておくとよい。
一方の頂点が進められたとき、他方がまだ -1 ならindexだけ進めてスキップする。

実装例

同じ点が連続しないようにしている。
面倒だったので、最初に $N+M$ 点をまとめてソートしているので、計算量には $\log$ がつく。

一応、共通部分の面積を求める以下の問題でVerifyしているが、 面積だと多少の誤差は許されてしまうので、直接的に合っているかは未Verify。

ネタバレ注意

特に小数点誤差によっては間違った結果を返す可能性がある。
とはいえ、与えられる $P,Q$ の座標が整数であれば、小数点が出現するのは交点のみであり、 小数点同士の四則演算などは行わないので $x,y \le 10^5$ くらいは大丈夫、、、なはず。

Python3

programming_algorithm/geometry/convex_intersection.txt · 最終更新: 2022/01/27 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0