Схождение точек останова в алгоритме Fortune

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

Сказать:

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.

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

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

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

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

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

В моем случае у меня есть горизонтальная линия развертки, которую я двигаю от минимума 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

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

Вот фрагмент кода 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 ;