Есть ли алгоритм для создания схемы графика?

Question

Я искал Интернет и, возможно, мне не хватает правильных ключевых слов, но мне не удалось найти ничего подобного. Я нашел только полилинии (или просто строки), которые не являются точными графами. Я хотел бы создать схему графика (радиуса r), как видно на рисунке. Есть ли что-то уже доступное? Я бы хотел избежать повторного использования колеса, так сказать.

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

Оптимально в C#.

Обновление: Мне нужно рассчитать контур полигона, а не просто визуально нарисовать его. Зеленые точки представляют собой полученный многоугольник. Также «внутренние» отверстия полностью игнорируются. Достаточно всего одного многоугольника.

Обновление 2: Лучшее изображение, чтобы показать некоторые более экстремальные случаи. Также края графа никогда не перекрываются, поэтому нет необходимости приспосабливаться к этому.

Обновление 3: Картинка обновлена ​​еще раз, чтобы отразить скос.

Answer 1

Во-первых, для каждой «линии» от точки A до B сгенерируйте прямоугольник (все 4 точки как «путь», так сказать). Затем выполните поиск двух перекрывающихся прямоугольников и объедините их:

Слияние немного сложнее, идея: начните с вычисления угла всех 8 строк (например, если прямоугольники пройдены по часовой стрелке). Затем проведите один прямоугольник до первого пересечения линии, проверьте с углами, какое направление «снаружи», и двигайтесь вдоль линии пересечения второго прямоугольника ... до тех пор, пока вы не вернетесь в начальную точку снова => Теперь вы пройдете форма обоих вместе (и, надеюсь, где-то она была сохранена).

Объединить до тех пор, пока не останется только одна большая часть (или несколько неперекрывающихся частей). Теоретически, начиная с любой точки, вы можете пройти всю форму, но есть еще одна проблема: возможны отверстия.
Если одна фигура имеет два или более набора дизъюнктов точек (где точка из набора 2 не может достижима из набора 1 и наоборот), все, кроме одного, дизъюнктного пути имеют отверстие. Легкая возможность получить реальную внешнюю границу - это поиск экстремума, т. Е. точка с наибольшей или наименьшей координатой X или Y (только одна из 4 комбинаций в достаточном количестве). Этот момент, безусловно, является частью внешней границы.