Обход графа с поиком его "внешних" точек.

[pu4koff]

Сообщение от vedro-compota

Алгоритм Грехэма работает с точками не взирая на рёбра, а вся сложность задачи- как раз в возможном отсутствии этих рёбер у графа))

Там есть поиск подходящей вершины. Что мешает там проверить на наличие ребра между вершинами? Нашли вершину, но нет ребра - ищем другую вершину. Не вижу тут трудностей. Хотя "мой" граф этим алгоритмом будет очень проблематично обработать.

[vedro-compota]

ну ))) ваш граф не совсем то - всё-таки на пересечении рёбер должна быть вершина ))

[IliaIT]

А интересно можно ли так вывернуть тут граф что бы количество "внешних точек " было минимальным? тогда и задача по проще построится.

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

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

Угадал идею что хотели создать?

[vedro-compota]

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

а точнее - всегда есть два варианта решения - обход по часовой и против часовой стрелки )))) но не больше двух вариантов ))

[Virtson]

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

Подсказка к алгоритму - введите параметр для каждого ребра: посчитайте количество вершин, смежных c обоими вершинами данного ребра одновременно. Это будет 1 либо 2 (для таких графов, как ваши).
Так вот, Вам нужны те ребра, которые получат параметр = 1. Остается их соединить.

[Utkin]

Сообщение от Virtson

Что же вы спорите ...

Введем дополнительное условие :
ребра не могут пересекаться без образования вершины, иными словами любое пересечение считается вершиной графа (координаты её известны по 4м точкам).
Более того, внуренние вершины все равно НЕ идут в ответ, они только для однозначной постановки задачи.

Тогда графы, которые привел Utkin, будут разными. И с графом pu4koff все становится понятно.

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

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

[Virtson]

Сообщение от Utkin

Более сложные могут понадобиться

Тогда это будет другая задача. Решаем ту, которая есть, без усложнений.

[vedro-compota]

Подсказка к алгоритму - введите параметр для каждого ребра: посчитайте количество вершин, смежных c обоими вершинами данного ребра одновременно. Это будет 1 либо 2 (для таких графов, как ваши).
Так вот, Вам нужны те ребра, которые получат параметр = 1. Остается их соединить.

отличная идея,

Virtson

! спасибо )) сами придумили ? ))

(Уткин, бери пример )))))))

[Virtson]

Сам придумал.
Мне подобными задачами приходится в трехмерном варианте заниматься,
при моделировании атомарных структур =)

[Utkin]

Сообщение от vedro-compota

(Уткин, бери пример )))))))

В смысле ?