計算幾何(5)

問) ある凸多角形の頂点列 Point[0],Point[1],…,Point[N-1]と、ある点Point Aが与えられたときに、Aがこの凸多角形の内部の点であるかどうかを判定するアルゴリズムを示せ。

解答と解説)
これは計算幾何の分野で言うところの点位置決定問題(point location problem)である。

本問題は、凸多角形という前提があるので、簡単である。

一例を示すと、「多角形の隣り合う2頂点Point[i],Point[i+1]とAとのCCW(CCWとはid:yaneurao:20070118で用意したrobustなarg関数)をすべて求めて、その符号がすべて同じであればAは多角形の内側に存在する」とする方法がある。

他のやり方としてはAを通る水平線がAの右側でこの多角形の辺と交わる回数をカウントしても良い。「交わる回数が奇数であればAは多角形の内側である」とする方法がある。ただ、これはその水平線が多角形の頂点で交わるときの扱いが場合わけがいくつか発生してそう単純でもない。(右図)

前処理を事前にやっておいて良いのであれば、ボロノイ図を事前に作成しておくなどやりようがある。ラスタ数が固定であるなら(例えばペイントソフトでユーザーが囲ったリージョン(多角形)の内部か外部かを判定したいならば)、事前に多角形内部をペイントしてしまっても良いかも知れない。