ある点が多角形の内側にあるか外側にあるかを判定するアルゴリズムの一つにCrossing Number Algorithmがあります。本記事ではCrossing Number Algorithm説明とC++,Pythonでの実装例を紹介します。
Crossing Number Algorithm
Crossing Number Algorithmとは点から水平方向に引いた半直線が多角形の辺を交差する回数で判定します。交差回数が奇数なら多角形の内側、偶数なら多角形の外側にあると判定します。
例えば以下の図のL字型の多角形において、点Aからx方向に延びる直線と多角形の辺との交差回数は2回です。また、点Bから延びる直線と辺との交差回数は3回です。
点Aは多角形の外側、点Bは多角形の内側にあることから、多角形の辺との交差回数で内外判定ができることがイメージできるかと思います。
ここまでで、Crossing Number Algorithmについての概要は理解できたかと思います。以降では、Crossing Number Algorithmの実装方法について紹介します。
実装方針
判定したい点を点P、多角形の任意の辺の両端をそれぞれP1,P2としたとき、点Pからx方向に延ばした半直線と辺が交差するか否かは以下の条件で判定することができます。
- 点Pのy座標が点P1のy座標と点P2の座標の間にあること
- 点Pと同じy座標かつ線分P1-P2上の点P3を求め、点Pのx座標が点P3のx座標よりも小さいこと
上記1,2を満たすとき点Pからx方向に延ばした半直線と辺が交差します。これを多角形のすべての辺に対して実施することで、交差回数を求めることができます。
実装例(C++)
C++の実装例は以下です。
#include <iostream>
#include <vector>
// 点の座標クラス
class Point {
public:
int32_t x;
int32_t y;
explicit Point(const int32_t x, const int32_t y) : x(input_x), y(input_y) {}
}
// 多角形クラス
class Polygon {
public:
std::vector<Point> vertexes;
explicit Polygon(const std::vector<Point>& points) : vertexes(points) {}
}
/**
* 点が多角形内にあるか判定する関数
*
* @return true(内側) / false(外側)
*/
bool is_point_inside_polygon(const Point& point, const Polygon& polygon) {
// 交差回数のカウンタ
uint32_t c = 0;
for (const auto& v : polygon.vetexes) {
const uint32_t i = &v - &polygon.vetexes[0];
// 隣の頂点
const Point v1 = (i == polygon.vetexes.size() - 1) ? polygon.vetexes[0]
: polygon.vetexes[i + 1];
// pointのy座標が2頂点の間にあるか？
if (((v.y <= point.y) && (v1.y > point.y)) ||
((v.y > point.y) && (v1.y <= point.y))) {
double x = v.x + ((point.y - v.y) / double(v1.y - v.y) * (v1.x - v.x));
// 辺上にある場合は内側判定
if(point.x == x){
return true;
}
if (point.x < x) {
count++;
}
}
}
return (count % 2) == 1;
}
// 使用例
int main() {
std::vector<Point> ps = {{1, 1}, {4, 1}, {4, 4}, {1, 4}};
Polygon polygon{ps};
Point p1{2, 2};
if (is_point_inside_polygon(p1, polygon)) {
std::cout << "inside!" << std::endl;
} else {
std::cout << "outside!" << std::endl;
}
return 0;
}5~11行目は点の座標を示すクラス、14~19行目は多角形を示すクラスで、26~48行目がCrossing Number Algorithmの処理です。
37~38行目で条件1の「点Pのy座標が点P1のy座標と点P2の座標の間にあること」を判定しています。また、39行目で点P3のx座標を求め、46行目で点Pと点P3のx座標を比較しています。これらの条件を満たす時、countをインクリメントします。
また、点Pが辺上にある場合は多角形の内側と判定し、trueを返しています(42~43行目)。返上は外側と判定したい場合は、42~44行目をコメントアウトしてください。
すべての頂点に対して上記の処理をした後、countが奇数の時true、偶数の時falseを返します。
実装例(Python)
続いてPythonでの実装例は以下です。C++の実装例をPythonに書き直しただけなので、説明は省略します。
def is_point_in_polygon(point, polygon):
# 交差回数のカウンタ
count = 0
p_x = point[0]
p_y = point[1]
for i, v, in enumerate(polygon):
# 頂点座標
v_x = v[0]
v_y = v[1]
# 隣の頂点座標
v1_x = polygon[0][0] if i == len(polygon)-1 else polygon[i+1][0]
v1_y = polygon[0][1] if i == len(polygon)-1 else polygon[i+1][1]
if((v_y <= p_y) and (v1_y > p_y)) or ((v_y > p_y) and (v1_y <= p_y)):
x = v_x + ((p_y - v_y) / (v1_y - v_y)*(v1_x -v_x))
# 辺上にある場合は内側判定
if x == p_x:
return True
elif p_x < x:
count += 1
return bool(count%2 == 1)
# 使用例
if __name__ == '__main__':
point = [2,2]
polygon = [[1, 1], [4, 1], [4, 4], [1, 4]]
if is_point_in_polygon(point, polygon):
print("inside!")
else:
print("outside")
参考
本記事のソースコードは以下で公開しているので参考にしてみてください。https://github.com/kengo519/materials/tree/main/cross_number_algorithm
アルゴリズムは以下のサイトを参考にしています。
「NTTPC【第2回】点の多角形に対する内外判定」https://www.nttpc.co.jp/technology/number_algorithm.html
コメント