Алгоритм разброса точек по сетке

prudin

Есть файл с координатами точек... их порядка 10^8 как минимум
Надо их разбросать по такой сетке: (в узлах круги радиусом r )

Каков оптимальный алгоритм разброса точек по такой сетке?
Need any Idea... or C-code if somone has

prudin

up

prudin

никаких идей?

vital_m

Вопрос не понятен.

estochka

я не большой атэц проганья, но помоему задача не поставлена

prudin

есть N точек с координатами (x_i,y_i)
Есть области на плоскости в которые некоторые из них точно попадут... области - это круги радиуса r (для начала пусть радиусы будут одинаковыми) Центры(координаты) этих кругов известны... Надо разбросать эти точки на поверхность и посмотреть распределение таковых во всех заданных областях...
Интересно то что области могут быть и квадратиками... или другой фигурой...но need хотябы для кружочков на равномерной сетке...

disepa

Первая идея которая приходит в голову кроме перебора - использовать R-trees или что-то в этом духе.

prudin

А если поподробнее

ramses1971

Надо разбросать эти точки на поверхность и посмотреть распределение таковых во всех заданных областях...
Можно еще подробнее, для самых тупых ?

prudin

да

ALEKS67

Хех, а что значит "разбросать"?
Можно смоделировать какое-нибудь распределение в этих кружочках(или произвольных областях).
А вот что значит фраза "разбросать эти точки на поверхность и посмотреть распределение таковых" лично мне не понятно

ereyzer

а в чем проблема-то? нужна помощь сформулировать критерий "точка попала в круг/квадрат/что-то-там-еще"?

prudin

хотел узнать ести другой метод быстрее чем метод перебора всех точек на предмет попадания в i-й круг

prudin

разбросать эт значить расположить или рисовать и считать в каждом кружочке число попавших точек

disepa

>А если поподробнее
Что подробнее? Набери в google r-trees
и читай что это такое. Если в кратце, это дерево,
и чтобы найти в нем элемент надо просто пройтись от корня
вниз. Только конечные вершины не точки а какая-то фигура (прям под твою
задачу).
Если найду у себя в закромах инфу по этому делу, то дам.

prudin

буду благодарен

filippov2005

Пусть сетка с шагом R. Это значит, что узлы - это точки с координатами (nR, mR где n,m - целые.
Пусть узлов (кружочков радиуса r) на сетке - P Q штук. И они лежат в прямоугольнике (PR)x(QR).
Заводим двумерный массив счетчиков - по одному на каждый кружок.
Цикл по N разбрасываемым точкам.
Вычисляем координаты узлов, кружочки которых содержать точку (x_i, y_i):
Для этого надо решить неравнество в целых числах: |(mR - x_i)^2 + (nR - y_i)^2| <= r, где неизвестные - числа (m,n).
Для всех решений (m, n) увеличиваем соответсвующие счетчики на 1.
Осталось только решить неравенство. Его можно решить перебором, но естественно не по всем (m, n). А, например, перебирать только такие пары (m, n что |m - x_i/R| <= r/R, |n-y_i/R|<=r/R. Таких пар не более, чем (2[r/R] + 1)^2 - контсанта не зависящая от количества точек.
Количество операций - О(N).
Если делать полный перебор - то получится О(NPQ).
Для других областей (не окружностей) получатся другие неравенства. Но для их решения также потребуется количество операций независящее от количества узлов и точек, а только от размера решетки и размеров областей.

filippov2005

метод перебора всех точек на предмет попадания в i-й круг
Надо не точки перебирать, а наоборот - круги.
Так как про расположение кругов упорядочено (в отличие от точек) и мы можем сократить перебор.

UltraLoko

Надо не точки перебирать, а наоборот - круги.
Че тупим то? Конечно точки надо перебирать. Может для тебя конечно слово "перебирать" что-то другое значит Вобщем цикл по точкам, для каждой точки находим соответствующий ей круг (перебирать круги для этого не надо, просто взять целые части координат там и т.п.)
Так как про расположение кругов упорядочено (в отличие от точек) и мы можем сократить перебор.
Именно поэтому.

filippov2005

Че тупим то?
No, comments
Конечно точки надо перебирать. Может для тебя конечно слово "перебирать" что-то другое значит
Другое
Автор треда предлагал для каждого круга _перебирать точки_ на предмет попадания. Но как мы с тобой понимаем лучше для каждой точки _перебирать круги_ на предмет содержания.
перебирать круги для этого не надо, просто взять целые части координат там и т.п.
.
Вот тут согласен. Перебор я написал, как один из возможных методов решения за число операций не зависящее от количества кругов.
Это естественно гораздо хуже, чем явное решение через целые части.

UltraLoko

Ну вот и славненько

prudin

Сама задача нужна гласит :
Построить распределение (зависимость) n(R) (от центра координат до краёв сетки) для заданного блока данный(координат x и y) не для всей области. а для областей (у нас кружки) центры которых известны
кругов например m*m штук.
см рис

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

tongan

Наверно не все поняли
Функция n(R) - вычисляется от 0 (центр координат) до Rmax, причем разбивка идет на бины(шаги число которых тоже надо задать(напр. 10 бинов) .
У базовой фигуры(маленькие кружочки) известна площадь...
Так вот Нужно считать именно функцию пространственного распределения всех точек попавшие в кружочки от радиуса R...
вроде понятно излагаю

UltraLoko

Зачем вы вообще пользуетесь словом "распределение"? Я вот не могу понять, что оно в данном случае означает. "Количество" точек что ли надо считать? То есть берется i-ый бин (тоже, что за слово? кольцо имеется в виду { (x,y) = r | i \delta < |r| < (i+1)\delta } ?) и нужно сосчитать количество точек удовлетворяющих одновременно двум условиям
1) Принадлежит данному бину
2) Принадлежит отному из маленьких кружочков.
В итоге строится функция n(i).
Так?

kachokslava

bin (recycle bin) - корзина для того, чтобы туда складывали.
хранилище, вместилище

tongan

похожее сделано уже

a7137928

мозгоепство
Я ни хрена не понял из того, что ты написал. Что такое "распределение" в твоем понимании? Каким образом точки оказываются на плоскости? Они туда попадают случайно, как реализации двумерного случайного вектора (распределение которого известно? или его надо узнать? или нам даны координаты каждой точки? Что происходит с теми точками, которые не попадают в кружочки?
И главный вопрос: нахрен все это нужно?
Где-то читал фак по тому, как правильно задавать вопросы в форуме...
настоятельно рекомендую ознакомиться.

tongan

хех ... это часть большой задачи...
Оставить комментарий
Имя или ник:
Комментарий: