Всем Привет

На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Здравствуйте, _defrager, Вы писали:


_>Всем Привет

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Я думаю, что достаточно протестировать на принадлежность каждой из окружностей точку, представляющую среднее арифметическое координат центров с весами, пропорциональными соответствующим радиусам. Если она не принадлежит всем окружностям, то искомой точки нет, в противном случае — это она.

Здравствуйте, _defrager, Вы писали:

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Три варианта.

1. Простой. Берется какая-то сетка, закрашиваются клетки, покрываемые всеми кругами (рисуются один за одним алгоритмом Брезенхема). Алгоритм приблизительный, чем точнее хочется иметь решение, тем больше брать точность сетки.

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

3. Сложный. Пересечение кругов — это или круг (возможно, нулевого радиуса) или этакий выпуклый многоугольник, у которого вместо строн дуги окружностей. Надо только написать процедуру, которая будет пересекать такую фигуру с очередной окружностью. Как это делать с целым кругом, надеюсь, понятно. Теперь многодугник Для этого будем рассматривать, как новый круг пересекается с каждой из дуг многодугника. Возможны три случая — а) новый круг содержит дугу целиком б) новый круг пересекается с дугой (в этом случае находим точки пересечения и строим на них стороны нового многодугника (эта сторона может заканчиваться как на этой дуге, так и на других дугах)) в) дуга за пределами круга (смотрим пересечения с другими дугами). Это уже точное решение.

Здравствуйте, deniok, Вы писали:

D>Я думаю, что достаточно протестировать на принадлежность каждой из окружностей точку, представляющую среднее арифметическое координат центров с весами, пропорциональными соответствующим радиусам. Если она не принадлежит всем окружностям, то искомой точки нет, в противном случае — это она.

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

Здравствуйте, subdmitry, Вы писали:

S>Это не верно. Возьмем две касающиеся окружности одного радиуса и еще одну, проходящую через точку касания. Очевидно, точка среднего арифметического будет лежать в стороне от линии, соединяющей центры первых двух окружностей и проходящую через точку касания.

Да, согласен, интуиция подвела

Здравствуйте, _defrager, Вы писали:


_>Всем Привет

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Ну самое тупое, что можно придумать:
Если все окружности совпадают, то понятно. Берем любые две несовпадающие окружности, находим точки их пересечения. И проверяем каждую из них на принадлежность всем остальным окружностям.

Здравствуйте, _DAle_, Вы писали:

_DA>Если все окружности совпадают, то понятно. Берем любые две несовпадающие окружности, находим точки их пересечения. И проверяем каждую из них на принадлежность всем остальным окружностям.

Отлично! Только так работать не будет — взятые наугад две точки пересечения могут и не содержаться остальных кругах (возьмем, к примеру два пересекающихся круга и еще один полностью в области пересечения). Но верно, что если искомая точка вообще существует, то она может быть взята как точка пересечения каких-то из окружностей. Следовательно, перебрав все возможные пары окружностей, перебрав все их точки пересечения и проверив, находятся ли эти точки внутри остальных кругов, мы решим задачу. Только сложность решения O(n^3), ну для 25 окружностей надеюсь, это сойдет, если, конечно, не надо их сталкивать много раз в секунду. Если надо больше скорости, можно рассмотреть алгоритм 3 из предыдущего письма — он работает за O(n^2).

Здравствуйте, _defrager, Вы писали:

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем?
Если каждый круг пересекается со всеми остальными кругами, такая точка есть.
2 круга пересекаются, если расстояние между их центрами меньше суммы их радиусов.

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Здравствуйте, _defrager, Вы писали:

_>>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем?
DEA>Если каждый круг пересекается со всеми остальными кругами, такая точка есть.

Это не так. Нарисуй три касающихся попарно круга и чуть-чуть сдвинь к общему центру. У них будут попарные пересечения, но не общие для всех трех точки.

DEA>2 круга пересекаются, если расстояние между их центрами меньше суммы их радиусов.

Здравствуйте, _defrager, Вы писали:
_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

поскольку алгоритмически задача, видимо, весьма сложна, можно предложить обходной способ, если такое устроит — создать регионы (в GDI Windows — CreateEllipticRgn) и найти их пересечение (CombineRgn)

Здравствуйте, subdmitry, Вы писали:

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

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

Здравствуйте, MBo, Вы писали:

MBo>поскольку алгоритмически задача, видимо, весьма сложна, можно предложить обходной способ, если такое устроит — создать регионы (в GDI Windows — CreateEllipticRgn) и найти их пересечение (CombineRgn)


Всем рекомендую установить в настройках своего профиля Личные Данные->Форум->Режим по умолчанию=Плоский и читать все ответы как ленту. А то, как я смотрю, регулярно возникает ситуция, когда приведенное правильное решение многие просто не замечают, видимо из-за лени вычитывать все ветки темы.

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, _DAle_, Вы писали:

_DA>>Если все окружности совпадают, то понятно. Берем любые две несовпадающие окружности, находим точки их пересечения. И проверяем каждую из них на принадлежность всем остальным окружностям.

