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

Как проверить принадлежность точки (X, Y) к треугольной области (X1, Y1; X2, Y2; X3, Y3)??? Помогите пожалуйста, очень надо!!!

 

X должна быть одновременно больше 2-х координат и меньше 1-й координаты, либо меньше 2-х координат и больше 1-й, соответственно с игрик.

 

???

 

напиши процедуру. и пихай туда сначала х, потом у

 

Данное условие является недостаточным! Т.к. имеются точки удовлетворяющие этому условию, но не принадлежащие данному треугольнику!

 

twgt

Это условие необходимое, но не достаточное, что легко проверяется на элементарных примерах. Варианты достаточных условий
1) метод луча: луч, например x:=Xo проведенный вправо от точки, должен либо пересекать одну (и только одну) сторону треугольника, либо проходить через его вершину и при этом отрезки, выходящие из этой вершины, должны лежать по разные стороны от луча.
2) метод обхода контура: точка должна лежать по одну сторону от всех трех (направленных) прямых, проходящих через стороны треугольника

PS: О, пока я сочинял ответ, AlexPAV_NSO уже убедился в недостаточности простых сравнений X, Y

PPS: Добавил доп.условие для случая прохождения луча через вершину

 

leo
Эхх... а я тут разрисовался блин.. не успел ))))

 

nitrotoluol
Только еще 4 хитрых случая не нарисовал: прохождение луча через вершину и через сторону треугольника когда точка внутри (или на стороне) и снаружи

 

leo
Там и одного случая хватит, хотя если признаться, мне только 2 варианта в голову пришло... )) Вот этот и с углами. Там по теореме синусов углы находим и сравниваем то что приводилось twgt
плюс сравниваем улол между двумя сторонами и одной из этих сторон и лучом.

А с вершиной там как...?

 

nitrotoluol

В методе луча можно и без синусов обойтись только сравнением координат.
Луч, проведенный из точки (X0,Y0) вправо пересекает отрезок (X1,Y1)-(X2,Y2) если
((Y1 >= Y0) or (Y2 >= Y0)) and ((X1 >= X0) xor (X2 >= X0))
Если пересечение оказывется в вершине, т.е. X1=X0 или X2=X0, то смотрим как расположены Y противоположных точек отрезков, например при X2 = X0 д.б. (Y1 >= Y0) xor (Y3 >= Y0), в противном сл.точка лежит вне треугольника и луч просто касается вершины __\/__

PS: из-за возможности прохождения луча через отрезок (т.е. через две вершины __/_\_), проверки на равенство д.б. похитрее

 

Самый простой метод - посчитать площади треугольников:
если дан треугольник ABC, точка X, то
S(ABC) = S(ABX)+S(ACX)+S(BCX), если точка лежит внутри треугольника.
Площади легко считать по формуле Герона

 

maxdiver

ИМХО, ориентированная площадь по координатам считается проще и быстрее

 

maxdiver

Раз пошла такая пьянка, то самый простой способ в данном случае - обход контура
Точка строго внутри треугольника, если все три величины
side1 = (Y2-Y1)*(Xo-X1)-(X2-X1)*(Yo-Y1)
side2 = (Y3-Y2)*(Xo-X2)-(X3-X2)*(Yo-Y2)
side3 = (Y1-Y3)*(Xo-X3)-(X1-X3)*(Yo-Y3)
имеют один и тот же знак

 

А вообще в fp принимаются решения?

Мой вариант:
Берем иссл. точку(S) и ближайшую и ней(A). Если S внутри ABC, то расстояния от нее до C и D меньше расстояний до тех же вершин от точки A.
Реализуется элементарно, на мой взгляд.

 

dr_dred
Во-первых откуда взялась вершина D? Во-вторых, если там не D, а B, то условие недостаточное.

 

Да, опечатка вышла, но почему недостаточно такой проверки?

 

dr_dred

Не достаточное условие. Возьми точку вблизи стороны острого угла, и увидишь что она может быть как внутри, так и снаружи, хотя расстояния до вершин меньше. А лучше проведи круги из B и C через A и убедись, что область их пересечения выходит за пределы треугольника

 

Понятно, спасибо.

 

В Win есть функция PtInRegion(RGN: HRGN; X, Y: Integer): Bool (gdi32.dll) для областей, но работает она слишком медленно!

 

leo
Это же уравнение прямой на плоскости через две точки практически!
Интересное решение, надо запомнить.