|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
07.04.2016, 13:32 | #1 |
Форумчанин
Регистрация: 06.10.2011
Сообщений: 181
|
C# Определение количества точек в определенном радиусе от точки
Ребят, есть ли у кого какие мысли по поводу того как можно решить следующую задачу. Есть координатная плоскость (допустим 200х200). На ней с рандомными координатами добавляются точки (скажем штук 100). Для точки я определил класс, содержащий переменные координат, переменная, определяющая радиус, в котором точка будет обнаруживать другие точки, ну и собственно List<> точек, в который записываются ссылки на все точки, которые находятся в радиусе "видимости" точки. Вопрос заключается в том, как заполнять список? Максимум до чего я додумался, это перебирать все точки, расчитывать расстояние между точками, и если оно меньше радиуса, то эта точка попадает в List. Но дело а том, что таких точек может быть много (скажем несколько тысяч, 2 и более точек могут иметь одинаковые координаты). Подскажите, есть ли у кого-нибудь какие-нибудь мысли по этому поводу. Хочется добиться максимальной эффективности при минимуме затрат.))
|
07.04.2016, 13:50 | #2 |
Старожил
Регистрация: 12.01.2011
Сообщений: 19,500
|
Несколько тысяч наверно не особо много если не 100500 раз в секунду пересчитывать надо.
А так можно погуглить куда-то в сторону k-d tree, quadtree и т.п.
Ушел с форума, https://www.programmersforum.rocks, alex.pantec@gmail.com, https://github.com/AlexP11223
ЛС отключены Аларом. |
07.04.2016, 14:05 | #3 |
Форумчанин
Регистрация: 06.10.2011
Сообщений: 181
|
Да вот как раз надо бы 100500 раз в секунду. Следующий этап - это движение точек. Соответственно, при переходе на соседнюю координату, надо определять новые точки, которые вошли в зону "видимости".
|
07.04.2016, 14:17 | #4 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Ну как вариант Использовать некую карту.
Создаете матрицу M*N и при отрисовке точке в матрицу ставите индекс точки которая там расположена. Матрица может состоять из листов, тогда можно будет записать несколько индексов точек в одной клетке. Тогда при проверке радиуса можно проверять только ячейки матрицы. Выходит быстрее перебора но в ущерб оперативной памяти для матрицы.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. |
07.04.2016, 14:48 | #5 |
Форумчанин
Регистрация: 06.10.2011
Сообщений: 181
|
У меня тоже была идея отказаться от перечисления точек, а создать в классе координатной плоскости список всех координат, и записывать в каждую координату, индекс точек, которые находятся по этим координатам. Но смысл в том, что точек может быть и 100 всего. Тогда цикл по всем координатам (в случае 200х200 получается 40000 элементов) займет больше времени, нежели по количеству точек.
Прошу прощения, что-то я тупанул. Понял вашу мысль. Можно будет попробовать. Последний раз редактировалось max_prorok; 07.04.2016 в 14:54. |
07.04.2016, 14:53 | #6 |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
В матрице можно использовать метод разрастания областей когда из требуемой точки вы будете исследовать близлежащие точки пока они расположены в нужном радиусе. Тогда вам не придется исследовать все поле.
В принципе обойтись безе перебора всех точек вам врядли удастся. Остается лишь максимально задействовать современные технологии и алгоритмы оптимизации. Можно использовать параллельные вычисления. А вообще нужны конкретные цифры. 40000 для расчета это мизер. На современных устройствах это все рассчитается достаточно быстро.
Skype - wmaster_s E-Mail - WorldMasters@gmail.com
Работаем по 3 критериям - быстро, качественно, недорого. Заказчик выбирает любые два. Последний раз редактировалось WorldMaster; 07.04.2016 в 15:02. |
07.04.2016, 15:17 | #7 |
Форумчанин
Регистрация: 06.10.2011
Сообщений: 181
|
40000 мизер, не спорю. Вот только если допустим на плоскости находится 1000 точек, и все они двигаются, то получается, что в секунду надо рассчитать 40000*1000*v, где v - скорость перемещения точки. Если даже взять 2,5 клетки в секунду, то получится около 40000*1000*2,5=100000000. А это уже не так уж мало. А если параллельно создается не одна такая поверхность, а несколько, то все это изрядно начнет тормозить.
|
07.04.2016, 15:32 | #8 | |
Старожил
Регистрация: 25.08.2011
Сообщений: 2,841
|
Цитата:
Странно считаете как то. При рендеринге каждой точки вычисляете регион в матрице где расположена точка и радиус вокруг нее. Далее передаете в функцию саму матрицу и координаты региона, функция перебирает все точки региона. Поле 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. |
|
07.04.2016, 20:42 | #9 |
Форумчанин
Регистрация: 06.10.2011
Сообщений: 181
|
Кстати, вопрос. Что лучше использовать: массив из List<> индексов точек или Lookup<>, где в качестве ключей использовать координаты (сделать структуру из двух координат) а в качестве значений использовать индексы точек? Или может быть Dictionary<> где в качестве значения использовать List<>?
Спустя n-ое время размышлений, пришел к выводу, что надо использовать ConcurrentDictionary<>, поскольку потом, когда точки смогут двигаться, их движение будет происходить в другом потоке, следовательно, и доступ нужен параллельный. Последний раз редактировалось max_prorok; 07.04.2016 в 21:16. |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Из заданного мн-ва точек на плоскости выбрать 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 |