Как проверить принадлежность точки (X, Y) к треугольной области (X1, Y

Вот, что у меня в итоге получилось:
_______________________________

Код (Text):

1. function InTrian(X0, Y0, X1, Y1, X2, Y2, X3, Y3: Integer): boolean;
2.  
3. function Side(pX1, pY1, pX2, pY2: Integer): Integer;
4. begin
5. Result:= (pY2-pY1)*(X0-pX1)-(pX2-pX1)*(Y0-pY1);
6. end;
7.  
8. function InLine_(X1, Y1, X2, Y2: Integer): boolean;
9. begin
10. if Y1 <> Y2 then begin
11.        Result:= (X1 - X0)*(Y1 - Y2) = (X1 - X2)*(Y1 - Y0);
12. end else
13.        Result:= Y0 = Y1;
14.  
15. Result:= Result
16. and (X0 >= min(X1, X2)) and (X0 <= max(X1, X2))
17. and (Y0 >= min(Y1, Y2)) and (Y0 <= max(Y1, Y2));
18. end;
19.  
20. begin
21.  
22. Result:= (sign(side(X1, Y1, X2, Y2)) = sign(side(X2, Y2, X3, Y3))) and
23.              (sign(side(X1, Y1, X2, Y2)) = sign(side(X3, Y3, X1, Y1))) or
24. InLine_(X1, Y1, X2, Y2) or InLine_(X2, Y2, X3, Y3) or InLine_(X3, Y3, X1, Y1);
25.  
26. end;

 

Всем огромное спасибо!!!

 

dr_dred
Если ты о side, то это ненормированный синус угла между векторами

AlexPAV_NSO
Что-то слишком сложно наворотил Если нужно включать в область точки на границе треугольника, то это определяется по side=0 и проверками типа (X0-X1) xor (X0-X2) < 0. На дельфях без особой оптимизации можно сделать например так:

Код (Text):

1. var
2.   s1,s2,s3:integer;
3.   function Side(pX1, pY1, pX2, pY2: Integer): Integer;
4.   begin
5.     Result:=(pY2-pY1)*(X0-pX1)-(pX2-pX1)*(Y0-pY1);
6.     if Result > 0 then
7.       Result:=1
8.     else
9.     if Result < 0 then
10.       Result:=-1
11.     else
12.     if not (((X0-pX1) xor (X0-pX2) < 0) or ((Y0-pY1) xor (Y0-pY2) < 0)) then
13.       Result:=2;      //точка на продолжении отрезка -> вне треугольника
14.     //else Result:=0   //точка на отрезке
15.   end;
16. begin
17.   s1:=Side(X1,Y1,X2,Y2);
18.   s2:=Side(X2,Y2,X3,Y3);
19.   s3:=Side(X3,Y3,X1,Y1);
20.   Result:=(s1 and s2 and s3 <= 0) or (s1 or s2 or s3 = 1);
21. end;

 

leo
Я предложил тот метод, который понятен даже при школьном уровне знаний, т.е. в данной ситуации самый простой метод.

 

leo
Если приравнять уравнение и нулю, перевести думаю в правую часть, потом провести разделение переменных, получится то уравнение с переменной х0.
Соотв. если разность больше нуля, то точка по одну сторону прямой, меньше - по другую, а если 0, то на прямой.
Я себе это так представил.

 

maxdiver
Насчет понятности на школьном уровне, пожалуй ты прав.
Только при чем тут "в данной ситуации" ) Аналитическую геометрию на первом курсе изучают, а метод луча и вовсе на одних сравнениях X,Y построен, только усидчивость нужна, чтобы все особые случаи рассмотреть

 

leo
Да, я сам на первом курсе, и формулы пока не забыл
Но вот с точки зрения понятности и запоминаемости - ИМХО проще площадь по Герону - всё-таки "старая добрая" формула

 

dr_dred
Конечно можно интерпритировать по разному, но все таки по физическому смыслу выражение
side = dY1*dX2-dX1*dY2 это синус угла между векторами единичной длины
Согласно той же школьной тригонометрии, к которой аппелирует maxdiver
dX = A*cos(a), dY = A*sin(a), где A - длина отрезка (вектора), a - угол наклона
Синус угла между двумя отрезками определяется через углы наклона по известной формуле
sin(a2-a1) = sin(a2)*cos(a1)-cos(a2)*sin(a1) = dY2'*dX1'-dX2'*dY1', где dX', dY' - это dX,dY нормированные на длину отрезка. Знак этого синуса определяет находится ли один вектор левее (угол от 0 до 180 гр) или правее другого (угол от 180 до 360). Ну и если нас интересует только знак, а не само значение синуса, то мы можем вместо нормированных dX',dY' использовать ненормированные, отбросив множитель 1/(A1*A2)

Вроде все ясно и понятно, вполне на школьном уровне. Но maxdiver'у почему-то больше нравится площадь по Герону, видимо название красивое и запоминающееся )

 

по моему лучше идеи с площадью нету

 

Ulv
Да нет. Вариант leo гораздо проще реализуется, оптимизируется легче (то же извлечение корня не нужно). Да и с площадями нельзя определить, находится ли точка на границе треугольника. Метод leo этого недостатка лишен.

 

