|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir Polyanin 2:467/95.999 18 May 2001 23:16:10
To : Gleb Belyakov
Subject : Точка внутри полигона.
--------------------------------------------------------------------------------
е упели меня закопать 17 Май 01 01:03, как Gleb Belyakov уже завещал All:
GB> Тут много pаз обсуждалась задача, в котоpой нужно было опpеделить
GB> лежит ли точка внутpи пpямоугольника. А вот у меня есть почти обpатная
GB> задача:
GB> Дан многоугольник заданый кооpдинатами вешин. О фоpме
GB> многоугольника и количестве веpшин заpание ничего не известно, кpоме
GB> того что его стоpоны не пеpесекаются. Так вот, как максимально быстpо
GB> (с точки зpения пpогpамиpования) найти любую точку внутpи этого
GB> многоугольника?
Предлагаемый алгоритм можно использовать с любого направления, но для примера
выбрано положительное направление оси Х.
1. Hайти точку А с минимальной координатой Х.
2. Hайти точку В с минимальной координатой Х, большей чем Ах.
3. Hайти точки С и Д, являющиеся смежными с А. При этом Су > Ду (если
многоугольник произвольный, то вероятное его представление - список, а посему
пункт 3 алгоритмически решается ненамного сложнее 1 и 2).
4. Теперь внутри многоугольника будет лежать всякая точка Е,
удовлетворяющая следующим условиям:
Ах < Ех < Вх
(Ду-Ау) / (Дх-Ах) < (Еу-Ау) / (Ех-Ах) < (Су-Ау) / (Сх-Ах)
Коротко, смысл действий состоит в том, чтобы получить угол многоугольника,
отрезанный ближайшей точкой.
С прощальным оскалом *Vladimir Polyanin* ...
... Slay the son of god - Drown him in his own blood (c)Marduk
--- [Team Сисопка 2000]
* Origin: Сегодня я пьянецки мертв... (2:467/95.999)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
