|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 29 Mar 2002 03:55:44
To : Alexey Skazik
Subject : Re: Определение границы...
--------------------------------------------------------------------------------
Alexey Skazik wrote:
>
> Есть множество точек на плоскости. Hужно найти такие точки, проведя ломанную
> ч/з которые, заключим всё остальное множество внутри.
> Идеи? Что-либо кроме простого перебора по парам точек, с выяснением есть
> ли что-либо с одной или другой стороны проведённой ч/з них прямой? :) Границы
> прямоугольной области, в которой гарантированно находится множество -известны.
В условии не требования выпуклости оболочки и нет никакого кртитерия
оптимальности. В такой ситуации можно поступить так:
Возмем центр масс данной системы точек и примем его за полюс полярной
системы координат. Соединим все точки множества в порядке возрастания их
угловой координаты. А если несколько точек имеют одинаковую координату -
то в порядке возрастания радиуса. Соединим также последнюю точку с
первой.
Все. (В этом случае все точки окажутся на границе :)
> :) Потом точки на границе нужно ещё и упорядочить, чтобы границу можно было
> обойти по/против часовой стрелки - без разницы.
Это требование выполнится автоматически.
Best regards,
Андрей.
P.S. Придумай какой-нибудь критерий оптимальности.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
