Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Алгоритм

kamerer © (2005-08-17 12:17:00)
Может кто втречал где или делал. Нужен алгоритм для построения замкнутой области(областей) на основе набора точек.
Если более подробно:
Есть куча точек. Нужно нарисовать кляксу(кляксы) в которые попадут все эти точки.

Этот алгоритм точно есть и даже как-то называется, но вот как не знаю. Буду рад любой информации или исходникам (хотя конечно предпочел бы билдеровский проект :))

Desdechado (2005-08-17 18:07:00) [1]
алгоритм NewClust и иже с ним
правда, он рассчитан на группировку точек и соединение их в сеть, номоджет быть легко модифицирован под нужный критерий

afanasic (2005-08-17 16:47:00) [2]

> Немного непонятно, ну ладно. А если результатом работы должно
> стать несколько областей? Центр-то один! Получится слишком
> большая область, когда можно обойтись несколькими маленькими.
>
> И форма этой области будет не совсем уж удобоваримой.

В условии нет однозначности... Из любого набора точек(N) можно построить минимум 1 кляксу, максимум (N div 3) кляксы, что конкретно ты хочешь получить - непонятно, причем легко построить одну - алгоритм описан и легко построить (N div 3) - брать по три точки, расположенные рядом и строить треугольники... Все остальные варианты - это воображение человека, а не алгоритм.
Ты можешь возразить, что можно взять из N точек K областей, где точки расположены особо кучно,- тогда предположим, что в области K1 находится L вариантов по M (max) областей, где точки тоже расположены особенно кучно относительно размеров области K1. Какой вариант брать? И далее по рекурсии... Таким образом мы придем к треугольникам, т.е. построим (N div 3) области...
Повторяю - недостаточно данных!

kamerer (2005-08-17 16:14:00) [3]
afanasic:
В алгоритме принцип волны - расходящаяся волна охватывает сначала ближайщие точки, потом удаленные и так далее, в процессе движения сначала образуется много маленьких ломаных, потом они смыкаются на общих точках, в итого последнее смыкание происходит на последней точке - решение найдено...

Немного непонятно, ну ладно. А если результатом работы должно стать несколько областей? Центр-то один! Получится слишком большая область, когда можно обойтись несколькими маленькими.

И форма этой области будет не совсем уж удобоваримой. Особенно если точки разбросаны далеко друг от друга. Тут надо что-то еще. Может и регионы.

afanasic (2005-08-17 15:26:00) [4]
В алгоритме принцип волны - расходящаяся волна охватывает сначала ближайщие точки, потом удаленные и так далее, в процессе движения сначала образуется много маленьких ломаных, потом они смыкаются на общих точках, в итого последнее смыкание происходит на последней точке - решение найдено...

Vlad Oshin (2005-08-17 14:51:00) [5]
нахождение средней для всех точек известно даже прапорщикам
пристреливали оружие? :)
берем папарно 2 точки, находим среднюю, она будет точой в следующей итерации

об окр.:
есть фла расстояния от т. до т., берем мах

а чем регионы не нравятся?

afanasic (2005-08-17 14:37:00) [6]
Алгоритм прост: находишь среднюю для всех точек, считаешь ее центром окружности, далее постепенно увеличивая радиус, охватываешь все больше и больше точек, запоминая последовательность их следования друг за другом, как только будет охвачена последняя точка, соединяешь полученный куски воедино - все. Алгоритм где-то есть, но с наскоку не найду... Если так не поймешь, напиши, я тебе по пунктам разложу...

kamerer (2005-08-17 14:28:00) [7]
А какую точку брать первой? Тут то и смысл весь в том, что бы рисовать начать с правильного места!

Vlad Oshin (2005-08-17 13:25:00) [8]

> Нужно нарисовать кляксу (кляксы)в которые попадут все эти
>

kamerer (2005-08-17 13:13:00) [9]
> MBo: Есть и алгоритмы для случаев, когда выпуклость не требуется, но тут построение неоднозначно, нужны доп. критерии.

Какие именно?

> Vlad Oshin: регион1=0
>1:
>берем следующие 3 точки, строим регион2
>пересекаем объединением R1 и R2
>goto 1

Не пойдет. А если получается несколько областей???

Vlad Oshin (2005-08-17 12:50:00) [10]

> Нужно нарисовать кляксу(кляксы) в которые попадут все эти
> точки.

регион1=0
1:
берем следующие 3 точки, строим регион2
пересекаем объединением R1 и R2
goto 1

Tonich (2005-08-17 12:41:00) [11]

> Vlad Oshin © (17.08.05 12:39) [8]
ну тохда
может конечно круг это частный случай кляксы, но тохда он уж очень частный ))))))

Vlad Oshin (2005-08-17 12:39:00) [12]

> Tonich © (17.08.05 12:28) [4]

> у кляксы же все ее граничные точки не обязательно равно
> отстоящие от центар

не обязательно равно отстоящие от центар <> обязательно неравностоящие
а посему,

> И кто мне скажет что круг - не клякса?

Tonich (2005-08-17 12:38:00) [13]

> Редкая клякса похвастает выпуклостью.
:)))))))))))))))))))))))))))))))))

Leonid Troyanovsky (2005-08-17 12:33:00) [14]

> MBo © (17.08.05 12:28) [3]
> Convex Hull это называется - построение выпуклой оболочки.

Редкая клякса похвастает выпуклостью.

--
Regards, LVT.

Tonich (2005-08-17 12:30:00) [15]
может конечно круг это частный случай кляксы, но тохда он уж очень честный ))))))

Tonich (2005-08-17 12:28:00) [16]

> И кто мне скажет что круг - не клякса?
ну у кляксы же все ее граничные точки не обязательно равно отстоящие от центар, а круга обязательно!!!

поэтому клякса это НЕ круг )))

MBo (2005-08-17 12:28:00) [17]
Convex Hull это называется - построение выпуклой оболочки.
Есть и алгоритмы для случаев, когда выпуклость не требуется, но тут построение неоднозначно, нужны доп. критерии.

jack128 (2005-08-17 12:25:00) [18]
А клякса прямоугольной формы подойдет?? -)
Result.TopLeft := Points[low(Points)] Result.RightBottom := Result.TopLeft; for i := low(Points) to high(Points) do begin if Result.Top > Points[i].Y then Result.Top := Points[i].Y else if Result.Bottom < Points[i].Y then Result.Bottom := Points[i].Y; if Result.Left > Points[i].X then Result.Left := Points[i].X else if Result.Right < Points[i].X then Result.Right := Points[i].X; end; InflateRect(Result, 1, 1);

Думкин (2005-08-17 12:20:00) [19]
самое тупое:
1. Ищем диаметр.
2. Строим на точках в которых диаметр реализуется - отрезок.
3. Из его середины строим круг.

И кто мне скажет что круг - не клякса?

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »