План игры
Следующее в основном просто более точное изложение вашей проблемы, но это может помочь:
- Перечислите каждую связанную область на плоскости, которая получается, когда нарисованы границы всех дисков. По предположению, каждая из этих областей покрыта 1 или более дисками.
- Каждый регион — это «вещь, которую нужно покрыть», и каждый диск — это «вещь, которую нужно покрыть». Найдите минимальное покрытие набора для этого набора регионов. К сожалению, это NP-сложно.
Это может не использовать всю структуру, доступную в задаче, но определенно даст вам оптимальный ответ.
Перечисление регионов
Перечислить регионы и записать, какие диски охватывают каждый из них на шаге 1, — сложная часть. Области обычно не являются выпуклыми, что усложняет проверку пересечения, и каждый добавляемый вами круг потенциально удваивает количество областей. Вот как бы я подошел к этому:
Забудьте о фактическом расположении каждого региона и определяйте регион только с точки зрения того, какие диски находятся внутри, а какие снаружи. т.е. область определяется вектором длины n из значений 0/1, каждое из которых указывает, должна ли область внутри или снаружи этого диска быть включена в пересечение — рассматриваемая область формируется путем пересечения всех этих n областей. Таким образом, в принципе у вас может быть до 2 ^ n областей, но на практике некоторые (большинство) векторов создают пустые области, потому что они влекут за собой пересечение двух дисков, которые не имеют пересечения - к счастью, это легко проверить. Должно быть просто рекурсивно генерировать все непустые регионы, за исключением того, что...
Плохие новости
К сожалению, теперь я понимаю, что необходимо выполнить полное тестирование пересечения, потому что не всегда можно сказать, когда область будет пустой. Критический контрпример состоит в том, что для двух дисков A и B, которые имеют небольшой участок перекрытия, и еще одного диска C, который перекрывает каждый из дисков A и B, в зависимости от положения всех трех дисков пересечение всех трех может быть или не быть. быть непустым. (Чтобы увидеть это, нарисуйте 3 диска разных цветов с непрозрачностью 50% в программе для рисования и перемещайте их.)
Работающий хак
Поскольку создание точного списка непустых регионов выглядит так, как будто это будет много работы и займет много времени из-за проверки пересечения, и вы утверждаете, что вам не нужны оптимальные решения, вы можете попробовать просто использовать сетку выборочных точек как набор «вещей, которые нужно охватить» вместо точного списка непустых регионов. Определить, какие диски покрывают заданную точку выборки, несложно. Затем решите максимальное покрытие, как и раньше.
Чтобы убедиться, что пробелов нет, выполните повторный запуск несколько раз, каждый раз случайным образом меняя координаты точек выборки. Увеличивайте плотность точек выборки до тех пор, пока конечный результат не изменится.
01.11.2010
