Алгоритм

← →
kamerer (2005-08-17 12:17) [0]

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

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

← →
Думкин © (2005-08-17 12:20) [1]

самое тупое:
1. Ищем диаметр.
2. Строим на точках в которых диаметр реализуется - отрезок.
3. Из его середины строим круг.

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

← →
jack128 © (2005-08-17 12:25) [2]

А клякса прямоугольной формы подойдет?? -)
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);

← →
MBo © (2005-08-17 12:28) [3]

Convex Hull это называется - построение выпуклой оболочки.
Есть и алгоритмы для случаев, когда выпуклость не требуется, но тут построение неоднозначно, нужны доп. критерии.

← →
Tonich © (2005-08-17 12:28) [4]

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

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

← →
Tonich © (2005-08-17 12:30) [5]

может конечно круг это частный случай кляксы, но тохда он уж очень честный ))))))

← →
Leonid Troyanovsky © (2005-08-17 12:33) [6]

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

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

--
Regards, LVT.

← →
Tonich © (2005-08-17 12:38) [7]

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

← →
Vlad Oshin © (2005-08-17 12:39) [8]

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

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

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

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

← →
Tonich © (2005-08-17 12:41) [9]

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

← →
Vlad Oshin © (2005-08-17 12:50) [10]

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

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

← →
kamerer (2005-08-17 13:13) [11]

> MBo: Есть и алгоритмы для случаев, когда выпуклость не требуется, но тут построение неоднозначно, нужны доп. критерии.

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

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

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

← →
Vlad Oshin © (2005-08-17 13:25) [12]

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

← →
kamerer (2005-08-17 14:28) [13]

А какую точку брать первой? Тут то и смысл весь в том, что бы рисовать начать с правильного места!

← →
afanasic (2005-08-17 14:37) [14]

Алгоритм прост: находишь среднюю для всех точек, считаешь ее центром окружности, далее постепенно увеличивая радиус, охватываешь все больше и больше точек, запоминая последовательность их следования друг за другом, как только будет охвачена последняя точка, соединяешь полученный куски воедино - все. Алгоритм где-то есть, но с наскоку не найду... Если так не поймешь, напиши, я тебе по пунктам разложу...

нахождение средней для всех точек известно даже прапорщикам
пристреливали оружие? :)
берем папарно 2 точки, находим среднюю, она будет точой в следующей итерации

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

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

← →
afanasic (2005-08-17 15:26) [16]

В алгоритме принцип волны - расходящаяся волна охватывает сначала ближайщие точки, потом удаленные и так далее, в процессе движения сначала образуется много маленьких ломаных, потом они смыкаются на общих точках, в итого последнее смыкание происходит на последней точке - решение найдено...

← →
kamerer (2005-08-17 16:14) [17]

afanasic:
В алгоритме принцип волны - расходящаяся волна охватывает сначала ближайщие точки, потом удаленные и так далее, в процессе движения сначала образуется много маленьких ломаных, потом они смыкаются на общих точках, в итого последнее смыкание происходит на последней точке - решение найдено...

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

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

← →
afanasic (2005-08-17 16:47) [18]

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

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

алгоритм NewClust и иже с ним
правда, он рассчитан на группировку точек и соединение их в сеть, номоджет быть легко модифицирован под нужный критерий

Алгоритм Найти похожие ветки