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

Question

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

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

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-s-t. Точка p находится внутри треугольника тогда и только тогда, когда все они положительны.

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

РЕДАКТИРОВАТЬ 2: Для еще большей вычислительной эффективности, см. Комментарий coproc ниже (который подчеркивает, что если заранее известна ориентация узлов треугольника (по часовой стрелке или против часовой стрелки), деление на 2*Area в выражениях для s и t можно избежать). См. Также Perro Azul * jsfiddle-код в комментариях к ответу Andreas Brinck .

Answer 4

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

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? Если это правда, это не может быть внутри. Если ложно, это по крайней мере внутри "конусов", которые удовлетворяют условию. Теперь, когда мы знаем, что точка внутри треугольника (треугольника) должна находиться на той же стороне AB, что и BC (и также CA), мы проверяем, отличаются ли они. Если они есть, s не может быть внутри, иначе s должен быть внутри.

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

Answer 5

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);
}

_{[ edit ]}
^{принято предложенное изменение @Pierre; см. комментарии}

Answer 6

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

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

Answer 7

Простой способ:

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

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

черная пешка и вольфрам

Answer 8

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

• не распределяет умножение по скобкам
• избегая вычисления нескольких раз одних и тех же терминов, сохраняя их
• сокращение сравнения (как указано coproc и Thomas Eding )

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

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 )

Ведущий к:

• переменная "вызывает": 30
• переменная память: 7
• дополнения: 4
• вычитаний: 8
• умножений: 6
• делений: нет
• сравнения: 4

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

Answer 9

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

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

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

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

Преимущества:

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

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

Answer 10

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

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