algorithm - эта - Как определить, находится ли точка в двумерном треугольнике?




принадлежность точки треугольнику паскаль (16)

Java-версия барицентрического метода:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

Вышеприведенный код будет работать точно с целыми числами, не допуская переполнения. Он также будет работать с треугольниками по часовой стрелке и против часовой стрелки. Он не будет работать с коллинеарными треугольниками (но вы можете проверить это, проверив det == 0).

Барицентрическая версия работает быстрее, если вы собираетесь тестировать разные точки с одним и тем же треугольником.

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

Кредит: я сделал вышеупомянутый код из статьи Википедии о барицентрических координатах.

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


В общем, простейший (и вполне оптимальный) алгоритм проверяет, на какой стороне полуплоскости, создаваемой ребрами, находится точка.

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

И вот какой код вы можете начать:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

Вот эффективная реализация Python :

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

и пример вывода:


Другая функция в python , быстрее, чем метод разработчика (по крайней мере для меня) и вдохновлена ​​решением Cédric Dufour :

def ptInTriang(p_test, p0, p1, p2):       
     dX = p_test[0] - p0[0]
     dY = p_test[1] - p0[1]
     dX20 = p2[0] - p0[0]
     dY20 = p2[1] - p0[1]
     dX10 = p1[0] - p0[0]
     dY10 = p1[1] - p0[1]

     s_p = (dY20*dX) - (dX20*dY)
     t_p = (dX10*dY) - (dY10*dX)
     D = (dX10*dY20) - (dY10*dX20)

     if D > 0:
         return (  (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D  )
     else:
         return (  (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D  )

Вы можете протестировать его с помощью:

X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8]) 
p1 = np.array([12 , 55]) 
p2 = np.array([7 , 19]) 
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
    p_test[0] = points_unif[0][i]
    p_test[1] = points_unif[1][i]
    if ptInTriang(p_test, p0, p1, p2):
        plt.plot(p_test[0], p_test[1], '.g')
    else:
        plt.plot(p_test[0], p_test[1], '.r')

Это займет много времени, но эта сетка протестирована в 0,0195319652557 секунд против 0.0844349861145 секунд кода разработчика .

Наконец, комментарий к коду:

# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1  and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x)   (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ]   [(p1.y-p0.y)   (p2.y-p0.y)]   [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
# 
# [ s ] =   A^-1  * [ X - p0.x ]
# [ t ]             [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A)   =   [(p2.y-p0.y)   -(p2.x-p0.x)]
#              [-(p1.y-p0.y)   (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
#     s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
#     s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20

Если вы ищете скорость, вот процедура, которая может вам помочь.

Сортируйте вершины треугольника по их ординатам. Это занимает в худшем случае три сравнения. Пусть Y0, Y1, Y2 - три отсортированных значения. Рисуя три горизонтали через них, вы разбиваете плоскость на две полуплоскости и две плиты. Пусть Y - ордината точки запроса.

if Y < Y1
    if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
    else Y > Y0 -> the point lies in the upper slab
else
    if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
    else Y < Y2 -> the point lies in the lower slab

Затраты на два сравнения. Как вы видите, быстрое отклонение достигается за точки, находящиеся за пределами «ограничивающей плиты».

По желанию вы можете поставить тест по абсциссам для быстрого отклонения слева и справа ( X <= X0' or X >= X2' ). Одновременно будет выполняться быстрый тест с ограничивающей коробкой, но вам также нужно будет отсортировать по абсциссам.

В конце концов вам нужно будет вычислить знак данной точки относительно двух сторон треугольника, которые ограничивают соответствующую плиту (верхнюю или нижнюю). Тест имеет форму:

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

Полное обсуждение комбинаций i, j, k (их шесть, основанных на результатах сортировки) выходит за рамки этого ответа и «оставлено как упражнение для читателя»; для эффективности они должны быть жестко закодированы.

Если вы считаете, что это решение является сложным, обратите внимание на то, что он в основном включает в себя простые сравнения (некоторые из которых могут быть предварительно вычислены), плюс 6 вычитаний и 4 умножения в случае сбоя теста ограничительной рамки. Последнюю стоимость трудно превзойти, так как в худшем случае вы не можете избежать сравнения контрольной точки с двумя сторонами (ни один метод в других ответах не имеет более низкой стоимости, некоторые из них ухудшают, например, 15 вычитаний и 6 умножений, иногда делений).

ОБНОВЛЕНИЕ: Быстрее с преобразованием сдвига

Как объяснялось выше, вы можете быстро найти точку внутри одной из четырех горизонтальных полос, разделенных тремя ординатами вершин, используя два сравнения.

Вы можете дополнительно выполнить один или два дополнительных X-теста, чтобы проверить настойчивость к ограничивающей рамке (пунктирные линии).

Затем рассмотрим преобразование «сдвига», заданное X'= X - m Y, Y' = Y , где m - наклон DX/DY для самого высокого ребра. Это преобразование сделает эту сторону треугольника вертикальной. И так как вы знаете, на какой стороне средней горизонтали вы находитесь, достаточно проверить знак по отношению к одной стороне треугольника.

