Интересная задача

[Ivan XXX]

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

[peace_man]

А смысл?... ты хочешь чтобю тебе код написли, чтоли?... у нас такие задачи в школе были...

[X0R]

peace_man, заипали если честно трындеть что у в школе было, а что не было. А код черкнуть всем слабо Школьники ёпить!

[SuHar`]

peace_man, НЕ ВЕРЮ.
НЕ путайте КРУГ и ОКРУЖНОСТЬ.
И код не мне не нужен. Мне нужна идея, необходимое и достаточное ословие того, что n кругов имеют общую точку. Задача далеко не школьная. Кроме того, ее не каждый студент и даже выпускник ВУЗа, как оказалось, в состоянии решить.

[КаЗаХсТаН]

Ну тогда - геморой...
Т.к. полученная фигура - выпуклая, то лишних проблем - не будет
1. Находим первые 2-е точки пересечения 1-ых 2-ух кругов(в смысле окружности эти кругов). Получим фигуру F1
2. Смотрим 3-ий круг по удаленности его центра до этих точек. Вот здесь нужно брать карандаш и рисовать всевозможные случаи (я их насчитал 4) пересечения 3-его круга с фигурой F1. В зависимости от типа пересечения - находим точки. Точка может быть одна, 2-е или 3, а может и весь круг(в данном случае возвращаемся к п.1). Получим фигуру F2
3. Смотрим круг 4-ый...

PS: надо будет для каждой точки вновь полученной фигуры хранить № круга для того, чтобы была возможность проверить - пересекаются ли дуги.

Излагаюсь я не совсем точно, но может кто-то и поймет...
Мог бы написать, но:
1. Нет времени (тут работы часа на 3)
2. На PHP мало кто поймет...

[Ivan XXX]

предлагаю их просто тупо на экране отрисовывать )
фон - белый
цвета у всех кругов разные. при попадании круга / его части на фон цвет не меняется. если на уже другой цвет, то складывать исходный и текущий... сумбурно, но, наверн, понятно о чем речь )

[shuri]

Сообщение от Milky Man

Это ты кого имел ввиду?

Не вас, это точно :-) Не люблю перебор, обычно это показатель, что задача решена неоптимально :-)

[shuri]

Сообщение от SuHar`

peace_man, НЕ ВЕРЮ.
НЕ путайте КРУГ и ОКРУЖНОСТЬ.

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


Всякое сечение шара плоскостью есть круг. Центр этого круга есть основание перпендикуляра, опущенного из центра шара на секущую плоскость.

[Part!zan]

SuHar`, имхо, это численные методы. Какой-нть метод простых итераций.

[Milky Man]

SuHar`, такс, попытаюсь необходимое условие сформулировать. Если круги имеют общие точки, то их окружности пересекаются. Если существует точка, которая принадлежит всем кругам одновременно, то это обязательно будет точка пересечения хотя бы двух кругов (концентрические круги частный случай, проверяется отдельно - если нет ни одной точки пересечения и достаточное условие выполнено - смотри про расстояния между центрами и радиусы). Надеюсь это не надо доказывать, что множество точек, принадлежащих всем кругам будет иметь хотя бы две точки пересечения окружностей, если только окружности не концентрические - несложно проверяется. Задача сводится к следующему - найти все точки пересечения окружностей, а затем проверить каждую из этих точек на принадлежность к каждому из кругов (расстояние от центра до точки пересечения окружностей). Вроде, просто делается.

[SuHar`]

Сообщение от Milky Man

SuHar`, такс, попытаюсь необходимое условие сформулировать. Если круги имеют общие точки, то их окружности пересекаются. Если существует точка, которая принадлежит всем кругам одновременно, то это обязательно будет точка пересечения хотя бы двух кругов (концентрические круги частный случай, проверяется отдельно - если нет ни одной точки пересечения и достаточное условие выполнено - смотри про расстояния между центрами и радиусы). Надеюсь это не надо доказывать, что множество точек, принадлежащих всем кругам будет иметь хотя бы две точки пересечения окружностей, если только окружности не концентрические - несложно проверяется. Задача сводится к следующему - найти все точки пересечения окружностей, а затем проверить каждую из этих точек на принадлежность к каждому из кругов (расстояние от центра до точки пересечения окружностей). Вроде, просто делается.

Точно! Достаточно найти всего одну пару пересекающихся или касающихся окружностей(тогда хотя бы одна из их общий точек должна удовлетворять неравенствам всех кругов, чтобы все круги имели хотя бы одну общую точку). А если таковых нету, то достаточно проверить условие с радиусами и расстояниями между центрами! Всё!
Спасибо.
Блин, и как же я сам не догадался?

[Milky Man]

Сообщение от SuHar`

Точно! Достаточно найти всего одну пару пересекающихся или касающихся окружностей(тогда хотя бы одна из их общий точек должна удовлетворять неравенствам всех кругов, чтобы все круги имели хотя бы одну общую точку). А если таковых нету, то достаточно проверить условие с радиусами и расстояниями между центрами! Всё!
Спасибо.
Блин, и как же я сам не догадался?

Да, только две точки можно проверить. Про все я погорячился.

[SuHar`]

Milky Man, облом((( рано радоваться. Нарисовали мне тут случай, когда не сработает этот способ.... Сейчас времени нет - завтра выложу картинку.

[КаЗаХсТаН]

Сообщение от Milky Man

SuHar`, такс, попытаюсь необходимое условие сформулировать. Если круги имеют общие точки, то их окружности пересекаются. Если существует точка, которая принадлежит всем кругам одновременно, то это обязательно будет точка пересечения хотя бы двух кругов (концентрические круги частный случай, проверяется отдельно - если нет ни одной точки пересечения и достаточное условие выполнено - смотри про расстояния между центрами и радиусы). Надеюсь это не надо доказывать, что множество точек, принадлежащих всем кругам будет иметь хотя бы две точки пересечения окружностей, если только окружности не концентрические - несложно проверяется. Задача сводится к следующему - найти все точки пересечения окружностей, а затем проверить каждую из этих точек на принадлежность к каждому из кругов (расстояние от центра до точки пересечения окружностей). Вроде, просто делается.

А не ФАКТ!!! А если круг ПОЛНОСТЬЮ находиться в фигуре пересечения остальных кругов??!

[Snusmumrik]

Сообщение от Milky Man

концентрические круги частный случай, проверяется отдельно - если нет ни одной точки пересечения и достаточное условие выполнено - смотри про расстояния между центрами и радиусы

Сообщение от КаЗаХсТаН

А не ФАКТ!!! А если круг ПОЛНОСТЬЮ находиться в фигуре пересечения остальных кругов??!

поздравляю, шарик...

[Milky Man]

Сообщение от КаЗаХсТаН

А не ФАКТ!!! А если круг ПОЛНОСТЬЮ находиться в фигуре пересечения остальных кругов??!

В случае наличия концентрических окружностей, необходимое условие - проверка центра окружности на принадлежность остальным кругам. Потому как если центр принадлежит всем кругам, то и все точки будут им принадлежать при отсутствии точек пересечения окружности этого круга с другими окружностями кругов. Тоже легко делается.

[SuHar`]

С концентрическими кругами тоже трудности могут быть.
Как, например, обработать этот случай?:

[SuHar`]

А хотя....
В общем ладно. Вечером попробую реализовать в программном коде.

[SuHar`]

Так. Вроде додумался....
Сначала попарно рассматриваем все круги. Если нашлась пара пересекающихся окружностей, то подставляем точки их пересечения во все неравенства. Если хотя одна точка принадлежит всем неравенствам, значит задача решена. Если точки не принадлежат ни одному из неравенств или вообще не нашлось пары пересекающихся окружностей, то значит, что или общих точек у кругов нет, или существует по крайнем мере один круг, полностью находящийся внутри другого. Ищем вложенный круг. Если не найдется вложенных кругов, то общих точек у всех кругов нет. Если найдется вложенный круг, то тогда: ищем самый маленький вложенный круг, подставляем координаты его центра во все неравенства кругов. Если принадлежит - задача решена, если нет, то сравниваем его попарно со всеми другими кругами. Если найдется круг, который с ним пересекается, подставляем точки пересечения в неравенства. Если хоть одна удовл. всем неравенствам, то задача решена. Если нет, или не нашлось круга, который с ним пересекается, значит круги не имеют общих точек.
Фубля... вроде все))).

