Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
Требуется определить, находится ли точка внутри треугольника.
Есть такое решение (оно мне кажется слишком громоздким):
проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат...

Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

Проводишь любой луч из этой точки — если луч пересечет стороны нечетное количество раз — то внутри, иначе — снаружи

Здравствуйте, Anpek, Вы писали:

A>Проводишь любой луч из этой точки — если луч пересечет стороны нечетное количество раз — то внутри, иначе — снаружи

Хреново работает, если луч прошел через вершину

Пусть ABC — треугольник, R — точка.

Тогда [AB, AR], [BС, BR], [CA, CR] должны быть одного знака.

Здравствуйте, Logic Bomb, Вы писали:

LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...



Площадь треугольника — половина векторного произведения двух его сторон, взятая по модулю. Эта формула легко записывается через координаты вершин треугольника.



Дальше делаем так:

ABCSquare = Square(A, B, C);
ABDSquare = Square(A, B, D);
BCDSquare = Square(B, C, D);
CADSquare = Square(C, A, D);
Sum = ABDSqare + BCDSquare + CADSquare;

if (ABCSquare < Sum)
     print("Outside");
else
     print("Inside");

Если нужно проверять еше и попадание на границу, то нужно проверять ABDSquare, BCDSquare, CADSquare на равенство нулю.

Здравствуйте, Logic Bomb, Вы писали:

LB>Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
LB>Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
LB>Требуется определить, находится ли точка внутри треугольника.
LB>Есть такое решение (оно мне кажется слишком громоздким):
LB>проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат...

LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

Смотрите здесь

ВАХ ВАХ ВАХ!
Спасибо всем!

Здравствуйте, Logic Bomb, Вы писали:

LB>Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
LB>Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
LB>Требуется определить, находится ли точка внутри треугольника.
LB>Есть такое решение (оно мне кажется слишком громоздким):
LB>проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат...

LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

Можно и из векторной алгебры. Достаточно посмотреть знаки следующих смешанных произведений векторов:

AB*AP, BC*BP, CA*CP. Их знаки соответствуют знакам синуса угла между векторами (с учетом направления поворота). Т.е. по сути надо чтобы относительно каждой стороны точка была всегда либо справа, либо слева в зависимости от обхода. В любом случае достаточно, чтобы у всех произведений знак совпадал. Преимущество в том, что здесь не требуется деление или корень.

Я, как правило делаю, следующим образом.

Пусть дана точка P и три вершины треугольника A, B, C.

Я считаю координаты точки относительно системы координат, образованной
векторами AB, AC с началом в точке A.

u = ((P — A) & AB) / |AB| ^ 2,
v = ((P — A) & AC) / |AC| ^ 2.

Если u < 0 || u > 1 || v < 0 || v > 1, то точка не лежит внутри
треугольника.

Если это условие не соблюдается, то повторяю тест уже в системе
координат (B, BA, BC).

P.S. & == скалярное произведение.

Logic Bomb wrote:
> Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
> Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
> Требуется определить, находится ли точка внутри треугольника.
> Есть такое решение (оно мне кажется слишком громоздким):
> проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат...
>
> Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

Сответственно, если тестов выполняется много и координаты треугольника
постоянны,
то можно предвычислить выражения типа AB / |AB| ^ 2.

sch wrote:
> Я, как правило делаю, следующим образом.

Здравствуйте, sch, Вы писали:

sch>Я, как правило делаю, следующим образом.

sch>Пусть дана точка P и три вершины треугольника A, B, C.

sch>Я считаю координаты точки относительно системы координат, образованной
sch>векторами AB, AC с началом в точке A.

sch>u = ((P — A) & AB) / |AB| ^ 2,
sch>v = ((P — A) & AC) / |AC| ^ 2.

sch>Если u < 0 || u > 1 || v < 0 || v > 1, то точка не лежит внутри
sch>треугольника.

А не проще ли проверять

u < 0 || u > 1 || v < 0 || v > 1 || v + u > 1

?

В этом случае не нужно проверять для оставшихся 2-х систем.

Здравствуйте, Logic Bomb, Вы писали:

LB>Неужли нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

