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

Question

Есть ли простой способ определить, находится ли точка внутри треугольника? Это 2D, а не 3D.

Answer 1

Мне нужно было проверить треугольник в «контролируемой среде», когда вы абсолютно уверены, что треугольники будут по часовой стрелке. Итак, я взял jsfiddle Perro Azul и изменил его, как предложено coproc для таких случаев; также удалены избыточные 0,5 и 2 умножения, потому что они просто отменяют друг друга.

http://jsfiddle.net/dog_funtom/H7D7g/

Вот эквивалентный код C # для Unity:

public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2)
{
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0)
        return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

Answer 2

bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

Это не может быть более эффективным, чем это! Каждая сторона треугольника может иметь независимую позицию и ориентацию, следовательно, три вычисления: l1, l2 и l3, безусловно, необходимы, включая 2 умножения каждый. Как только l1, l2 и l3 станут известны, результатом будет лишь несколько базовых сравнений и логических операций.

Answer 3

Честно говоря, это так же просто, как Ответ Саймона П Стивена однако при таком подходе у вас нет твердого контроля над тем, хотите ли вы, чтобы точки на краях треугольника были включены или нет. 1003 *

Мой подход немного другой, но очень простой. Рассмотрим следующий треугольник;

Чтобы иметь точку в треугольнике, мы должны выполнить 3 условия

1. Угол ACE (зеленый) должен быть меньше угла ACB (красный)
2. Угол ECB (синий) должен быть меньше угла ACB (красный)
3. Точка E и точка C должны иметь один и тот же знак, когда их значения x и y применяются к уравнению | AB | линия.

В этом методе у вас есть полный контроль, чтобы включить или исключить точку на краях по отдельности. Таким образом, вы можете проверить, находится ли точка в треугольнике, включая только | AC | край например.

Так что мое решение в JavaScript будет следующим:

function isInTriangle(t,p){

  function isInBorder(a,b,c,p){
    var m = (a.y - b.y) / (a.x - b.x);                     // calculate the slope
    return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y);
  }
  
  function findAngle(a,b,c){                               // calculate the C angle from 3 points.
    var ca = Math.hypot(c.x-a.x, c.y-a.y),                 // ca edge length
        cb = Math.hypot(c.x-b.x, c.y-b.y),                 // cb edge length
        ab = Math.hypot(a.x-b.x, a.y-b.y);                 // ab edge length
    return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle
  }

  var pas = t.slice(1)
             .map(tp => findAngle(p,tp,t[0])),             // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0])
       ta = findAngle(t[1],t[2],t[0]);
  return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p);
}

var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}],
      point1 = {x:3, y:9},
      point2 = {x:7, y:9};

console.log(isInTriangle(triangle,point1));
console.log(isInTriangle(triangle,point2));

Answer 4

Самый простой способ, и он работает со всеми типами треугольников, это просто определить углы точек P, A, B, C точек. Если любой из углов больше 180.0 градусов, то он снаружи, если 180.0, то он на окружности, а если acos изменяет тебе и меньше 180.0, то он внутри. physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Answer 5

Предположительно высокопроизводительный код, который я адаптировал в JavaScript (статья ниже):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

pointInTriangle (p, p0, p1, p2) - для треугольников против часовой стрелки

pointInTriangle (p, p0, p1, p2) - для треугольников по часовой стрелке

Посмотрите в jsFiddle (тест производительности включен), также есть проверка обмотки в отдельной функции http://jsfiddle.net/z7x0udf7/3/

Вдохновленный этим: http://www.phatcode.net/articles.php?id=459