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




эта принадлежность (21)

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

Вот информация высокого качества в этой теме на 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);
}

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


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

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

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

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


bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

почти идеальные декартовы координаты, преобразованные из барицентрических, экспортируются в пределах * v (x) и * w (y). Оба удвоения экспорта должны иметь * char раньше в каждом случае, вероятно: * v и * w Код может использоваться и для другого треугольника четырехугольника. Таким образом, подписанный написал только треугольник abc по часовой стрелке abcd quad.

A---B
|..\\.o|  
|....\\.| 
D---C 

точка o находится внутри треугольника ABC для тестирования со вторым треугольником, который вызывает это направление CDA функции, и результаты должны быть правильными после *v=1-*v;и *w=1-*w;для четырехугольника


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


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


Другая функция в 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

Вот эффективная реализация 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))

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


Самый простой способ и он работает со всеми типами треугольников - это просто определить углы точек точки 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


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

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-код Перро Азула в комментариях под ответом Андреаса Бринка .


Если вы знаете координаты трех вершин и координаты конкретной точки, вы можете получить область полного треугольника. Затем вычислите площадь трех треугольных сегментов (одна точка - заданная точка, а две другие - любые две вершины треугольника). Таким образом, вы получите площадь трех треугольных сегментов. Если сумма этих площадей равна общей площади (которую вы получили ранее), то точка должна находиться внутри треугольника. В противном случае точка не находится внутри треугольника. Это должно сработать. Если есть какие-либо проблемы, сообщите мне. Спасибо.


Используя аналитическое решение для барицентрических координат (отмечено Андреасом Бринком ) и:

  • не распространяя умножение на круглые скобки
  • избегая вычисления в несколько раз тех же терминов путем их хранения
  • уменьшая сравнения (как указывает копрок и Томас Эдинг )

можно свести к минимуму количество «дорогостоящих» операций:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

(код может быть вставлен в Perro Azul jsfiddle.net/PerroAZUL/zdaY8/1 )

Руководители:

  • переменная «напоминает»: 30
  • переменное хранилище: 7
  • добавлений: 4
  • субстанции: 8
  • умножения: 6
  • дивизии: нет
  • сравнений: 4

Это довольно хорошо сравнивается с решением Kornel Kisielewicz (25 повторений, 1 хранилище, 15 подстановок, 6 умножений, 5 сравнений) и может быть еще лучше, если требуется обнаружение по часовой стрелке / против часовой стрелки (которое принимает 6 повторений, 1 дополнение, 2 подстановки , 2 умножения и 1 сравнение само по себе, используя определитель аналитического решения, как указано rhgb ).


Простым способом является:

найти векторы, соединяющие точку с каждой из трех вершин треугольника и суммировать углы между этими векторами. Если сумма углов равна 2 * pi, то точка находится внутри треугольника.

Два хороших сайта, объясняющих альтернативы:

blackpawn и wolfram


То, что я делаю, является предварительным вычислением трех нормалей лица,

  • в 3D с помощью поперечного произведения бокового вектора и вектора нормали лица.

  • в 2D, просто заменяя компоненты и отрицая их,

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

Выгоды:

  • много предварительно рассчитано настолько велико для многоточечного тестирования на том же треугольнике.

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


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

  1. Область A определяется как любой вектор, заданный s * v02 + t * v01, с условием s> = 0 и t> = 0. Если любая точка внутри треугольника v0, v1, v2, она должна быть внутри области A.

  1. Если дальнейшее ограничение s и t принадлежит [0, 1]. Мы получаем область B, которая содержит все векторы s * v02 + t * v01, причем условие s, t принадлежит [0, 1]. Стоит отметить, что нижняя часть Района B является зеркалом треугольника v0, v1, v2. Проблема возникает, если мы можем дать некоторое условие s и t, чтобы далее исключить низкую часть Района B.

  1. Предположим, что мы даем значение s, а t меняется в [0, 1]. В следующем рисунке точка p находится на краю v1v2. Все векторы s * v02 + t * v01, которые расположены вдоль штриховой линии простой векторной суммой. В точке v1v2 и пунктирной линии p мы имеем:

(1-s) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

получаем 1 - s = tp, то 1 = s + tp. Если любой t> tp, который 1 <s + t, где находится на линии двойной линии, вектор находится вне треугольника, любой t <= tp, который 1> = s + t, где находится на одной штриховой линии, вектор внутри треугольника.

Тогда, если бы мы задали любые s из [0, 1], то соответствующий вектор t должен соответствовать 1> = s + t, для вектора внутри треугольника.

Итак, наконец, получим v = s * v02 + t * v01, v внутри треугольника с условием s, t, s + t принадлежит [0, 1]. Тогда переведите в точку, у нас есть

p - p0 = s * (p1 - p0) + t * (p2 - p0), причем s, t, s + t в [0, 1]

что совпадает с решением Андреаса для решения системы уравнений p = p0 + s * (p1 - p0) + t * (p2 - p0), причем s, t, s + t принадлежат [0, 1].


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

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

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

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


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

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

Чтобы иметь точку в треугольнике, мы должны удовлетворять 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));


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

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

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

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


Вот решение в python, которое эффективно, документировано и содержит три unittests. Это профессиональное качество и готово к включению в ваш проект в виде модуля, как есть.

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

Существует дополнительный дополнительный графический тест для вышеприведенного алгоритма для подтверждения его действительности:

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

Изготовление следующего рисунка:


Я написал этот код до последней попытки с 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. Однако вышеприведенный способ лучше подходит для некоторой оптимизации.


Не уверен, если это наиболее эффективное решение, но я бы перебирал все записи и использовал битовый набор, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит.

Мне нравятся простые решения - и я даже верю, что это может быть быстрее, чем вычисление суммы или суммы квадратов и т. Д.





algorithm math geometry