Это и есть самый простой способ. И самый эффективный, не требующий делений. Есть такое понятие как cross product, вычисляется для трех точек на плоскости. Если cross products всех трех сторон по отношению к искомой точке имеют одинаковый знак, то точка внутри, оначе — снаружи.

> А не проще ли проверять
>

> u < 0 || u > 1 || v < 0 || v > 1 || v + u > 1   
>

>
> ?
>
> В этом случае не нужно проверять для оставшихся 2-х систем.

Проще.
Но я почему-то до этой простой мысли так и не дошел

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Logic Bomb, Вы писали:

LB>>Неужли нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

MS>Это и есть самый простой способ. И самый эффективный, не требующий делений.
А как-же запись уравнеия прямой? Ведь деление там как раз присутствует. Мне способ с вычислением площадей показался проще. Еще про луч понравилось. Хотя вы помогли мне посмотреть на мой способ под другим углом — пропала необходимость выяснять ориентацию треугольника. Очевидные преимущества у этого способа есть и для более сложных фигур. Количество вычислений растет в прямой пропорции с количеством сторон (речь естественно идет только о фигурах без внутренних углов)

Здравствуйте, McSeem2, Вы писали:

предыдущий пост — мой!

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, McSeem2, Вы писали:

MS>>Здравствуйте, Logic Bomb, Вы писали:

LB>>>Неужли нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу...

MS>>Это и есть самый простой способ. И самый эффективный, не требующий делений.
А>А как-же запись уравнеия прямой? Ведь деление там как раз присутствует. Мне способ с вычислением площадей показался проще. Еще про луч понравилось. Хотя вы помогли мне посмотреть на мой способ под другим углом — пропала необходимость выяснять ориентацию треугольника. Очевидные преимущества у этого способа есть и для более сложных фигур. Количество вычислений растет в прямой пропорции с количеством сторон (речь естественно идет только о фигурах без внутренних углов)

Странно %).
Cross product — это векторное умножение.
Способ уже два раза предлагался. И тем не менее пользуется популярностью %)

Здравствуйте, Аноним, Вы писали:

А>А как-же запись уравнеия прямой? Ведь деление там как раз присутствует. Мне способ с вычислением площадей показался проще. Еще про луч понравилось. Хотя вы помогли мне посмотреть на мой способ под другим углом — пропала необходимость выяснять ориентацию треугольника. Очевидные преимущества у этого способа есть и для более сложных фигур. Количество вычислений растет в прямой пропорции с количеством сторон (речь естественно идет только о фигурах без внутренних углов)

    inline double cross_product(double x1, double y1, 
                                double x2, double y2, 
                                double x,  double y)
    {
        return (x - x2) * (y2 - y1) - (y - y2) * (x2 - x1);
    }



    bool point_in_triangle(double x1, double y1, 
                           double x2, double y2, 
                           double x3, double y3, 
                           double x,  double y)
    {
        bool cp1 = cross_product(x1, y1, x2, y2, x, y) < 0.0;
        bool cp2 = cross_product(x2, y2, x3, y3, x, y) < 0.0;
        bool cp3 = cross_product(x3, y3, x1, y1, x, y) < 0.0;
        return cp1 == cp2 && cp2 == cp3 && cp3 == cp1;
    }

Способ так же работет для любого выпуклого полигона. Для произвольного полигона — вкуривать Eric Haines, Point In Polygon Strategies.

Для определения CW/CCW достаточно вычислить Cross Product для трех точек треугольника. Если меньше нуля, значит CCW, в предаоложениии, что ось Y направлена вверх.

Здравствуйте, Logic Bomb, Вы писали:

LB>Неужели нет алгоритма проще?

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

0.находим для каждой стороны каноническое уравнение Ax+By+C=0 (!рассмотреть случай параллельности осям координат);
Если не параллельны:
1.проверяем на принадлежность сторонам:
пусть (x1,y1)<->(x2,y2)<=>Ax+By+C=0 — проверяемая сторона, тогда:

return ((A*x0+B*x0+C==0)&&(((x0>=min(x1,x2))&&(x0<=max(x1,x2))))||((y0>=min(y1,y2))&&(y0<=max(y1,y2))))));

