| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Треугольник АВС и точка P. Кто помнит геометрию? [Delphi]
Aleksey_a © (2004-09-28 03:32:00)Простая вроде задача но никак не могу вспомнить. Дано три точки на плоскости A(Aх,Aх), B(Bx,By) и C(Cx,Cy) (треугольник). Нужно решить задачу попадания или непопадания точки P(Px,Py) в этот треугольник.
wiz (2004-10-12 11:06:00) [1]2 Думкин: (извините за оффтоп) А я сбежал после второго курса... на ФФ
Думкин (2004-10-12 09:19:00) [2]> [28] wiz © (12.10.04 09:09)
его родимый.
wiz (2004-10-12 09:09:00) [3]2 Думкин: (извините за оффтоп) позвольте поинтересоваться: вы случаем не ММФ НГУ имеете ввиду? :)))
Megabyte-ceercop (2004-10-12 08:16:00) [4]
> У нас это лечили на первом курсе у подобных вам.
Потому то подобные нам и нелюбят учиться. :))
Думкин (2004-10-12 06:39:00) [5]> [25] Megabyte-ceercop © (12.10.04 06:02)
> Я не отношусь серьезно к разным там названиям. :)
:)
У нас это лечили на первом курсе у подобных вам. Лечили просто - на матане в первой сессии малейшая оговорка по существу - банан. Народ проникся. %)
А в математике иначе трудно(да и не только в ней). Терминология - тоже важно. Как ни глупо, но ряд войн на этом форуме возникают только по причине различий в терминологии.
Megabyte-ceercop (2004-10-12 06:02:00) [6]Ой. Я понял почему все запутались.
Я под словом прямоугольник - подразумеваю просто четырехугольник. :)
Я не отношусь серьезно к разным там названиям. :)
Думал и так будет ясно что я имел в виду :-|
wiz (2004-10-11 22:56:00) [7]2 Думкин:
угу... что-то я с утреца пораньше был чуток глупый :)
с другой стороны, это всё равно не то, что нужно человеку :)))
Думкин (2004-10-11 08:02:00) [8]> [21] wiz © (11.10.04 07:30)
Аффинным преобразованием такого же можно добиться и для произвольного параллелограмма. Если же жестко для прямоугольника - то это подгруппа движений.
Обобщать не надо - те же самые афинные преобразования. А как - ну тот же Александров(Аналитическая геометрия).
Megabyte-ceercop (2004-10-11 07:53:00) [9]
> wiz © (11.10.04 07:30) [21]
Мне нужны выпуклые, случайные многоугольники, и думаю нет формуулы проще и быстрее той, которая у меня уже есть.
Конечно для паралеллограммов можно упростить, но это не то.
wiz (2004-10-11 07:30:00) [10]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 "внутри"
(Алгоритм можно обобщить и на случай параллелограмов, но _не_ произвольных выпуклых четырехугольников)
Если интересно, могу написать как этот алгоритм реализовать.
Megabyte-ceercop (2004-10-11 06:19:00) [11]
> Ну уж, с прямоугольником можно и попроще :-)
Поделись эсли так. Мне очень нужно... Хотя куда уж проще то?
Fenik (2004-10-08 18:12:00) [12]Если заранее не известен порядок следования вершин, можно воспользоваться тем же свойством скалярного произведения. Вот универсальная функция:
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-08 11:49:00) [13]Проверено. Формулы которые я тут выложил пунктом выше. Работают безошибочно. и возвращают True если точка внутри прямоугольника (или треугольника во втором случае).
Megabyte-ceercop (2004-10-08 07:04:00) [14]Самые быстрые формулы в виде условий без вызора доп функций.
Есть прямоугольник 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
формулы пока не тестил.
Вывел их для работы над своими нелинейными тайлами.
Пробуйте.
XProger (2004-10-08 01:42:00) [15]
//Положение точки 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 := 'Неа!'; //Не попал =)
Fenik (2004-10-08 00:03:00) [16]http://delphibase.endimus.ru/?action=viewfunc&topic=mathcalc&id=10560
oldman (2004-10-04 18:20:00) [17]поправочка - если тоска пересечения совпадает с искомой - точка лежит на стороне
oldman (2004-10-04 18:19:00) [18]:)))
находишь точку пересечения высот (медиан, биссектрис)
строишь отрезок из этой точки в искомую
ищешь точки пересечения со сторонами треугольника
если точки есть - искомая точка вне треугольника
если нет - внутри
:)))
alexshx (2004-10-04 18:14:00) [19]Darth, я с тобой не согласен. Если точка лежит на одной из сторон треугольника, то одна из площадей треугольников PAC, PAB, PBC будет равна 0, а сумма площадей двух остальных и будет равна площади треугольника ABC. В случае, если заданная точка P - одна из вершин, то две из площадей PAC, PAB, PBC будут равны 0, а площадь оставшегося треугольника будет равна площади треугольника ABC.
EViruS (2004-10-01 05:51:00) [20]Есть много вариантов. Вот простейшие:
1) школьная геометрия
2) составить ур-я прммых и поглядеть как расположена точка относительно их
3) пройтись по всем вершинам (против ЧС) и проверить как располоден отрезок из вершины до точки и до след вершины, если он всегда правый, то следовательно точка в треугольнике
В общем, algolist.manual.ru
Стоит почитать про выпуклые оболочки или расположение точек относительно прямой.
| |
Страницы: 