特定のポイントがポリゴンの内側にあるかどうかを確認します
この問題では、1つのポリゴンが指定され、点Pも指定されます。ポイントがポリゴンの内側にあるか、ポリゴンの外側にあるかを確認する必要があります。
それを解くために、点Pから直線を描きます。それは無限大まで伸びています。線は水平、またはx軸に平行です。
その線から、線がポリゴンの辺と交差する回数を数えます。ポイントがポリゴンの内側にある場合、ポイントは辺と奇数回交差します。Pがポリゴンのいずれかの側に配置されている場合、ポイントは偶数回カットされます。いずれの条件も当てはまらない場合は、ポリゴンの外側にあります。
入力と出力
Input: Points of a polygon {(0, 0), (10, 0), (10, 10), (0, 10)}. And point P (5, 3) to check. Output: Point is inside.
アルゴリズム
checkInside(Poly, n, p)
入力: ポリゴンのポイント、ポリゴンのポイント数、チェックするポイントp。
出力: pがポリゴンの内側にある場合はtrue、それ以外の場合はfalse。
Begin if n<3, then return false create a line named exLine from point p to infinity, Slope of the line is 0°. count :=0 and i := 0 repeat create line called side, from point poly[i] to poly[(i+1) mod n] if the side and exLine intersects, then if side and exLine are collinear, then if point p on the side, then return true else return false count := count + 1 i := (i + 1) mod n until i ≠ 0 return true if count is odd End
例
#include<iostream> using namespace std; struct Point { int x, y; }; struct line { Point p1, p2; }; bool onLine(line l1, Point p) { //check whether p is on the line or not if(p.x <= max(l1.p1.x, l1.p2.x) && p.x <= min(l1.p1.x, l1.p2.x) && (p.y <= max(l1.p1.y, l1.p2.y) && p.y <= min(l1.p1.y, l1.p2.y))) return true; return false; } int direction(Point a, Point b, Point c) { int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y); if (val == 0) return 0; //colinear else if(val < 0) return 2; //anti-clockwise direction return 1; //clockwise direction } bool isIntersect(line l1, line l2) { //four direction for two lines and points of other line int dir1 = direction(l1.p1, l1.p2, l2.p1); int dir2 = direction(l1.p1, l1.p2, l2.p2); int dir3 = direction(l2.p1, l2.p2, l1.p1); int dir4 = direction(l2.p1, l2.p2, l1.p2); if(dir1 != dir2 && dir3 != dir4) return true; //they are intersecting if(dir1==0 && onLine(l1, l2.p1)) //when p2 of line2 are on the line1 return true; if(dir2==0 && onLine(l1, l2.p2)) //when p1 of line2 are on the line1 return true; if(dir3==0 && onLine(l2, l1.p1)) //when p2 of line1 are on the line2 return true; if(dir4==0 && onLine(l2, l1.p2)) //when p1 of line1 are on the line2 return true; return false; } bool checkInside(Point poly[], int n, Point p) { if(n < 3) return false; //when polygon has less than 3 edge, it is not polygon line exline = {p, {9999, p.y}}; //create a point at infinity, y is same as point p int count = 0; int i = 0; do { line side = {poly[i], poly[(i+1)%n]}; //forming a line from two consecutive points of poly if(isIntersect(side, exline)) { //if side is intersects exline if(direction(side.p1, p, side.p2) == 0) return onLine(side, p); count++; } i = (i+1)%n; } while(i != 0); return count&1; //when count is odd } int main() { // line polygon = {{{0,0},{10,0}},{{10,0},{10,10}},{{10,10},{0,10}},{{0,10},{0,0}}}; Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}}; Point p = {5, 3}; int n = 4; if(checkInside(polygon, n, p)) cout << "Point is inside."; else cout << "Point is outside."; }
出力
Point is inside.
-
Pythonで点が長方形の上または内側にあるかどうかを確認します
左下と右上の2つの点で表される長方形があるとします。この長方形の内側に特定の点(x、y)が存在するかどうかを確認する必要があります。 したがって、入力がbottom_left =(1、1)、top_right =(8、5)、point =(5、4)の場合、出力はTrueになります これを解決するには、次の手順に従います- 関数solve()を定義します。これにはbl、tr、pが必要です blのxおよびpのxblのyおよびpのy
与えられたポリゴンの内側または境界にある与えられた点をチェックするか、Pythonではないかをチェックするプログラムポリゴンを表すデカルト点[(x1、y1)、(x2、y2)、...、(xn、yn)]のリストがあり、xとyの2つの値があるとします。 (x、y)がこのポリゴンの内側にあるのか、境界上にあるのかを確認してください。 したがって、入力がpoints =[(0、0)、(1、3)、(4、4)、(6、2)、(4、0)] pt =(3、1) その場合、出力はTrueになります これを解決するには、次の手順に従います- ans:=False 0からポリゴンのサイズ-1までの範囲のiの場合、実行します (x0、y0):=ポリゴン[i] (x1、y1):=ポリゴン[(i + 1)ポリゴンのm