-
Если известно, что точка лежит в одной плоскости
с треугольником, то как узнать внутри она треугольника
или нет?????
-
-
А как по отрезку M1 (0,1,2) - M2(-1,-3,4)
найти уравнение прямой (x-x1)/m = (y-y1)/n = (z-z1)/p ?????????
-
> [2] Кошкин (04.07.09 18:20)
А это знает АнГя за первый курс.
-
-
Как вариант:
Проводим три вектора из точки лежащей в плоскости треугольника к вершинам этого треугольника. Вычисляем углы между векторами. Если сумма этих углов равна 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 тады сорри
-
Всё проще. function PtInTriang(const P, A, B, C: TPoint): Boolean;
function _PIT(const C1, C2, C3: TPoint): Boolean;
begin
Result :=
((P.x-C1.x)*(C1.y-C2.y) - (P.y-C1.y)*(C1.x-C2.x) >= 0) and
((P.x-C2.x)*(C2.y-C3.y) - (P.y-C2.y)*(C2.x-C3.x) >= 0) and
((P.x-C3.x)*(C3.y-C1.y) - (P.y-C3.y)*(C3.x-C1.x) >= 0);
end;
begin
if (A.x-B.x)*(C.y-B.y) > (A.y-B.y)*(C.x-B.x)
then Result := _PIT(A, C, B)
else Result := _PIT(A, B, C);
end; Если известно направление перечисления вершин, то можно упростить (сразу _PIT(A, B, C) без проверки).
-
> oldman © (16.07.09 13:05) [13]
>
> Можно проще.
> Если провести перпендикуляры из точки на все три стороны
> треугольника и точки пересечения перпендикуляров и прямых,
> на которых лежат стороны треугольника, будут принадлежать
> отрезкам сторон треугольника, точка находится внутри треугольника.
>
Это не так, причем в обе стороны.
Перпендикуляр может не попадать на сторону, а точка будет внутри. И наоборот, все перпендикуляры на сторонах, а точка снаружи.
|
Есть новые 
Нет новых [134430 +2][b:0][p:0.001]