планарный граф с фиксированной максимальной длиной ребер

Question

Я хочу создать случайные точки в 2D-пространстве, эти точки будут узлами плоского графа (построенного с использованием алгоритма графа Габриэля или RNG).

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

1) Мне нужно, чтобы все ребра графа были не длиннее заданного порога

2) После того, как я хочу узнать грани графа, грань представляет собой набор узлов, соединенных ребром. Лицо не содержит в себе других узлов. На изображении ниже лица подписаны меткой (F1, F2 ...)

Как сделать эти две вещи? некоторые алгоритмы? Есть какой-то способ, уже известный?

Ниже приведен пример графика, который я должен создать

http://imageshack.us/photo/my-images/688/immagineps.png/

Answer 1

1. Если вы можете допустить некоторую разницу в количестве точек, то вы можете изменить свой алгоритм графа Габриэля на инкрементный (большая часть усилий будет заключаться в увеличении алгоритма Делоне), а затем всякий раз, когда ребро будет слишком длинным вставьте в круг случайную точку, диаметр которой равен этому краю.

2. Наиболее удобные структуры данных для плоских графов ориентированы на ребро: например, список двусвязных ребер и представления quad-edge . Если вы еще не используете структуру данных этого типа для шага Делоне (и я не могу представить, почему бы вам этого не сделать), вы можете отсортировать исходящие соединения каждой вершины по углу. Отсюда легко реализовать функцию, которая принимает половину ребра и возвращает следующую половину ребра на той же грани в направлении против часовой стрелки. Теперь выполните итерацию по всем полуграммам, и для каждого полуграя, который еще не посещался, перебирайте грани, пока не вернетесь к тому, с чего начали. Пометьте все пол ребра во внутренней итерации как одну грань.