Что содержит береговая линия в алгоритме Fortune?
Я пытаюсь реализовать алгоритм Фортуны в Джулии, чтобы найти многоугольники Вороного массива случайных точек, но я действительно борюсь с береговой линией.
Я знаю, что береговая линия — это соединение нескольких парабол. Каждая парабола имеет точку из массива в качестве фокуса, поэтому пересечение парабол, расположенных рядом друг с другом, дает «край» между двумя областями Вороного. Каждая точка в массиве будет событием для береговой линии, но также будет нечто, называемое «круговыми точками», которые соответствуют полюсу (самому нижнему в данном случае) круга, который проходит через три «реальные точки». , а реальные точки — это точки в массиве случайных точек.
Я знаю, как пересекать параболы, я также знаю, что когда линия берега проходит через реальную точку, ее парабола будет половиной линии, пересекающей параболы предыдущих точек, и это пересечение легко найти.
Как вы храните пляжную линию? Вы просто сохраняете точки пересечения, когда проходите события, вычисляя каждое пересечение парабол соседей?
Я читаю Алгоритмы и приложения вычислительной геометрии Марка де Берга, но мой родной язык не английский, поэтому мне немного сложно понять некоторые вещи.
Так что было бы здорово, если бы вы могли помочь мне в этом, спасибо заранее.
Ответы 1
При принятии решения о том, как представлять линию пляжа, важно учитывать, что каждое «событие», которое вы обрабатываете в ходе алгоритма, должно вносить в него только местный модификаций. Если линия развертки немного перемещается, но не пересекает никаких событий, то ваше представление береговой линии не должно изменяться.
Следовательно, структура данных линии пляжа не должна включать никаких фактических точек на линии пляжа!
Также важно, чтобы вы могли найти части для модификации за время O(log N).
Самое простое представление — это просто бинарное дерево поиска, содержащее входные точки, которые вносят вклад в параболы береговой линии, по порядку. Изменения, сделанные во время каждого события, состоят из добавления или удаления отдельных точек.
Итак, изменения линии пляжа будут просто добавлять точки, с которыми пересекается линия развертки, по порядку, в этом случае линия развертки горизонтальна, поэтому они будут упорядочены с использованием координаты x, верно? А также если новое событие разбило одну параболу на две, например, у вас есть две точки [x1,y1] и [x2,y2], при этом y2<y1 и x2 близки к x1, когда линия развертки находится во второй точке, моя береговая линия вместо [x1,y1] станет [x1,y1],[x2,y2],[x1,y1]?
Да все верно. вы также должны удалять точки, когда их параболы перекрываются соседними параболами. Все эти события упорядочены по приоритетной очереди в соответствии с координатой x линии развертки, когда они происходят.
Добро пожаловать в StackOverflow. Вы задаете хорошие вопросы. Не могли бы вы выбрать самый важный и отредактировать свой вопрос, чтобы начать с него? Кроме того, не могли бы вы показать свои исследования и то, что вы уже пробовали?