Приветствую!

Предположим:


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

На рисунке показаны линии и случаи когда контур получается замкнутым, а когда нет. Разными цветами помечены разные сплайны, т. е. контур может быть образован набором сплайнов.


Присоединённый файл ( Кол-во скачиваний: 68 )
 kontr.JPG 13,75 Kb

DarkDragon, ты ж как-то сумел определить замкнутые они или нет. попробуй словами описать принцип по которому ты определял.

Вообще-то это задача на графы. При этом, если надо просто определить, есть замкнутые контура или нет, достаточно посчитать число граней (это и есть замкнутый контур) по формуле Эйлера (точно не помню, но что-то там из числа вершин и числа ребер).

Bitter, да вот незнаю как сформулировать это словами :( В голову ничего не приходит, поэтому и нарисовал картинки.

Ну к примеру тот замкнутый четырехугольник по сути имеет 5 точек, 4 - которые нарисованы и одна которая лежит на одной из четырех нарисованных точек, тем самым замыкая контур. В этом случае достаточно проверить начальную и конечную точку, и если их координаты совподают, значить можно сделать вывод что контур замкнут, но как быть когда в одном сплайне образуются множество замкнутых триугольников, четырехугольников или многоугольников (как показано на закрашенном многоугольнике)? А если контур замыкают не один сплайн а несколько (как показано на разоцветном многоугольнике)?



Earnest, мне нужно не просто определить есть ли замкнутые, но и найти все эти точки, чтобы можно было закрасить эти контуры.

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

maxdiver, для произвольного графа фокус не пройдет. Дело в том, что грани можно по-разному определять, так что нет однозначности в определении минимальных полигонов. Но если граф эвклидов (т.е. узлы - это эвклидовы точки), то при обходе можно использовать направления ребер. Т.е. начинаем с какого-то узла и идем все время налево (или направо).

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

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

Это сообщение отредактировал(а) maxdiver - 23.3.2010, 00:30

Разумеется, в пересечениях узлы быть должны, чтоб мой метод сработал. Такую хрень, как ты описывашь, тоже можно корректно обойти, но сложнее, да и полигон получится самопересеченный. Но лучше уж пересечения посчитать.
Если нужно просто закрасить, то я бы просто выкинула все узлы степени 1 (пока они не кончатся), а потом закрасила бы метод сканирования по горизонтали. Точно так же (ну чуть сложнее) методом сканирования можно и контура собрать. Только тогда все равно потребуются точки пересечения, иначе какой контур... Хотя, с другой стороны, если самопересеченные контура устраивают, небольшое усложнение анализа при сканировании позволит и их собрать.

Earnest
добавлять новые узлы в пересечениях нельзя, потому что по условию это не засчитывается за пересечение (из картинок видно - там, где в точке пересечения нет узла, там не получился замкнутый контур).

А, вот вторая идея - про выкидывание узлов степени 1, и потом уже обычное закрашивание связных областей, кажется уже верным  (а ведь после удаления узлов степени 1 можно добавлять узлы в точке пересечения).