Пересечение окружности с алгоритмом линии развертки

К сожалению, я все еще не настолько силен в понимании алгоритма Sweep Line . Все статьи и учебники по этой теме уже прочитаны, однако до понимания еще далеко. Просто чтобы прояснить ситуацию, я стараюсь выполнять как можно больше упражнений. Но действительно интересные и важные задачи все еще остаются для меня проблемой.

Следующее упражнение я обнаружил в заметках лекции Пересечение отрезка линии всемогущим Джеффом Эриксоном.

Упражнение 2. Опишите и проанализируйте алгоритм строчной линии, чтобы определить, учитывая, что окружностей на плоскости, пересекаются ли какие-либо два, за времени. Каждый круг задается своим центром и радиусом, поэтому входные данные состоят из трех массивов и . Будьте осторожны, чтобы правильно реализовать низкоуровневые примитивы. $n$ $O(n \log n)$ $X[1.. n], Y [1.. n]$ $R[1.. n]$

Давайте попробуем сделать сложную вещь проще. Что мы знаем о пересечении кругов? Какой аналог можно найти с пересечением линий. Две линии могут пересекаться, если они смежные, какое свойство двух кругов должно иметь для пересечения? Пусть будет расстоянием между центром окружностей, и центрами окружностей. Рассмотрим несколько случаев: $d$ $r_{0}$ $r_{1}$

Случай 1: если то решений нет, кружки разделены. $d > r_{0} + r_{1}$
Случай 2: если тогда нет решений, потому что один круг содержится внутри другого. $d < |r_{0} - r_{1}|$
Случай 3: если и то окружности совпадают и существует бесконечное число решений. $d = 0$ $r_{0} = r_{1}$

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

Алгоритм. Теперь нам нужно найти что-то общее между двумя пересекающимися кругами. При пересечении с аналогом на линию нам нужно иметь условие вставки и удаления условия в очередь событий. Допустим, точка события - это координата x первой и последней точек, к которым касается вертикальная линия развертки. В первой точке мы вставляем кружок в статус и проверяем на пересечение (3 случая для проверки упомянуты выше) с ближайшими кружками, в последней точке мы удаляем кружок из статуса .

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

Приложение :

Я вставляю круг, когда вертикальная линия развертки касается круга в первый раз, и удаляю круг из состояния, когда линия развертки касается его в последний раз. Проверка на пересечение должна быть сделана для ближайшего предыдущего круга. Если мы добавили круг к статусу, и уже был другой круг, который мы добавили ранее, и он все еще был там, следовательно, предыдущий круг не был «замкнут», поэтому может быть пересечение.

algorithms computational-geometry ком
источник

всемогущий [цитата нужна]

Джефф

@ com, что вы подразумеваете под "ближайшим предыдущим кругом"?

Джо

Я предполагаю, что statusподдерживает круги, в настоящее время пересекающие линию развертки? Предположим, у вас есть 100 кружков status, и вы обрабатываете событие вставки и вставляете 101-й кружок. Сколько кругов вы сравниваете, чтобы проверить на пересечение? Как вы выбираете, какие круги сравнивать?

Джо

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

Ответы:

Вы определенно на правильном пути. Большой вопрос: когда вы вставляете круг, какие другие круги вы проверяете на пересечение? Как вы выполняете эту проверку?

В случае пересечения сегмента линии сегменты линии в любой заданной координате x полностью упорядочены. (Вы можете перечислить их от самой низкой до самой высокой координаты Y). Таким образом, вы можете поддерживать линейные сегменты в бинарном дереве поиска, а при добавлении нового сегмента вам нужно только выяснить, где он принадлежит в бинарном дереве поиска, и проверить его соседей на наличие событий пересечения.

В случае кругов не сразу понятно, какие круги проверять. Если ваш ответ «все», то ваш алгоритм требует некоторой работы.

Можете ли вы придумать способ представить круги так, чтобы они были полностью упорядочены, как отрезки?

Попробуйте представить круги как два полукруга. Каждое событие вставки фактически является двумя событиями: вставка верхней половины и вставка нижней половины.

Джо
источник

К сожалению, я не понимаю идею полукругов, возможно, вы рассматриваете полукруг как минимальную единицу окружности, которая может пересекаться (3 случая пересечения: пересечение находится на верхнем полукруге, или на нижнем, или на них обоих). В начале все круги упорядочены по координате х их левой и правой границ. Таким образом, мы не должны рассматривать координаты x в статусе , потому что все круги уже находятся в порядке координат x. Поэтому представляется более логичным рассмотреть координату y центра (полукруга) или любую комбинацию y и радиусов. Твое мнение?

ком

@com Вам нужны центральная точка и радиус, чтобы определить, пересекаются ли две окружности, как вы делали в своих собственных проверках пересечения. Только координата y и только радиус не полностью определяют границу круга. Кажется, в алгоритмах стреловидности есть нечто фундаментальное, чего вы не понимаете, но мне сложно сказать, что это такое.

Джо

Я мог бы подумать об этом подходе, аналогичном циклу Bentley Ottmann, который выполняется за O ((n + k) logn) времени.

Я мог бы свести проблему пересечения окружности к пересечению отрезка. Я буду рассматривать вертикальный диаметр, параллельный оси Y для каждого из кругов. Алгоритм должен использовать горизонтальную линию, которая охватывает плоскость снизу вверх.

Теперь у нас есть верхняя конечная точка, нижняя конечная точка для каждого из кругов. Кроме того, нам нужно изменить предикат Intersection, чтобы он говорил, что два сегмента пересекаются тогда и только тогда, когда линия развертки прорезает оба круга в одной точке.

Поскольку задача о пересечении линии может быть решена за O ((n + k) logn), такая же оценка следует и для пересечения окружности.

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

TheGT
источник