Если известно, что точка лежит в одной плоскости
с треугольником, то как узнать внутри она треугольника
или нет?????

гугл знает.
http://acmp.ru/article.asp?id_text=174

А как по отрезку M1 (0,1,2) - M2(-1,-3,4)

найти уравнение прямой   (x-x1)/m = (y-y1)/n = (z-z1)/p     ?????????

> [2] Кошкин   (04.07.09 18:20)

А это знает АнГя за первый курс.

http://www.nuru.ru/mat/geom/004.htm

больше за вас гуглить не буду

Как вариант:
Проводим три вектора из точки лежащей в плоскости треугольника к вершинам этого треугольника. Вычисляем углы между векторами. Если сумма этих углов равна 360 градусов, занчит точка лежит внутри треугольника, иначе - снаружи.
P.S.
Код приводить не буду, я похоже неправильно считаю углы и у меня в сумме выходит 400, но так как работает стабильно решил так и оставить.

можно ещё по площадям, используя формулу Герона

А что работает быстрее?

> [7] Galiaf   (08.07.09 19:34)

Тесты покажут.
Вообще скорее всего результат буждет примерно одинаковый.

вариант с площадям хорош ещё и тем, что даст отрицательный результат в том случае, если точка не лежит в плоскости треугольника

> Кошкин   (04.07.09 06:22)  
> Если известно, что точка лежит в одной плоскости
> с треугольником, то как узнать внутри она треугольника
> или нет?????


Вопрос первого курса института по инженерной графике.
Заливаем плоскость белым цветом, треугольник черным.
Если пиксель по координатам точки черного цвета - точка внутри треугольника (или на его границе), если белого - нет.

> [10] oldman ©   (16.07.09 12:38)

Это жесть. :) Не применимо на практике, ибо треугольников 200 000. А заливка страшно не быстрая штука.

> oldman ©   (16.07.09 12:38) [10]
А я уж, грешным делом, подумал, что некроманы на форуме извелись. Видно слишком рано обрадовался:(
Тем более, что ничего нового в ветку не добавил.

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

Для [13] необходимо:

1. Уравнение перпендикуляра
2. Уравнение точки пересечения
3. Уравнение принадлежности точки отрезку

Да здравствует гугль и википедия!

// проверка вхождения точки в треугольник ***********************************
 // умножений - 6; сложений  - 12;
 // UseBorder=True  - с учетом точек принадлежащих сторонам треугольника
 // UseBorder=False - без учета точек принадлежащих сторонам треугольника
 function InTriangle(const P,P1,P2,P3:TRealPoint; const UseBorder:Boolean=False):Boolean;
  var S,AB,V1,V2 : TRealPoint;
      D          : Real;
  begin
   V1.X := P2.X - P1.X;
   V1.Y := P2.Y - P1.Y;
   V2.X := P3.X - P1.X;
   V2.Y := P3.Y - P1.Y;
   D    := V1.X * V2.Y - V1.Y * V2.X;
   S.X  := P.X - P1.X;
   S.Y  := P.Y - P1.Y;
   AB.X := V1.X * S.Y - V1.Y * S.X;
   AB.Y := V2.Y * S.X - V2.X * S.Y;
   if UseBorder then
    if D>0 then Result := ABEQ(AB.X,0) and ABEQ(AB.Y,0) and LSEQ(AB.X + AB.Y,D)
           else Result := LSEQ(AB.X,0) and LSEQ(AB.Y,0) and ABEQ(AB.X + AB.Y,D)
   else
    if D>0 then Result := (AB.X>0) and (AB.Y>0) and (AB.X + AB.Y<D)
           else Result := (AB.X<0) and (AB.Y<0) and (AB.X + AB.Y>D);
  end;

да и ещё
 // **************************************************************************
 function ABEQ(const R1,R2:Real):Boolean; // True if R1 >= R2
  begin
   Result := (Abs(R1-R2)<INF) or (R1>R2);
  end;

 // **************************************************************************
 function LSEQ(const R1,R2:Real):Boolean; // True if R1 <= R2
  begin
   Result := (Abs(R1-R2)<INF) or (R1<R2);
  end;

хотя если вопрос по 3D тады сорри

Всё проще.




Если известно направление перечисления вершин, то можно упростить (сразу _PIT(A, B, C) без проверки).

> oldman ©   (16.07.09 13:05) [13]
>
> Можно проще.
> Если провести перпендикуляры из точки на все три стороны
> треугольника и точки пересечения перпендикуляров и прямых,
>  на которых лежат стороны треугольника, будут принадлежать
> отрезкам сторон треугольника, точка находится внутри треугольника.
>

Это не так, причем в обе стороны.
Перпендикуляр может не попадать на сторону, а точка будет внутри. И наоборот, все перпендикуляры на сторонах, а точка снаружи.

> Если известно, что точка лежит в одной плоскости с треугольником

Желательно это показать с помощью уравнений, иначе это просто ничего не значит, а, следовательно, и все последующие решения или попытки решений
:)

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

