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

StackOverflow https://stackoverflow.com//questions/9612065

Вопрос

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

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

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

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

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

Это было полезно?

Решение

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

Сказать:

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.

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

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

Другие советы

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

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

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

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

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

Вот фрагмент C # код для вычисления Chigncenter 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 ;
.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top