プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

特定のポイントがポリゴンの内側にあるかどうかを確認します


この問題では、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.

  1. 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

  2. 与えられたポリゴンの内側または境界にある与えられた点をチェックするか、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