math - 点が三角形の内側にあるかどうかを判別

Question

プログラムは 3 つの座標の値を読み取る必要があります。

• P1(x1,y1)
• P2(x2,y2)
• P3(x3,y3)

別の座標 P(x,y) と同様に、この点が上の 3 点から形成される三角形の内側にあるかどうかを判断します。

Answer 1

これを行う適切な方法は、三角形の 3 つの点から 4 番目の点の重心座標を計算することです。それらを計算する式は、「重心座標への変換」セクションの最後に記載されていますが、ここでは数学的な説明を少なくしたいと思います。

point簡単にするために、値xとを持つ構造体 があると仮定しますy。ポイントを次のように定義しました。

point p1(x1, y1);
point p2(x2, y2);
point p3(x3, y3);

point p(x,y); // <-- You are checking if this point lies in the triangle.

alphaここで、一般に 、beta、 と呼ばれる重心座標は、gamma次のように計算されます。

float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) /
        ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
       ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float gamma = 1.0f - alpha - beta;

alpha、beta、およびのすべてgammaが より大きい場合0、点は点、、および で構成されるp三角形内にあります。p1p2p3

この背後にある説明は、三角形の内部の点は、三角形の点と 3 つの係数 ([0,1] の範囲内の各点に 1 つ) を使用して記述できるということです。

p = (alpha)*p1 + (beta)*p2 + (gamma)*p3

この関数を並べ替えると、重心座標を計算する式が得られますが、その手順は質問の範囲を超えているように感じます。それらは、私がリンクしたウィキペディアのページで提供されています。

pしたがって、点が 3 つの点で表される領域内にあるためには、各係数が 0 より大きくなければなりません。

Answer 2

Instead of P1, P2 and P3, lets assume the points as A,B and C.

          A(10,30)
            / \
           /   \
          /     \
         /   P   \      P'
        /         \
B (0,0) ----------- C(20,0) 

Algorithm :

1) Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. 

    Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2

2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area be A1.
3) Calculate area of the triangle PBC. Let this area be A2.
4) Calculate area of the triangle PAC. Let this area be A3.
5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

Given below is a program in C:

#include <stdio.h>
#include <stdlib.h>

/* A utility function to calculate area of triangle formed by (x1, y1), 
   (x2, y2) and (x3, y3) */
float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
   return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}

/* A function to check whether point P(x, y) lies inside the triangle formed 
   by A(x1, y1), B(x2, y2) and C(x3, y3) */
bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{   
   /* Calculate area of triangle ABC */
   float A = area (x1, y1, x2, y2, x3, y3);

   /* Calculate area of triangle PBC */  
   float A1 = area (x, y, x2, y2, x3, y3);

   /* Calculate area of triangle PAC */  
   float A2 = area (x1, y1, x, y, x3, y3);

   /* Calculate area of triangle PAB */   
   float A3 = area (x1, y1, x2, y2, x, y);

   /* Check if sum of A1, A2 and A3 is same as A */
   return (A == A1 + A2 + A3);
}

/* Driver program to test above function */
int main()
{
   /* Let us check whether the point P(10, 15) lies inside the triangle 
      formed by A(0, 0), B(20, 0) and C(10, 30) */
   if (isInside(0, 0, 20, 0, 10, 30, 10, 15))
     printf ("Inside");
   else
     printf ("Not Inside");

   return 0;
}

Time : O(1)

Space: O(1)

Answer 3

与えられた 3 つのポイントの平均を取ります。この新しい点 P4 は、常に三角形の内側にあります。

ここで、P と P4 が 3 つの直線P1P2 P2P3とのそれぞれの同じ側にあるかどうかを確認しP3P1ます。(P -> P1) x (P -> P2)これを行うには、外積および(P4 -> P1) x (P4 -> P2)(P->P1 は P から P1 へのベクトル)の符号をチェックし、次に他の 2 つのペアをチェックします。