Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.04.2016, 13:32   #1
max_prorok
Форумчанин
 
Регистрация: 06.10.2011
Сообщений: 181
По умолчанию C# Определение количества точек в определенном радиусе от точки

Ребят, есть ли у кого какие мысли по поводу того как можно решить следующую задачу. Есть координатная плоскость (допустим 200х200). На ней с рандомными координатами добавляются точки (скажем штук 100). Для точки я определил класс, содержащий переменные координат, переменная, определяющая радиус, в котором точка будет обнаруживать другие точки, ну и собственно List<> точек, в который записываются ссылки на все точки, которые находятся в радиусе "видимости" точки. Вопрос заключается в том, как заполнять список? Максимум до чего я додумался, это перебирать все точки, расчитывать расстояние между точками, и если оно меньше радиуса, то эта точка попадает в List. Но дело а том, что таких точек может быть много (скажем несколько тысяч, 2 и более точек могут иметь одинаковые координаты). Подскажите, есть ли у кого-нибудь какие-нибудь мысли по этому поводу. Хочется добиться максимальной эффективности при минимуме затрат.))
max_prorok вне форума Ответить с цитированием
Старый 07.04.2016, 13:50   #2
Alex11223
Старожил
 
Аватар для Alex11223
 
Регистрация: 12.01.2011
Сообщений: 19,500
По умолчанию

Несколько тысяч наверно не особо много если не 100500 раз в секунду пересчитывать надо.

А так можно погуглить куда-то в сторону k-d tree, quadtree и т.п.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом.
Alex11223 вне форума Ответить с цитированием
Старый 07.04.2016, 14:05   #3
max_prorok
Форумчанин
 
Регистрация: 06.10.2011
Сообщений: 181
По умолчанию

Да вот как раз надо бы 100500 раз в секунду. Следующий этап - это движение точек. Соответственно, при переходе на соседнюю координату, надо определять новые точки, которые вошли в зону "видимости".
max_prorok вне форума Ответить с цитированием
Старый 07.04.2016, 14:17   #4
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Ну как вариант Использовать некую карту.
Создаете матрицу M*N и при отрисовке точке в матрицу ставите индекс точки которая там расположена.
Матрица может состоять из листов, тогда можно будет записать несколько индексов точек в одной клетке.
Тогда при проверке радиуса можно проверять только ячейки матрицы. Выходит быстрее перебора но в ущерб оперативной памяти для матрицы.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.
WorldMaster вне форума Ответить с цитированием
Старый 07.04.2016, 14:48   #5
max_prorok
Форумчанин
 
Регистрация: 06.10.2011
Сообщений: 181
По умолчанию

У меня тоже была идея отказаться от перечисления точек, а создать в классе координатной плоскости список всех координат, и записывать в каждую координату, индекс точек, которые находятся по этим координатам. Но смысл в том, что точек может быть и 100 всего. Тогда цикл по всем координатам (в случае 200х200 получается 40000 элементов) займет больше времени, нежели по количеству точек.

Прошу прощения, что-то я тупанул. Понял вашу мысль. Можно будет попробовать.

Последний раз редактировалось max_prorok; 07.04.2016 в 14:54.
max_prorok вне форума Ответить с цитированием
Старый 07.04.2016, 14:53   #6
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

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

В принципе обойтись безе перебора всех точек вам врядли удастся. Остается лишь максимально задействовать современные технологии и алгоритмы оптимизации.
Можно использовать параллельные вычисления.
А вообще нужны конкретные цифры. 40000 для расчета это мизер. На современных устройствах это все рассчитается достаточно быстро.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.

Последний раз редактировалось WorldMaster; 07.04.2016 в 15:02.
WorldMaster вне форума Ответить с цитированием
Старый 07.04.2016, 15:17   #7
max_prorok
Форумчанин
 
Регистрация: 06.10.2011
Сообщений: 181
По умолчанию

40000 мизер, не спорю. Вот только если допустим на плоскости находится 1000 точек, и все они двигаются, то получается, что в секунду надо рассчитать 40000*1000*v, где v - скорость перемещения точки. Если даже взять 2,5 клетки в секунду, то получится около 40000*1000*2,5=100000000. А это уже не так уж мало. А если параллельно создается не одна такая поверхность, а несколько, то все это изрядно начнет тормозить.
max_prorok вне форума Ответить с цитированием
Старый 07.04.2016, 15:32   #8
WorldMaster
Старожил
 
Аватар для WorldMaster
 
Регистрация: 25.08.2011
Сообщений: 2,841
По умолчанию

Цитата:
Сообщение от max_prorok Посмотреть сообщение
40000 мизер, не спорю. Вот только если допустим на плоскости находится 1000 точек, и все они двигаются, то получается, что в секунду надо рассчитать 40000*1000*v, где v - скорость перемещения точки. Если даже взять 2,5 клетки в секунду, то получится около 40000*1000*2,5=100000000. А это уже не так уж мало. А если параллельно создается не одна такая поверхность, а несколько, то все это изрядно начнет тормозить.

Странно считаете как то.

При рендеринге каждой точки вычисляете регион в матрице где расположена точка и радиус вокруг нее.
Далее передаете в функцию саму матрицу и координаты региона, функция перебирает все точки региона.
Поле 1000 на 1000 - вроде как большое.
Радиус вокруг точки - 10, тогда регион вокруг точки будет всего 100 клеток. Это будет меньше.

А при параллельности зачем кучу матриц то создавать???
допустим у вас 12000 точек. и 4 ядерный проц. Создаете 4 потока и каждому даете по 4000 точек за которыми он следит.
И должно быть хорошо.


Каждую секунду считаете 1000 точек, для каждой радиус 10*10=100 клеток итого 100000.
Но.. скажите пожалуйста время выполнения для этой формулы? операции то не такие и сложные поэтому скорее всего скорострельность может быть достаточно высокой.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два.

Последний раз редактировалось WorldMaster; 07.04.2016 в 15:38.
WorldMaster вне форума Ответить с цитированием
Старый 07.04.2016, 20:42   #9
max_prorok
Форумчанин
 
Регистрация: 06.10.2011
Сообщений: 181
По умолчанию

Кстати, вопрос. Что лучше использовать: массив из List<> индексов точек или Lookup<>, где в качестве ключей использовать координаты (сделать структуру из двух координат) а в качестве значений использовать индексы точек? Или может быть Dictionary<> где в качестве значения использовать List<>?

Спустя n-ое время размышлений, пришел к выводу, что надо использовать ConcurrentDictionary<>, поскольку потом, когда точки смогут двигаться, их движение будет происходить в другом потоке, следовательно, и доступ нужен параллельный.

Последний раз редактировалось max_prorok; 07.04.2016 в 21:16.
max_prorok вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Из заданного мн-ва точек на плоскости выбрать 3 разные точки A,B,C так,чтобы внутри треугольника ABC было максимальное число точек Ronin94 Общие вопросы C/C++ 4 02.02.2015 18:31
Вычисление количества различных точек пересечения двух прямых x3Braid Помощь студентам 1 11.06.2012 17:18
Алгоритм подсчета количества точек пересечения отрезков juliaaaa Помощь студентам 2 24.02.2011 19:58
определение количества точек,попадающих в заданную область 13xxx Паскаль, Turbo Pascal, PascalABC.NET 0 20.12.2010 23:14
Метод оценки сверху количества точек!!! kostyan142 Помощь студентам 15 12.01.2010 20:26