Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
TR411
3 / 3 / 0
Регистрация: 31.10.2013
Сообщений: 32
1

Посчитать площадь вокруг облака точек (с учётом области влияния точек)

26.02.2014, 10:55. Просмотров 1415. Ответов 17
Метки нет (Все метки)

Есть набор точек на плоскости.

Каждая точка имеет известную область влияния, допустим в радиусе 1000 м. Для простоты область влияния точки можно задавать квадратами, а не окружностями. Поскольку точек много - это не сильно важно.
Области влияния могут перекрываться.
Задача состоит в том, чтобы посчитать количество точек на единицу площади совокупной области влияния.

Для этого мне надо посчитать суммарную площадь влияния с учётом того, что области могут перекрываться.

Я написал для решения этой задачи алгоритм, который окружал каждую точку квадратом с заданными размерами. Под катом подробно описан алгоритм. Однако он видимо оказался не оптимальным, поскольку при достаточно большом количестве точек и их взаимопересечений время счёта возрастало так, что и за ночь программа не посчиталась.

Поэтому прошу посоветовать алгоритм быстрого решения подобной задачи.

Кликните здесь для просмотра всего текста
Я решил эту задачу следующим образом.
Совокупная площадь равна сумме неперекрытых площадей. Например если даны 3 точки, то площадь будет равна: S1+S2+S3+S12+S13+S23+S123.
S1 - та часть площади области влияния точки 1, которая не пересекается с областями влияния точек 2 и 3.
S12 - часть области влияния пересечения областей влияния точек 1 и 2, которая не пересекается с областью влияния точки 3.
S123 - область влияния, общая для всех трёх точек.
Была создана функция, возвращающая площадь пересечения любого набора элементов. Если на входе 1 элемент - то площадь его пересечения с самим собой.
Далее составлялась таблица двойных пересечений, в данном случае размерностью 3 на 3. Если элемент 1 пересекался с 3, то значение таблицы (1,3)=Истина, иначе Ложь.
Каждая S считалась по рекурсивной функции, назову её чистое пересечение ЧП. Например, область влияния точки 1, которая не пересекалась бы с областями точек 2 и 3 считалась по функции:
S1=ЧП(1)=(Полная площадь вокруг точки 1)-ЧП(1,2)-ЧП(1,3)-ЧП(2,3)-ЧП(1,2,3).
или
S12=ЧП(1,2)=(Полная область пересечения точек 1 и 2)-ЧП(1,2,3).
Примечание по поводу (Полная область влияния точки 1). Для одного элемента считалось его полное пересечение с самим собой
В данном случае использовалась таблица пересечений и в выражении участвовали только те элементы, которые пересекаются с точкой 1.


Задачу я решаю на VBA (Access), что также влияет скорость расчётов.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2014, 10:55
Ответы с готовыми решениями:

Прореживание облака точек
Здравствуйте Довольно много занимался подобными задачами, но вот нужна...

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

Центр "облака" точек
Есть массив точек с координатами Х, У. Необходимо найти координаты наиболее...

Перенос точек по БПФ в центр области
Добрый день. Не знаю, куда лучше написать, написал сюда, т.к. вопрос вроде про...

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

17
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 13:47 2
Я вижу такое решение:
Кликните здесь для просмотра всего текста
-Берем не помеченную точку, добавляем площадь её области в общую сумму.
-Для каждой другой не помеченной точки, которая имеет пересечение областей с данной (в случае с квадратной областью расчеты по поиску проще - проверка по разности координат точек), находим площадь пересечения областей, и вычитаем её из общей суммы.
-Помечаем данную точку
-Повторяем алгоритм пока есть не помеченные точки

Вместо меток можно просто сделать двойной цикл FOR
FOR i от 1 до N-1
FOR j от i+1 до N

Надеюсь решение правильное

Добавлено через 31 минуту
В случае с круглой областью можно упростить определение пересечения областей - сначала определяем пересечение квадратов, если уж квадратные области пересекаются - то тогда уже проверяем пересекаются ли круги (по расстоянию между точками).

Перед проверкой пересечения по расстоянию можно еще добавить проверку по координатам, но не простую - найти такую разницу координат, что круги гарантированно будут пересекаться - такой "худший" случай по проверке по координатам у нас появляется когда точки расположены по диагонали (относительно координатной сетки), а круги касаются друг друга. Расстояние тут известно - 2R, это у нас гипотенуза прямоугольного треугольника с углами по 45 градусов. Следовательно если модуль разности по обеим координатам меньше чем http://www.cyberforum.ru/cgi-bin/latex.cgi?2R\frac{\sqrt{2}}{2}=\sqrt{2}R,то круги обязательно пересекаются. К тому же не обязательно считать эту цифру каждый раз - можно вычислить один раз и запомнить в переменную.

