Треугольник АВС и точка P. Кто помнит геометрию?

← →
Aleksey_a (2004-09-28 03:32) [0]

Простая вроде задача но никак не могу вспомнить. Дано три точки на плоскости A(Aх,Aх), B(Bx,By) и C(Cx,Cy) (треугольник). Нужно решить задачу попадания или непопадания точки P(Px,Py) в этот треугольник.

← →
Darth (2004-09-28 04:18) [1]

точка должна лежать справа от AB, BC и CD.

← →
Aleksey_a (2004-09-28 05:46) [2]

А можно попонятней? Что такое справа и как это выглядит в формуле?

← →
ЮЮ © (2004-09-28 06:18) [3]

Z-координата векторных произведений ABхAP, BCxBP и CAxCP должны быть (положитедьны/отрицательны - не помню, поищи теорию)

← →
Булат Шакиров (2004-09-28 06:36) [4]

http://algolist.manual.ru/maths/geom/belong/poly2d.php

← →
MBo © (2004-09-28 07:55) [5]

все скалярные произведения нормалей сторон на векторы точка-соотв. вершина должны быть положительны (при нумерации вершин против час. стрелки)

← →
Sodom (2004-09-28 09:33) [6]

А если подойти к этому проще. Нарисуй треугольник, точку, закрась его и посмотри совпадает ли цвет точки с цветов заливки. :)

← →
Леван (2004-09-28 10:11) [7]

Пусть Fab(m)=0 - уравнение прямой, проходящей через точек "a","b":

(x-xa)/(xb-xa)-(y-ya)/(yb-ya)=0

условие, что точка "с" и точка "p" лежат по одной стороне линии ab, заключается в
Fab(c)*Fab(p)>0
т.е. если

Fab(c)*Fab(p)>0
Fbc(a)*Fbc(p)>0
Fac(b)*Fac(p)>0
то точка p лежит внутри треугольника abc

← →
Денис К. (2004-09-28 10:56) [8]

Как я понял речь идет про плоскость, а не про пространство.
Тогда, если знаешь что такое векторное произведение, то
M = AB x AP
N = BC x BP
Q = CA x CP
Знаки M.z, N.z, Q.z должны быть одинаковыми (либо "+" либо "-"),
а если какая-то из координат *.z = 0 то точка лежит на стороне или ее продолжении.

← →
alexsh (2004-09-30 20:49) [9]

Если сумма площадей треугольников PAC, PAB, PBC равна площади треугольника ABC, то точка лежит внутри треугольника

← →
Darth (2004-09-30 22:58) [10]

alexsh или на одной из его граней. Или является одной из его вершин.

← →
EViruS (2004-10-01 05:51) [11]

Есть много вариантов. Вот простейшие:
1) школьная геометрия
2) составить ур-я прммых и поглядеть как расположена точка относительно их
3) пройтись по всем вершинам (против ЧС) и проверить как располоден отрезок из вершины до точки и до след вершины, если он всегда правый, то следовательно точка в треугольнике
В общем, algolist.manual.ru

Стоит почитать про выпуклые оболочки или расположение точек относительно прямой.

← →
alexshx (2004-10-04 18:14) [12]

Darth, я с тобой не согласен. Если точка лежит на одной из сторон треугольника, то одна из площадей треугольников PAC, PAB, PBC будет равна 0, а сумма площадей двух остальных и будет равна площади треугольника ABC. В случае, если заданная точка P - одна из вершин, то две из площадей PAC, PAB, PBC будут равны 0, а площадь оставшегося треугольника будет равна площади треугольника ABC.

← →
oldman © (2004-10-04 18:19) [13]

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

← →
oldman © (2004-10-04 18:20) [14]

поправочка - если тоска пересечения совпадает с искомой - точка лежит на стороне

← →
Fenik (2004-10-08 00:03) [15]

http://delphibase.endimus.ru/?action=viewfunc&topic=mathcalc&id=10560

← →
XProger © (2004-10-08 01:42) [16]

//Положение точки p относительно прямой (p1, p2) function Side(p, p1, p2: TPoint): boolean; var a, b: TPoint; begin a.X := p2.X - p1.X; a.Y := p2.Y - p1.Y; b.X := p.X - p1.X; b.Y := p.Y - p1.Y; Result := (a.X * b.Y - a.Y * b.X) >= 0; end; cur := Point(X, Y); if Side(cur, p[1], p[2]) and Side(cur, p[2], p[3]) and Side(cur, p[3], p[1]) then Caption := "В яблочко!!!" //соответственно =) else Caption := "Неа!"; //Не попал =)

← →
Megabyte-ceercop © (2004-10-08 07:04) [17]

Самые быстрые формулы в виде условий без вызора доп функций.

Есть прямоугольник ABCD и точка P