[SuHar`]

Если чуток оптимизировать, то алгоритм такой:

1. проходимся по всем кругам. удаляем те в которые вписаны другие круги.
2. если круг остался один - есть решение. выходим из проги.
3. находим все точки пересичения ОСТАВШИХСЯ окружностей. запоминаем их координаты и ТО К КАКИМ КРУГАМ ОНИ ОТНОСЯТСЯ.
4. Прогоняем точки по очеререди через неравенства кругов (не подставляем в те неравенства, пересечением окружностей которых они получены). Если удовлетворяет всем неравенствам - выходим. Есть решение!

[mexx]

напряжная задача, не люблю геометрию))
со строками интересней всегда

[Milky Man]

Сообщение от SuHar`

Если чуток оптимизировать, то алгоритм такой:
1. проходимся по всем кругам. удаляем те в которые вписаны другие круги.
2. если круг остался один - есть решение. выходим из проги.
3. находим все точки пересичения ОСТАВШИХСЯ окружностей. запоминаем их координаты и ТО К КАКИМ КРУГАМ ОНИ ОТНОСЯТСЯ.
4. Прогоняем точки по очеререди через неравенства кругов (не подставляем в те неравенства, пересечением окружностей которых они получены). Если удовлетворяет всем неравенствам - выходим. Есть решение!

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

[Milky Man]

Сообщение от mexx

напряжная задача, не люблю геометрию))
со строками интересней всегда

