Я пытаюсь реализовать алгоритм Фортуны в Джулии, чтобы найти многоугольники Вороного из множества случайных точек, но я действительно борюсь с береговой линией.
Я знаю, что береговая линия - это союз нескольких парабол. Каждая парабола имеет точку из массива в качестве своего фокуса, поэтому пересечение парабол, находящихся рядом друг с другом, выдает «ребро» между двумя областями Вороного.
Каждая точка в массиве будет событием для пляжной линии, но будет также нечто, называемое «точками круга», которые соответствуют полюсу (в данном случае наименьшему) круга, который проходит через три «реальных точки» , а действительные точки - это точки в массиве случайных точек.
Я знаю, как пересекать параболы, я также знаю, что, когда береговая линия проходит через реальную точку, ее парабола станет половиной линии, которая пересекает параболы предыдущих точек, и это пересечение легко найти.
Как вы храните пляжную линию? Вы просто сохраняете точки пересечений при прохождении событий, вычисляя каждое пересечение соседних парабол?
Я читаю Алгоритмы и приложения вычислительной геометрии , написанные Марком де Бергом, но мой родной язык не английский, поэтому мне немного трудно понять некоторые вещи.
Так что было бы здорово, если бы вы могли помочь мне в этом, заранее спасибо.