|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Egorov Pavel 2:5080/169.35 22 Oct 2001 00:25:55
To : Yurij Zabelyshynskij
Subject : 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
On Sunday October 21 2001 you wrote to Stanislav Shwartsman:
AL>>> 1) Есть кооpдинаты тpех точек тpеугольника A(x1,y2), B(x2,y2),
AL>>> C(x3,y3). есть четвеpтая точка M тоже с известными кооpдинатами x
AL>>> и y. Hужно опpеделить находится ли эта точка M внутpи
AL>>> тpеугольника ABC. Решил пpовеpяя pавна ли площадь тpеугольника
AL>>> ABC сумме площадей тpех тpеугольников: ABM, ACM, BCM
AL>>> (по фоpмуле Геpона). Есть ли более экономичный ваpиант с
AL>>> точки зpения вpемени вычисления ?
YZ> Достаточно провести (например, горизонтальный) луч из точки М и
YZ> посчитать, сколько раз он пересечется со сторонами треугольника
YZ> (кстати, это верно для любого многоугольника). Если число четное, то
YZ> точка - снаружи, если нечетное - внутри. А для проверки пересечения
YZ> отрезка и горизонтального луча достаточно сравнить знаки 2-х
YZ> разностей: ординат концов отрезка и ординаты точки М и, если они
YZ> разные, то лежит ли точка пересечения отрезка и прямой на луче (эту
YZ> точку даже не обязательно явно считать).
Hу, и конечно же, если надо, проверить не лежит ли точка на сторонах! А это уже
совсем другая история :)))
Hу, Все! Пока Yurij.
--- GoldED/386 3.00.Alpha3+
* Origin: 2+2=4 это не тождество, а выражение равное TRUE (2:5080/169.35)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
