|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Artyom Petrov 2:5024/7.352 21 Oct 2001 21:39:36
To : Stanislav Shwartsman
Subject : Re: 2 Задачи по геометpии и соpтиpовка
--------------------------------------------------------------------------------
SS> Hello Arsen!
SS> 20 Oct 01 20:16, you wrote to All:
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и тpеугольника ABC.
AL>> Pешил пpовеpяя pавна ли площадь тpеугольника ABC сумме площадей
AL>> тpех тpеугольников: ABM, ACM, BCM (по фоpмуле Геpона).
AL>> Есть ли более экономичный ваpиант с точки зpения вpемени вычисления ?
SS> Как вариант могу предложить - если точка O внутри треугольника ABC, то
SS> сумма углов AOB, BOC, AOC равна 360 градусов. Иначе - всегда меньше.
Оба эти метода не надёжны из-за неточности вычислений. Если точка и находится
внутри
многоугольника вероятность получения верного результата очень мала.
У выпуклого n-угольника все вершины лежат по одну сторону относительно любой
грани.
Любая точка внутри должна лежать по ту же сторону что и остальные вершины, если
хотя бы для одной
грани это не выполняется, то точка лежит вне n-угольника.
Вот нарыл в своих архивах вариант решения на QBasic-е
CLS
INPUT "Число сторон выпуклого n-угольника"; n
DIM x(n + 1), y(n + 1), q(3, 2)
FOR i = 1 TO n
INPUT "x,y вершины:"; x(i), y(i)
NEXT i
INPUT "x,y точки:"; x(n + 1), y(n + 1)
u = n + 1
a = 1
FOR i = 1 TO n
IF i = n - 1 THEN a = 1 - n
u1 = i + a + 1
q(1, 1) = x(i + a) - x(i)
q(1, 2) = y(i + a) - y(i)
q(2, 1) = x(u) - x(i)
q(2, 2) = y(u) - y(i)
q(3, 1) = x(u1) - x(i)
q(3, 2) = y(u1) - y(i)
d1 = q(1, 1) * q(2, 2) - q(1, 2) * q(2, 1)
d2 = q(1, 1) * q(3, 2) - q(1, 2) * q(3, 1)
PRINT STR$(i) + " " + STR$(u1)
IF d1 = 0 THEN PRINT "Hа грани": END
IF SGN(d1) <> SGN(d2) THEN PRINT "Вне": END
NEXT i
PRINT "Внутри"
END
Hе пропадай Stanislav
e-mail: petrov_artyom@mail.ru
e-mail: Artyom.Petrov@p352.f7.n5024.z2.fidonet.org (в ФИДО)
Artyom (2:5024/7.352)--- Automatically added by Taimyr
--- ifmail v.2.15dev5
* Origin: Automatically added (2:5024/7.352)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
