はじめに
前々回は凸多角形を取り上げましたが,
Blogopolisにおける多角形の点包含判定と面積計算
Blogopolisでは,
また,
こうした
多角形の点包含判定
まず,
点(x, y)を始点とし,
一方,
このように,
なお,
この方針にしたがい,
リスト contains()メソッドの記述
public boolean contains(double x, double y) {
// 多角形のy座標範囲を求める
double minY = Double.POSITIVE_INFINITY;
double maxY = Double.NEGATIVE_INFINITY;
for (Point2D v : vertices) {
minY = Math.min(minY, v.getY());
maxY = Math.max(maxY, v.getY());
}
// yが最小値-最大値の範囲外の場合はfalseを返す
if (y <= minY || y >= maxY) {
return false;
}
// 与えられた座標を始点とし,右方向に十分長く延びる擬似的な半直線を作成
LineSegment halfLine = new LineSegment(x, y, x + 10000000, y);
int count = 0;
for (LineSegment edge : edges) {
// 半直線が辺の終点とちょうど重なる場合,次の辺の始点とも交差が検出され,
// 二重にカウントされてしまうため,カウントをスキップする
if (edge.y2 == y) {
continue;
}
if (edge.intersects(halfLine)) {
count++;
}
}
// 交差回数が奇数の場合は点を包含
return count % 2 == 1;
}
上のコードでは,
念のため再度述べますが,