Всем привет!
Есть интересная задачка!
Как можно с помощью математических или логических средств определить что фигура (полигон) разделена на части (одной или несколькими прямыми) и определить эти части(получить к ним отдельный доступ)?
Координаты точек для полигона  от A до J известны!
Точки пересечения прямой и полигона  от R1 до  R4 тоже известны!

Иллюстрация задачи прилагается…





Присоединённый файл ( Кол-во скачиваний: 2 )
 Basefig.JPG 33,31 Kb

Очень просто. Все вершины и ребра полигона помещаем в граф. Включая точки пересечения (которые разобьют соответствующие ребра полигона) и соединяющие их участки прямой. И обходим граф, выделяя все минимальные циклы. Граф обходим, начиная с самой левой точки, и все время сворачиваем направо. Можно и без графа обойтись, но это самая удобная структура, чтобы следить за пройденными ребрами и узлами...
Потом нужно выкинуть цикл, который не входит в полигон (F-R2-R3). 
Это можно сделать по-разному. Например, запомнить, с какой стороны от каждого ребра находится полигон и учитывать это при обходе.

Если честно не совсем понял, то есть считать суммы длины сторон по разному какой короче тот и брать?

Ты про поиск минимальных циклов? В общем случае не всегда минимальный периметр соответствует минимальному полигону. Так что нет. Кроме того, тогда придется перебирать все возможные циклы, а это излишне.
Нужно просто при обходе на каждой развилке все время сворачивать в одну сторону. Вот смотри: начинаем с точки B, т.к. она самая левая. Выбираем нарпавление обхода, что бы полигон был справа, т.е. идем к точке С. В ней вариантов нет - переходим к R1. Там 2 варианта: D либо R2. Выбираем R2, т.к. этот путь соответствует повороту направо и т.д., пока не вернемся к B. Далее нужно найти следующий начальный узел. Это должен быть самый левый узел, где еще есть непросмотренные варианты. Т.е. R1. Идем по непройденному ребру к В и опять, все время направо, пока не замкнемся. 
Здесь есть еще тонкости: например, ребро может быть пройдено дважды (но в разных направлениях). Но только так, чтобы справа обязательно был полигон. Т.е. ребро R1-R2 можно проходить дважды, а вот AB только один раз. Поэтому я и говорила, что при занесении ребер в граф нужно запомнить, с какой стороны у каждого полигон. Для исходных ребер полигона это просто, а вот с кусками пересекающей прямой нужно повозиться. Прроще всего определить, внутри ли полигона средняя точка отрезка: для внутренних участков приписать полигон с обеих сторон, для внешних - ни с одной. 
 

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

maxdiver, 
Да, это точно нахождение всех граней; ну, с некоторыми уточнениями. А алгоритм, о котором ты говоришь, похож на тот, который я описала? Самой интересно: в свое время искала-искала что-то более общее. Казалось бы, есть определение грани графа, а общего алгоритма я так и не нашла. Общего в том смысле, что без учета геометрии. Потом, правда, пришло в голову, что изображение планарного графа на плоскости вовсе не единственно, так что грани в некотором смысле тоже... 
Пыталась найти тему на которую ты сослался (прямо по твоему названию), но ничего не нашлось, наверное не совсем точно...

http://forum.vingrad.ru/forum/topic-195699.html
Сам посмотрел - там не совсем то, там прога выводит внешнюю грань тока 
И там задача вообще немножко другая была, там ещё самому надо было все отрезки со всеми пересекать.
Ну могу поискать у себя код и для всех граней.

Earnest

Ну в общем то же самое, что ты сказала 
Стартуем из любой вершины по любому непройденному ребру (прохождение по ребру в одну и в другую стороную считаем как различные), и идём так: приходя в какую-то вершину по некоторому ребру, всегда выходим из неё по ребру, следующему после нашего в порядке сортировки по полярному углу.

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

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

Это сообщение отредактировал(а) maxdiver - 6.1.2009, 23:15

Забыл отметить, что если непосредственно искать все грани, как я описывал, то найдётся ещё внешняя грань - в данном случае весь многоугольник. Это обычная проблема с этим алгоритмом всех граней, я не знаю, как её красиво обходить, я поступал так. Внешняя грань, найденная алгоритмом, будет отличаться от остальных тем, что она будет обходиться в обратном порядке. Кроме того, если правильно запускать процесс нахождения всех граней (например, из самой верхней вершины, а из неё по самому "левому" ребру), то первой найдётся именно внешняя грань, поэтому первую найденную грань выкидываем (обычно на практике она не нужна).

Добавлено через 10 минут и 43 секунды
Откопал у себя код.

Условие задачи:


Т.е. здесь внешнюю грань тоже надо выводить.

Решение (немного неоптимально написал по длине кода, но сейчас лень переписывать нормально  ):


Добавлено через 14 минут и 3 секунды
А в другой задаче, где надо было не выводить внешнюю грань, я отсекал её таким кодом (естественно, это надо делать до основного цикла поиска граней):

Я решила задачу выкидывания внешней грани по-другому - учетом обхода. 
Как я уже говорила, каждому ребру приписывается два признака: есть полигон справа, есть полигон слева. 
Каждое ребро мы можем пройти только один раз - так, чтобы полигон был справа по обходу. Соответственно, все полигоны получаются ориентированными по часовой стрелке. А внешняя грань всегда получается ориентированной наоборот. Кроме того, признак ребра (наличие полигона справа и слева) участвует в определении следующего ребра наряду с углом. В результате можно отсеять дырки, которые в смысле графа являются гранями ничуть ни хуже.


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


Я не изобретала велосипед. Как-то я наткнулась на страничку какого-то вроде канадского профессора, где очень хорошо иллюстрировался принцип решения булевских задач над полигонами (объединение, пересечение, разность, ...).  Принцип был понятен из пары слов и пары картинок. Был и код, но он привел меня в ужас. Явно студенты писали - сплошная лапша. Но, в принципе, задача, хорошо распадалась: поиск пересечений (метод сканирующей линии), классификация полученных ребер (тоже сканирующая линия), обход. Ну и плюс тонкости с точностью представления координат и вычислений.

Добавлено через 6 минут и 42 секунды

Вот здесь я тоже по-другому делаю: не с любой, а с минимальной, где есть непройденные ребра. А стартовое ребро тоже выбираем не абы как, а с наименьшим углом + такое, что справа есть полигон. Удачный старт сразу избавляет нас от "лишних" полигонов. Для меня это было очень критично, т.к. число вершин исчисляется десятками тысяч, а то и больше...

Earnest
Идея понятна. Хотя там наверно тоже не менее аккуратно надо подумать и написать. Зато да, с несколькими компонентами связности всё удачно получится.

Ну вряд ли это сильно что-то меняет, граней-то всё равно O(N), хоть с дырками, хоть без

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

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

Спасибо!
А вот еще вопрос:
Есть два многоугольника с координатами, нужно сделать их логическое вычитание…
Как это сделать ума не прилажу!?
Рисунок ниже:

GPC?

Есть фигуры А и Б заданне из отрезков
1)пересечь каждый отрезок фигуры А с каждым отрезком  фигуры Б. Если пересекаются - делим отрезки на 2 части точкой пересечения.
теперь все фигура А состоит из отрезков каждый из который лежит либо полностью внутри либо снаружи от фигуры Б. Аналогично с Б.
2)Результат А - Б будет состоять из отрезков А, которые лежат снаружи Б + отрезки Б, которые лежат внутри А!
Все!

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

PPS: модифицируя шаг 2 можно легко получить  и любые другие буленовские операции с регионами

GPC Рулит! все получилось!