Я пишу крылатую структуру данных для хранения диаграммы Вороного, и хотя она почти готова, есть одна небольшая проблема, которая поставила меня в тупик. Я должен отметить, что я следую за реализацией, предложенной Okabe, Boots и Sugihara в Spatial Tessellations, что означает, что все бесконечные лучи «обрезаются» граничной кривой для сохранения свойств графа, как показано здесь:
Точки пересечения усеченных лучей и границы (которые хранятся как нормальные вершины структуры данных) имеют определенный логический флаг, установленный на false (в то время как для нормальных вершин он установлен на true); таким образом, мы знаем, какие ребра на самом деле бесконечны.
Я написал функцию для добавления бесконечного луча, которая принимает в качестве аргументов вершину, к которой мы хотим ее соединить, и угол луча, и в очередь обновляет структуру данных. Это работает, проверяя, находится ли вершина в грани, связанной с каждым краем границы. Если это не так, мы переходим к следующему; если это так, то мы знаем, что луч должен разделить именно эту границу, и, таким образом, мы обновляем топологию. Например, если у нас есть следующая структура:
(красные края - граничные), и мы хотим добавить луч, направленный вниз (зеленая стрелка), прикрепленный к Зеленая вершина, мы можем сразу увидеть, что указанный луч в конечном итоге будет расщеплять ребро 3. Однако алгоритм будет делать что-то вроде следующего:
- Является ли вершина
v в грани, связанной с граничным ребром 1 (f1)? NO -> Перейти к следующему краю (f2) - Является ли
v in f2? NO -> Перейти к f3 - Является ли
v in f3? ДА -> Разделить e3 и обновить структуру ВЫПОЛНЕНО
Что снова дает:
.
Однако, если у нас есть эта другая конфигурация, предыдущий алгоритм не работает:
- Является ли
v в f1? ДА -> Разделить e1 и обновить структуру ВЫПОЛНЕНО
Ясно, что луч должен делиться e3, но алгоритм разделяется e1 вместо. Это связано с тем, что и f1, и f3 содержат v, а поскольку f1 предшествует f3, вместо этого он разбивает связанный с ним край. Поэтому нам необходимо учитывать ориентацию луча во время процедуры добавления. У меня было (много) идей о том, как это сделать, но все они в конечном итоге терпят неудачу, потому что они не учитывают тот факт, что усеченные ребра представляют собой конечное представление бесконечного ray.
Например, я подумал о том, чтобы получить две конечные точки граничного ребра по часовой стрелке, а затем проверить, сохраняет ли расщепляемая вершина (которая должна находиться между ними) указанный порядок с некоторой непрерывной сортировкой. алгоритм (алгоритм шнурка Гаусса, например). Однако усеченные края по определению имеют длину 1, поэтому, хотя первое из следующих изображений работает, второе - нет, потому что край слишком короткий.
