Есть плоскость О. Есть двухмерная декартова система координат 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 — это векторное произведение.

Господа, какое это векторное произведение? а тем более смешанное...
Начнем с того что cross_product- это скаляр! а вот остальные — это векторы:
смешанное произведение — вектор коллинеарный первому,имеющий длину равную площади параллелограмма основанного на двух ост векторах.
векторное произведение — вектор, обладающий след тремя св-вами:
1.направлен перпендикулярно плоскости исходных векторов;
2.образует с ними правую тройку;
3.имеющий длину равную площади параллелограмма основанного на двух ост векторах.

ближе к сути. Я покопался и нарыл в математике следующее обоснование cross_product:
Пусть а(ax,ay) и b(bx,by) -два ненулевых вектора,отложенных от одной точки. Рассмотрим правую СК
Направленный угол между векторами a и b — угол по модулю равный неориентированному углу между a и b и имеющий положительный знак если кратчайший поворт от вектора a к b осуществляется против часовой стрелки.
*)уголы между (a и b) и (b и a) имеют разные знаки.
Величина (ax*by-bx*a1) называется косым (или псевдоскалярным) произведением векторов a и b (обозначим за {a,b}). Эта величина определяет ориентированную площадь параллелограма посторенного на векторах a и b(знак площади тот же что и у знака угла).
*)к сведению: тангенс угла между a и b равен отношению косого произведения к скалярному, те tg W=(ax*by-bx*ay)/(ax*bx+ay*by)

приводя векторык общему началу, cross_product вычисляет именно косое произведение векторов, затем мы берем его знак и сравниваем с остальными, таким образом важно при выпуклых полигонах учитывать порядок следования вершин. По такому же принципу строятся алгоритмы нахождения выпуклой оболочки множества точек и алгоритмы определения порядка следования вершин выпуклого многоугольника.
Интересно то что для нулевых векторов косое произведение неопределено и существуют контр примеры неработоспособности данного алгоритма при замене < на <= поэтому необходимо (в случае необходимости,тк в данном листинге это не рассматривается) проверять на конгруэнтность вершинам и принадлежность сторонам треугольника (достаточно чтоб cross_product==0 и выполнить && с принадлежностью проэкций точки и стороны на оси координат).
Что бы зрительно представить работу алгоритма в качесве общей вершины следует брать саму проверяемую на принадлежность треугольнику точку. Те весьма красиво получается если заменить соответствующую часть алгоритма на:

        bool cp1 = cross_product(x1, y1, x, y, x2, y2) < 0.0;
        bool cp2 = cross_product(x2, y2, x, y, x3, y3) < 0.0;
        bool cp3 = cross_product(x3, y3, x, y, x1, y1) < 0.0;

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

M> Господа, какое это векторное произведение? а тем более смешанное...
Тут вот ссылку давали выше, сходите: http://en.wikipedia.org/wiki/Cross_product.

То что вы описали — это и есть векторное произведение, в случае если векторы лежать в плоскости Oxy. Тогда действительно, векторное произведение можно рассматривать как скаляр (поскольку у него только z-компонента отлична от нуля).

А вообще же cross product — это именно векторное произведение, и никак иначе.

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

M> Господа, какое это векторное произведение? а тем более смешанное...
M>Начнем с того что cross_product- это скаляр! а вот остальные — это векторы:

Cross product — векторное произведение

M>смешанное произведение — вектор коллинеарный первому,имеющий длину равную площади параллелограмма основанного на двух ост векторах.

Triple scalar product

M>векторное произведение — вектор, обладающий след тремя св-вами:

Cross product

А вот скаларное произведение — inner product.

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

K>А вот скаларное произведение — inner product.

Еще называют dot product (обозначается точеой, по аналогии с cross product, обозначаемым крестиком)

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


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

Самое простое, что есть на эту тему, посчитать площадь исходного треугольника, и сумму площадей pAB, pAC, pBС. Затем сравнить их с некоторой точностью. Если совпали — внутри. Иначе снаружи.

Вот площадь треугольника: abs((x2-x1)*(y3-y2)-(x3-x2)*(y2-y1))/2.

В нашем случае можно и не делить на 2. Лишнее вычисление, на проверку не влияет.

Проверка с точностью выглядит так: if (abs(a-b)<eps) {...}, где const eps=0.0000001, или сколько там хочется.

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

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

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

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

Отлично работает. Если луч прошел через вершину — нужно просто учесть между лучом и каждым ребром

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

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

Стандартный способ — смотреть на знаки так называемых косых (или псевдоскалярных) произведений. Для двух векторов a{x1,x2} и b{x2,y2} косое произведение определено так: x1*y2-x2*y1 и равно ориентированной площади параллелограмма, построенного на этих векторах.

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

struct point
{
  int x;
  int y;

  point(int x, int y) : x(x), y(y)
  {}

  point operator-(const point& p) const
  { return point(x - p.x, y - p.y); }
};

int pseudoScalarProduct(const point& p1, const point& p2)
{
  return (p1.x * p2.y - p2.x * p1.y);
}

bool doesPointBelongsToNgon(const point&    p,
                            const point     ngon[], // обход против часовой стрелки
                            int             n)
{
  for(int i = 0; i < n; i++)
  {
    int ps = pseudoScalarProduct(ngon[(i+1)%n] - ngon[i], p - ngon[i]);
    if(ps == 0)
      return true;  // принадлежит стороне
    if(ps < 0)      // если по часовой, знак >
      return false; // снаружи
  }
  return true;
}

Этот алгоритм имеет сложность O(N), хотя есть вариант и за O(logN).