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