Таким образом где-то в 50-70% случаев не требуется определять факт пересечения окружностей через расстояние между точками.
0
TR411
3 / 3 / 0
Регистрация: 31.10.2013
Сообщений: 32
26.02.2014, 14:02  [ТС] 3
wingblack, судя по моему пониманию вашего алгоритма, он работает только если пересекаются не более 2 областей.
Если рассмотреть например 3 точки с координатами A(1,1), B(2,1) и C(2,2) и радиусом влияния 1 (половина ребра квадрата), то есть область площадью 1, где пересекаются все три области влияния.
Получается так:
Код
Answer=0
point A: Answer=0+S(A)-S(AB)-S(AC)=4-2-1=1
point B: Answer=Answer+S(B)-S(BC)=1+4-2=3
point C: Answer=Answer+S(C)=3+4=7.
Правильный ответ - 8.
Сначала я пытался решить эту задачу окружив облако точек полигоном и найти его площадь. Используя понятие радиуса влияния, можно даже разбить точки на 2 кучки, если они очень далеко друг от друга. Но поскольку конфигурация облака точек может быть весьма сложной, я от этого отказался. Хотя я построил программу, окружающую облако точек полигоном. Но для сложных конфигураций точек полигон захватывал много лишнего места.
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 15:13 4
Знаете, а я согласен с ошибочность предложенного мною алгоритма (в плане подсчета площади).

Добавлено через 5 минут
Метод Монте-Карло наверное вам не подойдет.
0
raccoonlove
Заблокирован
26.02.2014, 15:18 5
Ну как, Монте-Карло, в принципе, мог бы и зайти, но оптимальное решение даст метод выметающей прямой (sweeping line). Пример такого алгоритма — Алгоритм Бентли — Оттмана. Если хотите подумать в этом направлении, могу подсказать.
0
TR411
3 / 3 / 0
Регистрация: 31.10.2013
Сообщений: 32
26.02.2014, 15:22  [ТС] 6
Нашел алгоритм, который сначала считает площадь области влияния точки, которая не пересекается с областями других точек ("чистая площадь"), прибавляет эту величину к ответу, а затем просто удаляет эту точку.
Этот алгоритм работает существенно быстрее. Хотя рекурсивное вычисление чистой площади всё равно делает его по прежнему неприемлемо медленным.
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 15:43 7
Лучший ответ Сообщение было отмечено TR411 как решение

Решение

Цитата Сообщение от TR411 Посмотреть сообщение
Нашел алгоритм, который сначала считает площадь области влияния точки, которая не пересекается с областями других точек ("чистая площадь"), прибавляет эту величину к ответу, а затем просто удаляет эту точку.
Этот алгоритм работает существенно быстрее. Хотя рекурсивное вычисление чистой площади всё равно делает его по прежнему неприемлемо медленным.
Ну можно хотя бы взять за идею выкидывать одиночные и точки только с одним пересечением

Добавлено через 14 минут
Вот нашел принцип включений-исключений
Чтобы посчитать размер объединения нескольких множеств, надо просуммировать размеры этих множеств по отдельности, затем вычесть размеры всех попарных пересечений этих множеств, прибавить обратно размеры пересечений всевозможных троек множеств, вычесть размеры пересечений четвёрок, и так далее, вплоть до пересечения всех множеств.
Правда тут встает проблема определение площади пересечения 3+ множеств

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

Добавлено через 2 минуты
Почему-то вспомнилось про алгоритм Брезинхейма для рисования окружности - можно ли его тут применить.
1
TR411
3 / 3 / 0
Регистрация: 31.10.2013
Сообщений: 32
26.02.2014, 16:09  [ТС] 8
wingblack, вот определение пересечения всех множеств - очень интересно. Я пытался вывести эту формулу, но как-то у меня получалась она сложнее. А вот это утверждение проверил, вроде верно. Сейчас проверю это в коде.

Пересечение 3+ областей как раз не проблема в случае квадратов. У меня функция для вычисления площади пересечения написана для любого N элементов.
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 16:39 9
Цитата Сообщение от TR411 Посмотреть сообщение
wingblack, вот определение пересечения всех множеств - очень интересно. Я пытался вывести эту формулу, но как-то у меня получалась она сложнее. А вот это утверждение проверил, вроде верно. Сейчас проверю это в коде.
Пересечение 3+ областей как раз не проблема в случае квадратов. У меня функция для вычисления площади пересечения написана для любого N элементов.
Да, задача в случае кругов довольно интересная получается, по крайней мере при поиске аналитического решения. Численно - да хоть по сетке, хоть Монте-Карло.
0
TR411
3 / 3 / 0
Регистрация: 31.10.2013
Сообщений: 32
26.02.2014, 16:51  [ТС] 10
wingblack, в общем, формула суммы N множеств идеально подошла. Скорость счёта по сравнению с моей лучшей формулой выше в 50 раз. Спасибо за подсказку!
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 17:27 11
Вот пришло в голову кое что для кругов, правда красиво нарисовать не получилось
Основная идея:
- для каждых двух пересекающихся окружностей провести хорды через точки пересечения.
- для каждой окружности с хордами определить точки пересечения хорд, разбить хорды на отрезки, оставить только те отрезки которые ближе к центру, провести линии от вершин отрезков к центру, все что за отрезками (относительно центра) "выкинуть"

