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

Question

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

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

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

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

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

Answer 1

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

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

Если три узла не коллинеарны , то ребра, которые перпендикулярно делят пополам сегменты между участками, также касаются круга, ребро которого содержит все три узла. Следовательно, точки останова, определяемые тройкой узлов Вороного, сходятся, если центр круга, определяемого тремя участками, находится перед участком middle , где «впереди» и «сзади» зависят от системы координат и выравнивание линии поворота, которое вы выбрали.

В моем случае у меня есть горизонтальная линия поворота, по которой я двигаюсь от минимума y к максимуму y, поэтому точки останова сходятся, если координата y центра круга больше, чем координата y среднего участка, и расходятся в противном случае.

Редактировать: Кристиан Д'Амато справедливо указывает, что алгоритм выше пропускает некоторые случаи сходимости. Последний алгоритм, который я использовал, приведен ниже. Конечно, я не уверен, что это на 100% правильно, но, похоже, это работает для всех случаев, на которых я его опробовал.

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0

Answer 2

Если сайты расположены по часовой стрелке вокруг центра круга, дуга сходится. Если они расположены против часовой стрелки вокруг центра круга, дуга расходится. (или наоборот, в зависимости от вашей реализации). Проверка на cw или ccw выпадает из кода, который вы используете, чтобы найти центр круга.

Вот фрагмент кода C # для вычисления окружности d точек a, b, c:

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;

Answer 3

Добро пожаловать, Дрейк.Я реализовал это, проверив, сходятся ли точки останова физически в центре круга с «фиктивным» приращением положения линии поворота.Это на самом деле немного усложняется, потому что в некоторых случаях центр круга может быть почти или точно в положении линии поворота, поэтому приращение линии поворота должно быть пропорционально разнице между текущим положением линии поворота и центром окружности, созданным, как вы рекомендуете.

Скажите:

1. currentSweeplineY = 1.0f;circleCenterY = 0.5f (и мы движемся вниз, то есть в убывающем направлении y).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (делитель 10.0f выбран произвольно).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

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

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