2.ну тогда проверяем три аналогичных условия для каждой стороны:
пусть (x1,y1)<->(x2,y2)<=>Ax+By+C=0 — проверяемая сторона, тогда:

bool usl1=((A*x0+B*y0+C)*(A*x3+B*y3+C)>0);

потом делаем —

return (usl1 && usl2 && usl3);

В принципе просто 2- проверяем чтоб точка противоположная стороне лежала в тойже полуплоскости и исходной точкой
проверять на параллельность осям координат просто — из равенства нулю разности иксов или игриков концов стороны, сразу заполняем uslX. и еще — очевидно что если две стороны параллельны осям, то третья — нет (типа оптимизации

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Аноним, Вы писали:

MS>

MS>    inline double cross_product(double x1, double y1, 
MS>                                double x2, double y2, 
MS>                                double x,  double y)
MS>    {
MS>        return (x - x2) * (y2 - y1) - (y - y2) * (x2 - x1);
MS>    }

Фишка в том,что это определение полуплоскости относительно прямой заданной уравнением:
(x-x2) = (y-y2)
(x2-x1) (y2-y1)
как я пологаю cross_product получен умножением этого уравнения на (x2-x1)*(y2-y1), но умножать мы имеем право только если это не ноль! дело в том,что каноническое уравнение это совсем не уравнение, а пропорция, поэтому мы имеем право рисовать дробь, а вот если его рассмастривать как уравнение необходимо проверять на ноль, который может получиться если сторона параллельна какой-нибудь оси координат,вот опять никуда не делись.
Еще — я не согласен с проверкой на отношение к нулю этого выражения , в этом случае нужно проверять на принадлежность стороне данной точки(те равенство нулю и принадлежность к промежутку...), и лучше еще сравнивать результаты не между собой, а с этим выражением для противоположной вершины в случае с прямоугольными треугольниками, хотя, думаю, это лишне — лучше вместо '...<0' писать '...<=0' и проверять на параллельность, но что оптимальней, опятьже —

Здравствуйте, ministr, Вы писали:

M>Здравствуйте, McSeem2, Вы писали:

M>Фишка в том,что это определение полуплоскости относительно прямой заданной уравнением:
M> (x-x2) = (y-y2)
M>(x2-x1) (y2-y1)
M>как я пологаю cross_product получен умножением этого уравнения на (x2-x1)*(y2-y1), но умножать мы имеем право только если это не ноль! дело в том,что каноническое уравнение это совсем не уравнение, а пропорция, поэтому мы имеем право рисовать дробь, а вот если его рассмастривать как уравнение необходимо проверять на ноль, который может получиться если сторона параллельна какой-нибудь оси координат,вот опять никуда не делись.

cross_product — это обычное смешанное произведение векторов: здесь, которое никак не зависит от ориентации векторов относительно осей, а зависит только от их длин и ориентации относительно друг друга.

M>Еще — я не согласен с проверкой на отношение к нулю этого выражения , в этом случае нужно проверять на принадлежность стороне данной точки(те равенство нулю и принадлежность к промежутку...), и лучше еще сравнивать результаты не между собой, а с этим выражением для противоположной вершины в случае с прямоугольными треугольниками, хотя, думаю, это лишне — лучше вместо '...<0' писать '...<=0' и проверять на параллельность, но что оптимальней, опятьже —

Равенство нулю говорит о том, что точка лежит на прямой, проходящей через сторону. Если точка должна лежать строго внутри треугольника, то в случае равенства нулю хотя бы одного из произведений можно сразу говорить, что не лежит внутри. Поэтому все произведения должны быть > 0 или все < 0.

В противном случае варианты следующие. Если ровно одно из смешанных произведений равно нулю, значит точка лежит на соотв. стороне, поэтому относительно двух других сторон достаточно иметь один и тот же знак произведения. Если 2 равны нулю, то точка совпадает с вершиной и третье произведение вообще роли не играет. Т.е во всех случаях достаточно проверить, что все произведения >= 0 или все <= 0. Больше дополнительно ничего проверять не нужно.

Здравствуйте, twisted_mind, Вы писали:

_>cross_product — это обычное смешанное произведение векторов
cross product — это векторное произведение.