таким образом площадь влияния точки "в толпе" равняется сумме площадей треугольников и секторов круга (не ограниченных хордами).

Для случая трех кругов все выглядит правильно, если пририсовать 4-й - вроде тоже.
Не претендую на то, что данный метод не имеет контр-примера.
0
Миниатюры
Посчитать площадь вокруг облака точек (с учётом области влияния точек)  
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
26.02.2014, 17:42 12
>> Задача состоит в том, чтобы посчитать количество точек на единицу площади совокупной области влияния.

Классический Монте-Карло, когда полное аналитическое решение, ну, во всяком случае, затруднительно. Берем N точек "в области влияния" и для каждой подсчитываем сколько исходных точек здесь повлияло. Сумму делим на N. Готово. Для подсчета "числа влияющих" широко используется OcTree, дающее хорошую скорость.

Не по теме:

Куда-то пропала опция "цитировать" ...

0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
26.02.2014, 17:42 13
Мое решение навеяно всплывшей в памяти диаграмой Вороного
0
Изображения
 
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
26.02.2014, 17:53 14
>> Мое решение навеяно всплывшей в памяти диаграмой Вороного

Это другая (более сложная) задача - интерполяция по облаку. Пример

*A ---- *B --------- *C

Для интерполяции в точке С не должна учитываться точка A (перекрытая B). А в постановке ТС может и учитываться (хватило бы радиуса)
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
27.02.2014, 13:14 15
Вот по быстренькому написал программку для визуальной проверки гипотезы по предложенному мною решению через хорды.
1) рисуем область максимального влияния точек
2) рисуем круги и хорды по пересечению двух кругов.
Более-менее наглядно выглядит для 6 точек, больше труднее разобрать
0
Миниатюры
Посчитать площадь вокруг облака точек (с учётом области влияния точек)  
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
27.02.2014, 15:48 16
Цитата Сообщение от Igor3D Посмотреть сообщение
Это другая (более сложная) задача - интерполяция по облаку. Пример
*A ---- *B --------- *C
Для интерполяции в точке С не должна учитываться точка A (перекрытая B). А в постановке ТС может и учитываться (хватило бы радиуса)
Смотря что понимать под облаком. Скорее всего вы что-то путаете.
Описание диаграммы Воронова как раз подходит для разделения перекрывающихся кругов влияния точек. В качестве признака разделения мы возьмем признак из диаграммы - к кому ближе, тот и главный. Таким образом к каждому "островку" применяем разбиение по диаграмме Воронова с дополнительным условием о радиусе.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
27.02.2014, 16:30 17
>> Описание диаграммы Воронова как раз подходит для разделения перекрывающихся кругов влияния точек. В качестве признака разделения мы возьмем признак из диаграммы - к кому ближе, тот и главный.

Только он был не Воронов, а Вороной А так да, причем обычно интересуются не одним, а 3 главными, чтобы интерполироваться по треугольнику. Но не вижу связи с данной задачей, как я понял, здесь просто спрашивается "сколько покрыто"
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
28.02.2014, 09:41 18
Цитата Сообщение от Igor3D Посмотреть сообщение
А так да, причем обычно интересуются не одним, а 3 главными, чтобы интерполироваться по треугольнику. Но не вижу связи с данной задачей, как я понял, здесь просто спрашивается "сколько покрыто"
При решении задачи встает проблема подсчета площади фигуры состоящей из множества окружностей, наложенных друг на друга.

Добавлено через 14 часов 49 минут
Интересно, насколько сильно отношение площадей при решениях через круги и квадраты будет отличаться от, собственно, отношения площадей круга и квадрата (в среднем).
0
28.02.2014, 09:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.02.2014, 09:41

Определить, попадает ли каждая из точек в указанную область, и найти площадь указанной области
пусть задана область на плоскости(вот так показанно на рисунке на координатной...

Фигура из облака точек
У меня есть чертеж AutoCAD (файл dwg), в котором представлено облако точек. Мне...

Отображение облака точек в 3D
Здравствуйте, есть облако точек , как мне отобразить это облако точек в 3д ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru