Равномерное расположение N точек в ограниченной области.

← →
4ECHOK © (2005-11-19 18:21) [0]

Необходимо разработать/найти алгоритм равномерного расположения определенного числа точек в произвольной замкнутой двухмерной области.
"Равномерного" - тут значит, что N точек оптимально расположены по всей площади фигуры.

Может кто направит на правильный путь ...

← →
XProger © (2005-11-19 18:39) [1]

Есть одномерная область. Размером S. Следовательно точки будут отдалены друг от друга на расстояние S/N. Ещё вопросы?

← →
4ECHOK © (2005-11-19 18:56) [2]

Что-то я не совсем понял связь между моим вопросом и твоим предложением. Как я сказал - область двумерная в декартовом пространстве R2, причем тут одномерная область ?
Равномерное расположение в двухмерном пространстве, в отличие от одномерного, не подразумевает удаленность точек на равные расстояния. А решение поставленной задачи требует разработки гораздо сложного алгоритма, нежели предложенного тобой.

Еще предложения ...

← →
XProger © (2005-11-19 18:59) [3]

Натяни сетку на свою фигуру. Площадь ячейки S/N. В узлах сетки получишь точки.
Ещё вопросы?

← →
4ECHOK © (2005-11-19 19:20) [4]

Берем самый простой вариант. Имеется окружность, в ней надо равномерно расположить 3 точки.
Допустим площадь круга составляет 9 м^2. Делим на 3, получаем 3 м^2 - площадь ячейки. Как по этой информации "натянуть сетку на фигуру" и "получить точки". ИМХО - бред.

← →
Separator © (2005-11-19 19:42) [5]

Ну заполняй от центра

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

← →
4ECHOK © (2005-11-19 19:48) [6]

Дык прикол в том, что число точек N может меняться. Поэтому "шаговый" алгоритм для произвольной области здесь неприменим. При том:
1. "Находишь центр" - можно без проблем найти для идеальных ситуаций типа окружность, квадрат.
2. "через определенный интервал" - его для начала надо найти =))

Т.е. НЕ стоит задача нанесения сетки, стоит задача "равномерной заливки" области некоторым количеством точек N.

← →
PAVIA © (2005-11-19 20:57) [7]

Берешь фигуру. Представляшь все его пиксели в виде линейного массива. Который равномерно и заполняешь.

← →
NE_Parovoz © (2005-11-19 21:20) [8]

4ECHOK
отталкиваеш каждую точку от остальных с силой пропорциональной расстоянию, и так же от стенок

не самый быстрый метод, но работать будет

← →
П7 (2005-11-20 05:18) [9]

> Берешь фигуру. Представляшь все его пиксели в виде линейного
> массива. Который равномерно и заполняешь.

Представим себе прямоугольную область X*Y. N - количество точек. Если N=X или N=Y, то применив алгоритм линейного расположения, получим, что все точки выстраиваются в ряд или колонку. Можно найти несколько таких примеров.

Поэтому, данный алгоритм тоже не совсем подходит.

> отталкиваеш каждую точку от остальных с силой пропорциональной
> расстоянию, и так же от стенок

А вот этот алгоритм, по-моему, может дать результаты.

← →
П7 (2005-11-20 18:20) [11]

> Представим себе прямоугольную область X*Y. N - количество
> точек. Если N=X или N=Y, то применив алгоритм линейного
> расположения, получим, что все точки выстраиваются в ряд
> или колонку. Можно найти несколько таких примеров.

Это уже частности, с которыми нужно и вполне можно бороться. Например случайным смещением. Или особым способом взятия линейного массива. Скажем: сначала берём по горизонтали, затем по вертикали, затем снова по горизонтали, и т.д. В общем тут экспериментировать нужно, но метод реально на порядок быстрее будет, чем с отталкиванием.

1. Можно вписать фигуру в более простую - например квадрат и равномерно заполнять его, и отбрасывть точки не попадающие в фигуру.
2. Можно апроксимировать фигуру многоугольником - и равномерно заполнять его.
3. Для квадратов, прямоугольников, окружностей и многоугольников - задачи разбирались в пятничных задачках МВо.

Равномерное расположение N точек в ограниченной области. Найти похожие ветки