Конвергенция точек останова в алгоритме Fortune

я реализую алгоритм свиплайна Fortune для вычисления диаграмм Вороного. Моя основная ссылка — «Вычислительная геометрия: алгоритмы и приложения» де Берга и др., и хотя их освещение темы очень ясно, они пропускают несколько небольших, но важных деталей, с которыми мне было трудно разобраться самому. Я искал помощь в Интернете, но другие веб-сайты либо дают более полный обзор, чем учебник, либо дают точно такой же псевдокод, как и в книге.

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

Единственная информация, с которой мне приходится работать, — это координаты x,y трех участков и текущая координата y линии развертки (я использую горизонтальную линию развертки).

На самом деле у меня есть одна идея для определения сходимости. Для двух участков точка разрыва между двумя участками береговой линии, которую они определяют, определяется только текущим положением линии развертки. Я подумал о том, чтобы записать положение двух точек останова, временно немного сдвинуть линию развертки и записать их новые положения. Поскольку ребра в нормальной диаграмме Вороного не искривляются, если расстояние между новой парой точек останова меньше, чем расстояние между старой парой, то точки останова сходятся; в противном случае они расходятся. Но это кажется опасным (я понятия не имею, всегда ли это работает) и уродливым. Наверняка должен быть лучший способ.

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