> kyky   (04.09.09 15:59) [20]

Каких уравнений? Условие такое. А если точно известно, что точка лежит в плоскости треугольника, то достаточно рассмотреть проекцию на XY, чтобы сказать, внутри ли она. см [21].

Есть треугольник с координатами углав X1Y1, X2Y2, X3Y3 и точка X4Y4
Среди X и Y найдем мин и макс
Треугольник как-бы "вписан" в прямоугольник XminYmin XmaxYmax (два угла треугольника всегда лежат на периметре пямоугольника)
Естественно, X4 и Y4 должны лежать внутри этого прямоугольника, чтобы точка могла принадлежать треугольнику

Если точка лежит вне треугольника, то
ХОТЯ БЫ ОДИН ИЗ ОТРЕЗКОВ (ТОЧКА-УГОЛ ПРЯМОУГОЛЬНИКА) НЕ ПЕРЕСЕКАЕТСЯ СО СТОРОНАМИ ТРЕУГОЛЬНИКА.

ЗЫ: Что-то меня все на простейшую геометрию тянет, но так проще писать проверку

А может все проще?

Точка принадлежит стороне треугольника [1] или отрезки (точка-углы треугольника) не пересекаются со сторонами треугольника [2].

> Кошкин   (04.07.09 06:22)  
> Если известно, что точка лежит в одной плоскости
> с треугольником


А че всех на 3D пробило?

> Galiaf   (08.07.09 03:23) [5]
> Как вариант:

И это правильно. Считать ориентированные углы.  Если модуль 2pi - то в плоскости и внутри. Если другойе значение - то вне треугольника или вне плоскости. Прчем если 0 - то вне треуга и в плоскости, а остальные значения - вне плоскости.

> oldman ©   (05.09.09 09:15) [25]

А тебе уже писал, не знаешь как решать не пиши. Поучаешь всех за школьную, а сам пишешь ерундой постоянно про нее.

> Дуб ©   (07.09.09 06:43) [27]


Мда... Все варианты я не просчитал...

Пардон, больше не буду!

вариант:
если отрезки, соединяющие точку с вершинами треугольника, не пересекают стороны треугольника, то точка находится внутри треугольника.
Кому уравнения написать?

> вариант:
> если отрезки, соединяющие точку с вершинами треугольника,
>  не пересекают стороны треугольника, то точка находится
> внутри треугольника.
> Кому уравнения написать?

вариант неверный

CrytoGen докажи!

CrytoGen,
чтобы уж совсем точно, то :
" ... не пересекают стороны треугольника и не находятся со сторонами на одних и тех же прямых, то ... ".

[32] - добавка, вероятно, лишняя.

>докажи!
равносторонний треугольник, точка вне его на продолжении медианы

МВо, твоя правда :)
А если так?
Если отрезки, соединяющие точку с вершинами треугольника, не пересекают стороны треугольника, и (!) точка находится внутри описанной окружности, то точка находится внутри треугольника.

> докажи!

http://chart.apis.google.com/chart?cht=lxy&chs=250x100&chls=2,1,0|1,1,2|1,1,2&chd=t:0,60,30,0|0,0,50,0|0,30,6 0|0,80,0|30,30|80,50

опоздал с рисунком.

Удалено модератором
Примечание: неправильно понял

>А если так?
Зачем наворачивать, если есть несколько простых способов:
1. Сумма углов от точки к вершинам = 2*Pi
2. Сумма площадей треугольников, образованных точкой и вершинами тр-ка, равна площади тр-ка
3. Луч из точки в любую сторону пересекает нечетное количество сторон
4. Точка находится по одну сторону от лучей сторон, направленных в порядке обхода
5. Разложить вектор AP по векторам AB и AC. Коэффициенты должны быть положительны, и сумма не превышать 1.

Первые 4 способа подходят для произвольных выпуклых многоугольников.

Два последних способа - самые быстрые, я предпочитаю 5-й, поскольку он для меня более нагляден.

МВо - вот это круто! Respect и т.д.
Первые пара-тройка способов, помнится, ещё в школе упоминались.
Остальные - весьма занимательно.

Поздравляю! Исчерпывающий ответ!

2MBo

4-й способ - самый оптимальный. Во-первых, всего три скалярных произведения, во-вторых, если точка лежит вне треугольника, есть хороший шанс, что нужно будет посчитать всего одно или два. Минус метода ровно один - надо знать направление обхода :) Но в моих задачах (сетки) оно всегда известно ;) Так что я юзаю в основном его.

Про пятый способ не знал, спасибо :) Тоже неплохой, вего 4 скалярных произведения надо посчитать. И на случай тетраэдра обобщается...

>Franzy
в пятом тоже три произведения
Да, на тетраэдр обобщается, на параллелепипед, и на параллелограмм (собственно, треугольник рассматривается как половина параллелограмма)

> Franzy   (08.09.09 15:02) [41]
> Минус метода ровно один - надо знать направление обхода :)

Можно и не знать, это решаемо - см. [18].