Я кстати и не возражал против метода сравнения площадей как такового. Вопрос лишь в том как считать эти площади. Формула Герона тут никак не катит, т.к. его удобно использовать лишь в случае, когда треугольник задан длинами сторон. Если же заданы координаты вершин, то легко представить, во что выливается расчет площади по Герону. Если заданы координаты вершин, то самым простым и универсальным способом расчета площади, справедливым для любого многоугольника, является расчет так называемой ориентированной площади методом трапеций Ss = Сумма{(Y[i+1]+Y)*(X[i+1]-X)/2}. Ориентированная площадь имеет знак (+), если обход многоугольника осуществляется по часовой стрелке и знак (-) если против, поэтому для получения обычной площади берется абс.значение S=abs(Ss). (Кстати такую или подобную методику расчета площади и в школе проходят, только не по геометрии, а по алгебре при изучении интегралов).
Теперь остается открыть великую тайну для тех, кто в школе зубрил формулы и не научился самостоятельно решать простейшие задачки из жизни треугольников )
Теорема:
Величина side = (Y2-Y1)*(X0-X1)-(X2-X1)*(Y0-Y1) = 2*Ss, где Ss - ориентированная площадь треугольника 0-1-2
Док-во №1: Как было показано выше side = A01*A12*sin(a1), где A01 и A12 - длины сторон 0-1 и 1-2, a1 - величина угла 0-1-2. Учитывая, что A01*sin(a1) = h - высота треугольника, получаем side = h*A12 = 2*Ss (площадь теугольника = 1/2 основания * высоту). Ч.т.д.
Док-во №2: Удвоенное значение ориентированной площади по методу трапеций
2*Ss = (Yo+Y1)*(X1-X0)+(Y1+Y2)*(X2-X1)+(Y2+Y0)*(X0-X2)
После элементарных преобразований (рекомендуемых в качестве домашнего задания получаем
side = 2*Ss = Y0*(X1-X2)+Y1*(X2-X0)+Y2*(X0-X1). Ч.т.д

Выводы:
1) Поскольку все таки речь идет о программировании, то критерии "лучше"\"проще" должны определяться вычислительной сложностью алгоритма, а не абстрактными представлениями о понятности на школьном уровне. Для всех рассмотренных методов достаточно школьного уровня, но число и латентность операций для их реализации могут быть существенно разными. И площадь по Герону тут ни в какие разумные рамки не лезет, уж лучше использовать апишную PtInRegion - куда уж проще и нагляднее )
2) По сути метод обхода контура и метод сравнения площадей взаимосвязаны, т.к. оба основаны на расчете (ориентированных) площадей треугольников и отличаются только способом принятия решения. В методе обхода все удвоенные площади 2*Ss = {s1,s2,s3} должны иметь один знак + необходим доп.анализ на принадлежность точке стороне при s = 0. В методе сравнения площадей точка попадает в контур (в т.ч. принадлежит стороне) при выполнении условия
abs(s1+s2+s3) = abs(s1)+abs(s2)+abs(s3)
Что в итоге будет быстрее уже зависит от конкретной реализации функций abs и sign. При безбранчевой реализации abs на асме, пожалуй сравнение площадей по вышеприведенной формуле можно реализовать проще и быстрее. Посему констатируем - метод площадей при соответствующей оптимизации рулит. Ура, победила дружба )

 

Добавлю до кучи (метод луча для произвольного замкнутого контура)
//x,y - координаты точки; poly - координаты вершин контура; n - число вершин контура

Код (Text):

1. int PointInPoly(float x, float y, TPoint* poly, int n)
2. {
3.     int     Count = 0;
4.    
5.     for (int i = 0; i < n; i++)
6.     {
7.         int j = (i + 1) % n;
8.         float pix = poly[i].x;
9.         float piy = poly[i].y;
10.         float pjx = poly[j].x;
11.         float pjy = poly[j].y;
12.         if (piy == pjy) continue;
13.         if (piy > y && pjy > y) continue;
14.         if (piy < y && pjy < y) continue;
15.         if (max(piy, pjy) == y)
16.         {
17.                 if (piy == y && pix >= x) {Count++; continue;}
18.                 if (pjy == y && pjx >= x) {Count++; continue;}
19.         }
20.         if (min(piy, pjy) == y) continue;
21.         float T = (y - piy)/(pjy - piy);
22.         if (T > 0.0 && T < 1.0 && pix + T*(pjx - pix) >= x) Count++;
23.     }
24.     return (Count & 1);
25. }

 

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

 

crypto
В твоем варианте реализации метода луча особые случаи попадания точки на границу контура обрабатываются по разному:

Код (Text):

1.  _._/   \_._    \_._/    _._     \ /     .
2. /           \           /   \     '     / \
3.  out      in     out      in     out    out

 

leo
Угу, вижу. Спасибо.
ЗЫ
Ты книги не пишешь? Я бы с удовольствием почитал.

 

Нет. Книги и статьи это серьезное литературное творчество, а меня хватает только на безответственные отрывочные заметки в форумах )

 

leo
Значит самая пора заняться серьезным творчеством
Не, я совершенно серьезно! Думается мне, что, к примеру, одни твои заметки по-поводу оптимизации кода с учетом процессорных тонкостей потянут на хорошую настольную книгу.