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

[Virtson]

Utkin, да не обращайте внимание =)
ТС хотел так поблагодарить за внимание к проблеме.

[Alpha_nl]

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

Доброе время суток , уважаемые программисты ))
Есть такая вот картинка-

И на этой же картинке, как мы видим есть ответ, вот что-то вроде такой последовательности вершин графа или нескольких последовательностей таких вершин ( на примере их как раз таки две ) и надо получить.
Форма задания графа ( просто , чтобы было понятно какие есть исходные данные) - это два стринггрида - 1) это координаты точек на форме 2) Это матрица связности.
Смысл в том чтобы "обойти" граф по внешним точка, внутренние нас не интересуют.
Если граф состоит из нескольких несвязанных между собой графов - то в ответ идут маршруты "внешнего обхода" всех их по отдельности.
Какие у кого есть по этому поводу идеи?
А именно-
1) как организовать структуру данных.
2) можно ли обойтись здесь без указателей ?


Прикреплю архив. Здесь программа пока просто рисует.

Интересует не программная реализация , а просто идеи того, как лучше решить , какие подзадачи, по-вашему содержит эта задача ))

Вы правильно сказали - это граф. И является лишь одним из его частных случаев. В сожелению теория графов описаная в курсах Intuit.ru не содержит решения геометрии графов. С этим я тоже столкнулся в задаче о влиянии "тяготения" одной вершины на соседние и пошаговое сближение вершин соединённые рёбрами с большим весом. Мне так же пришлось задавать многомерные координаты точек.
Ваша задача имеет геометрическое решение.
Моё видение следующее:
Решение1.
1. Граф разбивается на подграфы по принципу 2 вершины 3 ребра (рис1 синий контур).
2. Для каждого подграфа находим геометрический центр (зеленая вершина) Yср=(Y0+Y2+Y3)/3 ; Xср=(X0+X2+X3)/3 и тд.
3. Для каждой вершины подграфа определяем удаление от его геометрического центра.
4. Обходим граф используя параметры удаления от геометрического центра. Выбираем то ребро обхода для которого конечная вершина наиболее удалена.

Решение 2.
1. Делаем внешную "заливку" геометрической фигуры. В случае касания заливки и вершины или ребра - присваиваем rebro_vneshnee:=true;
vershina_vneshnee:=true;
2. Обходим граф с учетом этого параметра.
Внимание! при обходе 22 вершины вершины 25 и 26 являются внешними.
Здесь решения приоритета (выше /ниже левее правее).