2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вычисление оптимальной точки пересечения окружностей
Сообщение05.11.2014, 13:34 
Собственно есть задача по вычислению оптимальной точки, которая находится в области пересечения большинства окружностей, т.е. попадает внутрь большинства окружностей.

Исходные данные:
- Список точек центра окружностей
- Дистанция = радиус от центра окружности.


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

Может ли кто-нибудь с этим помочь ? :) Большое спасибо!

 
 
 
 Re: Вычисление оптимальной точки пересечения окружностей
Сообщение05.11.2014, 14:44 
Аватара пользователя
Окружностей Кругов.
По сути, пахнет перебором размера $2^n$; кое-что лишнее можно отсечь, но если большинство кругов действительно пересекаются все вместе, то - - -

-- менее минуты назад --

А хотя нет, можно проще.
1. Для каждого круга находим список тех, которые с ним пересекаются. (Тут придётся посчитать все попарные расстояния - квадратичный труд.)
2. Берём один круг (любой; лучше начинать с тех, у которых пересекающих больше) и выписываем углы пересечений. Типа "перерезан кругом номер 21 между 65 и 135 градусами, кругом 54 с... по...".

-- менее минуты назад --

3. Сортируем этот список углов, проходим по нему и находим, где пересечений больше всего.
4. То же самое для остальных кругов.
5. ...
6. PROFIT!

 
 
 
 Re: Вычисление оптимальной точки пересечения окружностей
Сообщение05.11.2014, 15:09 
а можно ли это как-то обличить в формулу ? :)

 
 
 
 Re: Вычисление оптимальной точки пересечения окружностей
Сообщение05.11.2014, 15:19 
Аватара пользователя
Если возник такой вопрос, то Вы уже зашли не туда.
В каком-то смысле можно, но этого не надо делать.

-- менее минуты назад --

Ну, будет там что-то типа $\max\limits_{i=1..n}\;\; \max\limits_{0\leqslant\varphi<2\pi}\;\sum\limits_j{1\over 2}\Big(sgn(\varphi-\varphi_1)+sgn(\varphi_2-\varphi)\Big)$ - а толку-то?
(На место $\varphi_1$ и $\varphi_2$ надо подставить границы диапазона углов круга $i$, отрезанного кругом $j$. Тоже несложно, но арксинусы, грязь, мухи, вот это всё.)

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group