第9回 凸多角形の交差計算（前編） | gihyo.jpはじめに 今回からは、2つの凸多角形を重ね合わせて、その共通部分を切り出す交差計算を見ていきます。以前に学んだ平面走査法をうまく応用することで、高速な交差計算が可能になります。また、この凸多角形の交差計算は、本連載の最後で取り上げるボロノイ図の作成にも深く関係します。 図形のブーリアン演算 Adobe Illustratorなどのドローツールでは、2つの図形を結合して新しい図形を作り出す操作が良く行われます。これはブーリアン演算（boolean operation）と呼ばれ、領域を併合するunion演算、共通部分を切り出すintersection演算、差分を求めるdifference演算といったバリエーションがあります（図1）。 図1 ブーリアン演算 一般に、図形のブーリアン演算は複雑な処理になります。多角形同士の演算を考えてみても、図2に示すように、演算結果が「穴」を含む領域になった