А ещё интересней в игры играть, наверное...

[mexx]

А ещё интересней в игры играть, наверное..

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

[SuHar`]

Сообщение от Milky Man

Да, пересЕчение пишется через "е"...

это очепятка)))

[Оля-ля]

Добрый вечер, предлагаю такой вариант решения: все окружности имеют "крайние" координаты по x и по y. Условно говоря, для каждой окружности Cn максимальная координата по оси X--Xn+Rn, минимальная-- Xn-Rn. Если по оси Х все такие отрезки [Xn-Rn;Xn+Rn] пересекаются, находим такое же пересечение по оси У. Если и оно существует, то существует некая область пересечения. Если нет--то не судьба. Проверку пересечения отрезков, думаю, понятно как реализовывать.
Зы: найдете ошибку--не судите строго)

[SuHar`]

Оля-ля, Не. Идея интересная, но опять же могу намалевать случай для трех кругов, когда это работать не будет: три круга попарно пересекаются, но все сразу трех точек не имеют.

[Milky Man]

Сообщение от Оля-ля

Добрый вечер, предлагаю такой вариант решения: все окружности имеют "крайние" координаты по x и по y. Условно говоря, для каждой окружности Cn максимальная координата по оси X--Xn+Rn, минимальная-- Xn-Rn. Если по оси Х все такие отрезки [Xn-Rn;Xn+Rn] пересекаются, находим такое же пересечение по оси У. Если и оно существует, то существует некая область пересечения. Если нет--то не судьба. Проверку пересечения отрезков, думаю, понятно как реализовывать.
Зы: найдете ошибку--не судите строго)

Это достаточное условие, но не необходимое. БОлее простое достаточное условие - проверка радиусов и центров (см. выше).
Это для квадратов прокатило бы.

[Оля-ля]

Я имею ввиду не попарное пересечение, а ОБЩЕЕ. Ищем пересечение для кругов С1 и С2, потом пересечение этого пересечения с С3 и т д пока не будет пустое множество или пока не дойдем до Сn. И так по каждой оси.
Зы: черезз полчаса код скину, если не облажаюсь))))

[Milky Man]

Сообщение от Оля-ля

Если и оно существует, то существует некая область пересечения.

То существует некая область, в которой присутствуют части всех кругов, о пересечении ничего сказать нельзя.