Общая точка
От: _defrager Россия  
Дата: 09.03.09 13:26
Оценка:
Всем Привет

На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?
Re: Общая точка
От: deniok Россия  
Дата: 09.03.09 13:53
Оценка:
Здравствуйте, _defrager, Вы писали:


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


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


Я думаю, что достаточно протестировать на принадлежность каждой из окружностей точку, представляющую среднее арифметическое координат центров с весами, пропорциональными соответствующим радиусам. Если она не принадлежит всем окружностям, то искомой точки нет, в противном случае — это она.
Re: Общая точка
От: subdmitry Россия  
Дата: 09.03.09 14:09
Оценка: 37 (3)
Здравствуйте, _defrager, Вы писали:

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


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

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

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

3. Сложный. Пересечение кругов — это или круг (возможно, нулевого радиуса) или этакий выпуклый многоугольник, у которого вместо строн дуги окружностей. Надо только написать процедуру, которая будет пересекать такую фигуру с очередной окружностью. Как это делать с целым кругом, надеюсь, понятно. Теперь многодугник Для этого будем рассматривать, как новый круг пересекается с каждой из дуг многодугника. Возможны три случая — а) новый круг содержит дугу целиком б) новый круг пересекается с дугой (в этом случае находим точки пересечения и строим на них стороны нового многодугника (эта сторона может заканчиваться как на этой дуге, так и на других дугах)) в) дуга за пределами круга (смотрим пересечения с другими дугами). Это уже точное решение.
And if you listen very hard the alg will come to you at last.
Re[2]: Общая точка
От: subdmitry Россия  
Дата: 09.03.09 14:14
Оценка: +1
Здравствуйте, deniok, Вы писали:

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


Это не верно. Возьмем две касающиеся окружности одного радиуса и еще одну, проходящую через точку касания. Очевидно, точка среднего арифметического будет лежать в стороне от линии, соединяющей центры первых двух окружностей и проходящую через точку касания.
And if you listen very hard the alg will come to you at last.
Re[3]: Общая точка
От: deniok Россия  
Дата: 09.03.09 14:18
Оценка:
Здравствуйте, subdmitry, Вы писали:

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


Да, согласен, интуиция подвела
Re: Общая точка
От: _DAle_ Беларусь  
Дата: 09.03.09 14:26
Оценка:
Здравствуйте, _defrager, Вы писали:


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


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


Ну самое тупое, что можно придумать:
Если все окружности совпадают, то понятно. Берем любые две несовпадающие окружности, находим точки их пересечения. И проверяем каждую из них на принадлежность всем остальным окружностям.
Re[2]: Общая точка
От: subdmitry Россия  
Дата: 09.03.09 14:38
Оценка: +1
Здравствуйте, _DAle_, Вы писали:

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


Отлично! Только так работать не будет — взятые наугад две точки пересечения могут и не содержаться остальных кругах (возьмем, к примеру два пересекающихся круга и еще один полностью в области пересечения). Но верно, что если искомая точка вообще существует, то она может быть взята как точка пересечения каких-то из окружностей. Следовательно, перебрав все возможные пары окружностей, перебрав все их точки пересечения и проверив, находятся ли эти точки внутри остальных кругов, мы решим задачу. Только сложность решения O(n^3), ну для 25 окружностей надеюсь, это сойдет, если, конечно, не надо их сталкивать много раз в секунду. Если надо больше скорости, можно рассмотреть алгоритм 3 из предыдущего письма — он работает за O(n^2).
And if you listen very hard the alg will come to you at last.
Re: Общая точка
От: 0xDEADBEEF  
Дата: 09.03.09 15:50
Оценка:
Здравствуйте, _defrager, Вы писали:

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

Если каждый круг пересекается со всеми остальными кругами, такая точка есть.
2 круга пересекаются, если расстояние между их центрами меньше суммы их радиусов.
__________
16.There is no cause so right that one cannot find a fool following it.
Re[2]: Общая точка
От: deniok Россия  
Дата: 09.03.09 16:04
Оценка: +1
Здравствуйте, 0xDEADBEEF, Вы писали:

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


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

DEA>Если каждый круг пересекается со всеми остальными кругами, такая точка есть.

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

DEA>2 круга пересекаются, если расстояние между их центрами меньше суммы их радиусов.
Re: Общая точка
От: MBo  
Дата: 09.03.09 16:38
Оценка:
Здравствуйте, _defrager, Вы писали:
_>На плоскости разбросаны круги разных радиусов (не больше 25). Как можно определить имеется ли точка принадлежащая им всем ?

поскольку алгоритмически задача, видимо, весьма сложна, можно предложить обходной способ, если такое устроит — создать регионы (в GDI Windows — CreateEllipticRgn) и найти их пересечение (CombineRgn)
Re[3]: Общая точка
От: subdmitry Россия  
Дата: 09.03.09 16:39
Оценка:
Здравствуйте, subdmitry, Вы писали:

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