S>Отлично! Только так работать не будет — взятые наугад две точки пересечения могут и не содержаться остальных кругах (возьмем, к примеру два пересекающихся круга и еще один полностью в области пересечения). Но верно, что если искомая точка вообще существует, то она может быть взята как точка пересечения каких-то из окружностей. Следовательно, перебрав все возможные пары окружностей, перебрав все их точки пересечения и проверив, находятся ли эти точки внутри остальных кругов, мы решим задачу. Только сложность решения O(n^3), ну для 25 окружностей надеюсь, это сойдет, если, конечно, не надо их сталкивать много раз в секунду. Если надо больше скорости, можно рассмотреть алгоритм 3 из предыдущего письма — он работает за O(n^2).

Я просто чего-то решил, что нам надо окружности в одной точке пересечь, а не круги.

P.S. Вот такое вот нелепое 1000-ое сообщение на рсдне

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, _defrager, Вы писали:

_>>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

S>Три варианта.

Спасибо! Все варианты нравятся буду пробовать

Думаю, что если такие точки есть, то одна из них находится на перечечении двух окружностей, т.к. регион, в котором эта точка может быть, ограничен отрезками окружностей, и один из "углов" тоже принадлежит этому региону. Поэтому можно сделать так:
1. Исключить варианты непересекающихся окружностей: Найти все круги, которые полностью находятся внутри других, и отбросить внешние. Отдельно рассмотреть извращенный случай концентрических (или немного смещенных, но непересекающихся — как матрешки) окружностей.
2. Найти попарные пересечения для всех окружностей (максимум две точки для каждой пары; одна — если касаются). Тут сразу, если нашли две окружности, которые не пересекаются — то такой точки нет.
3. Для каждой найденной точки пересечения проверить, находится ли она внутри всех кругов.
Можно третий шаг совместить со вторым, чтоб было быстрее (и меньше памяти использовало) — не хранить эти точки, а сразу проверять.

Здравствуйте, _defrager, Вы писали:


_>Всем Привет

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Рассмотрим бинарное отношение заданное на декартовом произведении множества окружностей само на себя
Истина — если имеется непустое множесто точек принадлежащих паре окружностей
Ложь — пара окружностей не имеет общих точек
Очевидно что если произведение всех элементов этого отношения ложь
то подобной точки не существует
От противного — если истина то существует по крайней мере одна — множество точек
принадлежащих всем окружностям не пусто
Врпрос как найти одну из точек множества пока открыт

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

Здравствуйте, subdmitry, Вы писали:

S>3. Сложный. Пересечение кругов — это или круг (возможно, нулевого радиуса) или этакий выпуклый многоугольник, у которого вместо строн дуги окружностей. Надо только написать процедуру, которая будет пересекать такую фигуру с очередной окружностью. Как это делать с целым кругом, надеюсь, понятно. Теперь многодугник Для этого будем рассматривать, как новый круг пересекается с каждой из дуг многодугника. Возможны три случая — а) новый круг содержит дугу целиком б) новый круг пересекается с дугой (в этом случае находим точки пересечения и строим на них стороны нового многодугника (эта сторона может заканчиваться как на этой дуге, так и на других дугах)) в) дуга за пределами круга (смотрим пересечения с другими дугами). Это уже точное решение.
найти минимальную хорду пересечения, сейчас не могу доказать но она
1 не факт что будет у самой маленькой окружности... (от противного)
2 она точно будет лежать своим куском в пересечении...

Здравствуйте, zubr, Вы писали:

Z>найти минимальную хорду пересечения, сейчас не могу доказать но она
Z>1 не факт что будет у самой маленькой окружности... (от противного)

Это в том смысле, что некоторые окружности могут лежать целиком в области многодугника, не пересекая его дуг? Согласен, надо разбирать и такой случай.

Здравствуйте, _defrager, Вы писали:


_>Всем Привет

_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

Первое что приходит на ум, это сканирование наподобии растеризации полигона.

1. находим все "низы" и "верхи" окружностей, находим все точки пересечения , пускай это будут ключевые точки.

2. поднимаемся снизу вверх по каждому из ключевых точек и проверяем есть ли регион внутри всех кругов.

Здравствуйте, subdmitry, Вы писали:

S>3. Сложный. Пересечение кругов — это или круг (возможно, нулевого радиуса) или этакий выпуклый многоугольник, у которого вместо строн дуги окружностей. Надо только написать процедуру, которая будет пересекать такую фигуру с очередной окружностью. Как это делать с целым кругом, надеюсь, понятно. Теперь многодугник Для этого будем рассматривать, как новый круг пересекается с каждой из дуг многодугника. Возможны три случая — а) новый круг содержит дугу целиком б) новый круг пересекается с дугой (в этом случае находим точки пересечения и строим на них стороны нового многодугника (эта сторона может заканчиваться как на этой дуге, так и на других дугах)) в) дуга за пределами круга (смотрим пересечения с другими дугами). Это уже точное решение.

ИМХО.
Этот алгортм можно предварить такой стадией:
Круги заменяем квадратам (понятно какими), давольно быстро находим их пересечение, м.б. точку или отрезок.
А уж потом переходим к основной стадии, избегая проверги полного вхождения круга в многодугник...