Предполагая, что вы предварительно вычислили наклон m , а также X' для срезанных треугольных вершин и коэффициентов уравнений сторон при X = m Y + p , вам понадобится в худшем случае

  • два сравнения ординат для вертикальной классификации;
  • необязательно одно или два сравнения абсцисс для отклонения коробки;
  • вычисление X' = X - m Y ;
  • одно или два сравнения с абсциссами срезанного треугольника;
  • один знак теста X >< m' Y + p' против соответствующей стороны срезанного треугольника.

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

Если линия, на которой находится точка, является горизонтальной, используйте выше / ниже.

Если точка находится в общей вершине нескольких треугольников, используйте треугольник, центр которого точка образует наименьший угол.

Больше удовольствия: три точки могут быть по прямой (нулевые градусы), например (0,0) - (0,10) - (0,5). В триангулирующем алгоритме «ухо» (0,10) должно быть отловлено, «треугольник», порожденный, является вырожденным случаем прямой.


Мне нужна точка в проверке треугольника в «управляемой среде», когда вы абсолютно уверены, что треугольники будут по часовой стрелке. Итак, я взял Perro Azul jsfiddle и изменил его, как это было предложено 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;
}

Предположительно высокопроизводительный код, который я адаптировал в 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


Решите следующую систему уравнений:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

Точка p находится внутри треугольника, если 0 <= s <= 1 и 0 <= t <= 1 и s + t <= 1 .

s , t и 1 - s - t называются барицентрическими координатами точки p .


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


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

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

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

  1. Угол ACE (зеленый) должен быть меньше угла ACB (красный)
  2. Угол ECB (синий) должен быть меньше угла ACB (красный)
  3. Точка E и точка C shoud имеют один и тот же знак, когда их значения 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));


Я написал этот код до последней попытки с Google и поиска этой страницы, поэтому я решил поделиться ею. Это в основном оптимизированная версия ответа Kisielewicz. Я также изучил метод Barycentric, но, судя по статье в Википедии, мне трудно понять, насколько она эффективнее (я предполагаю, что есть более глубокая эквивалентность). Во всяком случае, этот алгоритм имеет то преимущество, что не использует деление; потенциальной проблемой является поведение обнаружения края в зависимости от ориентации.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

На словах, идея такова: есть ли точка s слева или справа от обеих линий AB и AC? Если это правда, оно не может быть внутри. Если false, то, по крайней мере, внутри «конусов», удовлетворяющих условию. Теперь, поскольку мы знаем, что точка внутри треугольника (треугольника) должна быть с той же стороны AB, что и BC (а также CA), мы проверяем, отличаются ли они. Если они это сделают, s не может быть внутри, иначе s должно быть внутри.

Некоторые ключевые слова в расчетах представляют собой полуплоскости линии и определитель (2x2 поперечное произведение). Возможно, более педагогический путь, вероятно, должен думать об этом как о точке, находящейся внутри, если она находится на одной стороне (слева или справа) до каждой из линий AB, BC и CA. Однако вышеприведенный способ лучше подходит для некоторой оптимизации.


Я согласен с Андреасом Бринком , для этой задачи очень удобны барицентрические координаты. Обратите внимание, что нет необходимости решать систему уравнений каждый раз: просто оцените аналитическое решение. Используя обозначения Андреаса , решение:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

где Area - (подписанная) область треугольника:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

Просто оцените s , t и 1-st . Точка p находится внутри треугольника тогда и только тогда, когда все они положительны.

EDIT: Обратите внимание, что приведенное выше выражение для области предполагает, что нумерация узлов треугольника против часовой стрелки. Если нумерация по часовой стрелке, это выражение вернет отрицательную область (но с правильной величиной). Сам тест ( s>0 && t>0 && 1-st>0 ) не зависит от направления нумерации, однако, поскольку вышеприведенные выражения, умноженные на 1/(2*Area) также меняют знак, если ориентация узла треугольника меняется.

EDIT 2: для получения еще большей вычислительной эффективности см. Комментарий coproc ниже (что указывает на то, что если ориентация узлов треугольника (по часовой стрелке или против часовой стрелки) известна заранее, разделение на 2*Area в выражениях для s и t можно избежать). См. Также jsfiddle-код Перро Азула в комментариях под ответом Андреаса Бринка .


C # версия барицентрического метода, опубликованная andreasdr и Perro Azul. Обратите внимание, что расчет площади можно избежать, если s и t имеют противоположные знаки. Я проверил правильное поведение с довольно тщательным модульным тестом.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point 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 * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y;

    return A < 0 ?
            (s <= 0 && s + t >= A) :
            (s >= 0 && s + t <= A);
}

[ править ]
принятая предлагаемая модификация @Pierre; см. комментарии


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

Самый простой рабочий код: `

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)

`


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 известны, результат - это всего лишь несколько базовых сравнений и логические операции.







geometry