if ((B.x -A.x)*(P.y-A.y)>(P.x - A.x)*(B.y-A.y)) &
((C.x -B.x)*(P.y-B.y)>(P.x - B.x)*(C.y-B.y)) &
((D.x -C.x)*(P.y-C.y)>(P.x - C.x)*(D.y-C.y)) &
((A.x -D.x)*(P.y-D.y)>(P.x - D.x)*(A.y-D.y)) then Внутри_или_наоборот_ли._Еще_не_выяснил.

Для треугольника ABC :

if ((B.x -A.x)*(P.y-A.y)>(P.x - A.x)*(B.y-A.y)) &
((C.x -B.x)*(P.y-B.y)>(P.x - B.x)*(C.y-B.y)) &
((A.x -C.x)*(P.y-C.y)>(P.x - C.x)*(A.y-C.y)) then

формулы пока не тестил.
Вывел их для работы над своими нелинейными тайлами.
Пробуйте.

← →
Megabyte-ceercop © (2004-10-08 11:49) [18]

Проверено. Формулы которые я тут выложил пунктом выше. Работают безошибочно. и возвращают True если точка внутри прямоугольника (или треугольника во втором случае).

← →
Fenik (2004-10-08 18:12) [19]

Если заранее не известен порядок следования вершин, можно воспользоваться тем же свойством скалярного произведения. Вот универсальная функция:

function PtInTriang(const P, A, B, C: TPoint): Boolean; function _PIT(const C1, C2, C3: TPoint): Boolean; begin Result := False; if (P.x-C1.x)*(C1.y-C2.y) - (P.y-C1.y)*(C1.x-C2.x) >= 0 then if (P.x-C2.x)*(C2.y-C3.y) - (P.y-C2.y)*(C2.x-C3.x) >= 0 then if (P.x-C3.x)*(C3.y-C1.y) - (P.y-C3.y)*(C3.x-C1.x) >= 0 then Result := True; 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;

> Megabyte-ceercop © (08.10.04 11:49) [18]

Ну уж, с прямоугольником можно и попроще :-)
Ты наверное имел в виду выпуклый четырехугольник?

← →
Megabyte-ceercop © (2004-10-11 06:19) [20]

> Ну уж, с прямоугольником можно и попроще :-)

Поделись эсли так. Мне очень нужно... Хотя куда уж проще то?

← →
wiz © (2004-10-11 07:30) [21]

2 Megabyte-ceercop [20]:

Если у тебя действительно прямоугольник (стороны попарно параллельны и попарно перпендикулярны), то можно одним афинным преобразованием перейти в систему координат, где стороны прямоугольника направлены вдоль координатных осей. Тогда всё сводится к покоординатным проверкам больше/меньше...

алгоритм будет выглядеть примерно так:
1. на этапе построения прямоугольника строим матрицу перехода в локальную систему координат (вообще говоря, её можно построить таким образом, что в лок. координатах прямоугольник будет иметь точки (0,0); (0,1); (1,1); (1,0);)

2. "проверка точки P". домножаем вектор P на матрицу перехода (для двумерного случая - 6 умножений и 4 сложения) и делаем проверку: if (p_x_new>0) and (p_x_new<1) and (p_y_new>0) and (p_y_new<1) then "внутри"

(Алгоритм можно обобщить и на случай параллелограмов, но _не_ произвольных выпуклых четырехугольников)

Если интересно, могу написать как этот алгоритм реализовать.

> wiz © (11.10.04 07:30) [21]

Мне нужны выпуклые, случайные многоугольники, и думаю нет формуулы проще и быстрее той, которая у меня уже есть.
Конечно для паралеллограммов можно упростить, но это не то.

> [21] wiz © (11.10.04 07:30)

Аффинным преобразованием такого же можно добиться и для произвольного параллелограмма. Если же жестко для прямоугольника - то это подгруппа движений.
Обобщать не надо - те же самые афинные преобразования. А как - ну тот же Александров(Аналитическая геометрия).

2 Думкин:

угу... что-то я с утреца пораньше был чуток глупый :)
с другой стороны, это всё равно не то, что нужно человеку :)))

Ой. Я понял почему все запутались.
Я под словом прямоугольник - подразумеваю просто четырехугольник. :)
Я не отношусь серьезно к разным там названиям. :)
Думал и так будет ясно что я имел в виду :-|

> [25] Megabyte-ceercop © (12.10.04 06:02)
> Я не отношусь серьезно к разным там названиям. :)

:)
У нас это лечили на первом курсе у подобных вам. Лечили просто - на матане в первой сессии малейшая оговорка по существу - банан. Народ проникся. %)
А в математике иначе трудно(да и не только в ней). Терминология - тоже важно. Как ни глупо, но ряд войн на этом форуме возникают только по причине различий в терминологии.

> У нас это лечили на первом курсе у подобных вам.

Потому то подобные нам и нелюбят учиться. :))

2 Думкин: (извините за оффтоп) позвольте поинтересоваться: вы случаем не ММФ НГУ имеете ввиду? :)))

2 Думкин: (извините за оффтоп) А я сбежал после второго курса... на ФФ

Треугольник АВС и точка P. Кто помнит геометрию? Найти похожие ветки