多角形の内点判定

ある点が多角形に含まれるかどうかを判定する

ある２次元上の点が多角形の内部にあるかどうかを判定するには、判定点からX軸に水平な半直線を描き、 多角形の各線分との交点の個数が奇数ならば、内部の点と判断すればよい[1]。

プログラム[Java]

ある点 PointF p が多角形 PointF[] poly に含まれるかどうかを判定する Java プログラム boolean PointInPolygon(PointF p, PointF[] poly) を下に示す。

サイト[2] における日本地図領域を多角形 PointF[] japans で示した。 boolean PointInJapan(PointF p)の戻り値が true であれば、PointF p は日本地図領域内に含まれる地点である。 false ならば、日本地図領域外の地点である。

class PointF {

static PointF[] japans = {
  new PointF(153.8901f, 26.38211f),
  new PointF(132.1529f, 26.46809f),
  new PointF(131.6915f, 21.20992f),
  new PointF(122.5954f, 23.51966f),
  new PointF(122.5607f, 25.84146f),
  new PointF(128.8145f, 34.74835f),
  new PointF(129.3966f, 35.09403f),
  new PointF(135.3079f, 37.54740f),
  new PointF(140.5769f, 45.70648f),
  new PointF(149.1891f, 45.80245f),
  new PointF(153.8901f, 26.38211f) 
};

float X;
float Y;
     
public PointF(float x, float y) {
  X = x;
  Y = y;
}

static boolean PointInJapan(PointF p){
  return PointInPolygon(p, japans);
}


static boolean PointInPolygon(PointF p, PointF[] poly) {
  PointF p1, p2;
  boolean inside = false;
  PointF oldPoint = poly[poly.length-1];
  for (int i=0; i<poly.length; i++){
    PointF newPoint = poly[i];
    if (newPoint.X > oldPoint.X) { 
       p1 = oldPoint; 
       p2 = newPoint; 
    } else { 
       p1 = newPoint; 
       p2 = oldPoint; 
    }
    if ((p1.X<p.X)==(p.X<=p2.X) &&
      (p.Y-p1.Y)*(p2.X-p1.X) < (p2.Y-p1.Y)*(p.X-p1.X)) {
      inside = !inside;
    }
    oldPoint = newPoint;
  }
  return inside;
}

}

参考記事