Определить, находится ли точка внутри треугольника

Ответ 1

Правильный способ сделать это - вычислить барицентрические координаты четвертой точки, учитывая три точки вашего треугольника. Формула для их вычисления приведена в конце раздела "Преобразование в барицентрические координаты" , но я надеюсь, что здесь будет представлено менее подробное объяснение математики.

Предположим для простоты, что у вас есть структура, 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 лежит внутри треугольника, состоящего из точек p1, p2 и p3.

Объяснение этого состоит в том, что точка внутри треугольника может быть описана с использованием точек треугольника и трех коэффициентов (по одному для каждой точки в диапазоне [0,1]):

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

Перестановка этой функции дает вам формулу для вычисления барицентрических координат, но я чувствую, что шаги, которые могут сделать это, могут выходить за рамки вопроса. Они представлены на странице Википедии, на которой я связан вверх.

Отсюда следует, что каждый коэффициент должен быть больше 0, чтобы точка p лежала в области, описываемой тремя точками.

Ответ 2

Вместо P1, P2 и P3 допустим точки как A, B и C.

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

Алгоритм:

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.

Ниже приведена программа в 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;
}

Время: O (1)

Пробел: O (1)

Ответ 3

Возьмите среднее из трех заданных точек. Эта новая точка P4 всегда будет находиться внутри треугольника.

Теперь проверьте, лежат ли P и P4 на одной стороне каждой из трех строк P1P2 P2P3 и P3P1. Вы можете сделать это, проверив знаки кросс-продуктов (P -> P1) x (P -> P2) и (P4 -> P1) x (P4 -> P2) (где P- > P1 - вектор от P до P1), а затем две другие пары.