Да, ведь еще есть ситуация типа круг лежит целиком в круге. Такие ситуации надо отсекать, например, просто перестав рассматривать больший круг и оставив только маленький. То есть к такому алгоритму понадобится еще дополнительный предварительный проход, определяющий для каждой пары кругов, не лежит ли один в другом, с последующим выбрасыванием. После этого можно рассматривать точки пересечения.
And if you listen very hard the alg will come to you at last.
Re[2]: Общая точка
От: subdmitry Россия  
Дата: 09.03.09 16:54
Оценка:
Здравствуйте, MBo, Вы писали:

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



Всем рекомендую установить в настройках своего профиля Личные Данные->Форум->Режим по умолчанию=Плоский и читать все ответы как ленту. А то, как я смотрю, регулярно возникает ситуция, когда приведенное правильное решение многие просто не замечают, видимо из-за лени вычитывать все ветки темы.
And if you listen very hard the alg will come to you at last.
Re[3]: Общая точка
От: _DAle_ Беларусь  
Дата: 09.03.09 17:00
Оценка:
Здравствуйте, subdmitry, Вы писали:

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


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


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


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

P.S. Вот такое вот нелепое 1000-ое сообщение на рсдне
Re[2]: Общая точка
От: _defrager Россия  
Дата: 09.03.09 18:13
Оценка:
Здравствуйте, subdmitry, Вы писали:

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


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


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


Спасибо! Все варианты нравятся буду пробовать
Re[2]: Общая точка
От: 24  
Дата: 09.03.09 20:47
Оценка: 6 (1) +1
Думаю, что если такие точки есть, то одна из них находится на перечечении двух окружностей, т.к. регион, в котором эта точка может быть, ограничен отрезками окружностей, и один из "углов" тоже принадлежит этому региону. Поэтому можно сделать так:
1. Исключить варианты непересекающихся окружностей: Найти все круги, которые полностью находятся внутри других, и отбросить внешние. Отдельно рассмотреть извращенный случай концентрических (или немного смещенных, но непересекающихся — как матрешки) окружностей.
2. Найти попарные пересечения для всех окружностей (максимум две точки для каждой пары; одна — если касаются). Тут сразу, если нашли две окружности, которые не пересекаются — то такой точки нет.
3. Для каждой найденной точки пересечения проверить, находится ли она внутри всех кругов.
Можно третий шаг совместить со вторым, чтоб было быстрее (и меньше памяти использовало) — не хранить эти точки, а сразу проверять.
Re: Общая точка
От: nut888 Россия  
Дата: 10.03.09 14:55
Оценка: :)
Здравствуйте, _defrager, Вы писали:


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


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


Рассмотрим бинарное отношение заданное на декартовом произведении множества окружностей само на себя
Истина — если имеется непустое множесто точек принадлежащих паре окружностей
Ложь — пара окружностей не имеет общих точек
Очевидно что если произведение всех элементов этого отношения ложь
то подобной точки не существует
От противного — если истина то существует по крайней мере одна — множество точек
принадлежащих всем окружностям не пусто
Врпрос как найти одну из точек множества пока открыт
Re[2]: Общая точка
От: nut888 Россия  
Дата: 10.03.09 15:07
Оценка:
Могу еще добавить что если искомая точка существует
то она будет внутри круга (минимального радиуса) который содержит центры всех окружностей;
внутри прямоугольника (минимальной площади) который содержит центры всех окружностей
....
Re[2]: Общая точка
От: zubr Россия  
Дата: 13.03.09 12:07
Оценка:
Здравствуйте, subdmitry, Вы писали:

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

найти минимальную хорду пересечения, сейчас не могу доказать но она
1 не факт что будет у самой маленькой окружности... (от противного)
2 она точно будет лежать своим куском в пересечении...
Re[3]: Общая точка
От: subdmitry Россия  
Дата: 13.03.09 15:24
Оценка:
Здравствуйте, zubr, Вы писали:

Z>найти минимальную хорду пересечения, сейчас не могу доказать но она

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

Это в том смысле, что некоторые окружности могут лежать целиком в области многодугника, не пересекая его дуг? Согласен, надо разбирать и такой случай.
And if you listen very hard the alg will come to you at last.
Re: Общая точка
От: minorlogic Украина  
Дата: 13.03.09 17:28
Оценка:
Здравствуйте, _defrager, Вы писали:


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


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


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

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

2. поднимаемся снизу вверх по каждому из ключевых точек и проверяем есть ли регион внутри всех кругов.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: Общая точка
От: VEAPUK  
Дата: 15.03.09 00:58
Оценка:
Здравствуйте, subdmitry, Вы писали:

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


ИМХО.
Этот алгортм можно предварить такой стадией:
Круги заменяем квадратам (понятно какими), давольно быстро находим их пересечение, м.б. точку или отрезок.
А уж потом переходим к основной стадии, избегая проверги полного вхождения круга в многодугник...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.