Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > разделение полигона


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

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

http://ipicture.ru/

http://ipicture.ru/

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

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

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

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

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

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

Earnest
Цитата
Да, это точно нахождение всех граней; ну, с некоторыми уточнениями. А алгоритм, о котором ты говоришь, похож на тот, который я описала?

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

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

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

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

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

Условие задачи:
Цитата
Все грани

Задан плоский граф своими ребрами. Все его грани -- простые многоугольники. Граф связный. Выведите все его грани. 

Входные данные
Первая строка содержит целое n (1 <= n <= 300) -- количество ребер. Далее в n строках записаны ребра координатами соединяемых вершин. Все координаты целые, не превосходят по модулю 10000. 

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

Пример

Ввод
13 
0 6 3 6 
0 0 4 2 
4 4 6 6 
2 4 3 6 
3 6 6 6 
6 4 6 6 
4 2 6 4 
0 0 0 6 
2 2 2 4 
2 2 4 2 
0 6 2 4 
2 4 4 4 
4 2 4 4 

Вывод
6 
6 
0 0 
6 6 
4 2 
6 4 
3 6 
0 6 

5 
2 4 
0 0 
0 6 
2 2 
4 2 

3 
0 6 
3 6 
2 4 

4 
2 2 
4 2 
2 4 
4 4 

4 
2 4 
3 6 
6 6 
4 4 

4 
4 2 
4 4 
6 6 
6 4


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

Решение (немного неоптимально написал по длине кода, но сейчас лень переписывать нормально smile ):
Код
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>

using namespace std;


vector < pair<int,int> > pt;
int cur_i;


bool cmp (int i, int j)
{
    return
        atan2 (pt[i].first-pt[cur_i].first+0.0, pt[i].second-pt[cur_i].second+0.0) <
        atan2 (pt[j].first-pt[cur_i].first+0.0, pt[j].second-pt[cur_i].second+0.0);
}


vector < vector<int> > g;
vector < vector<char> > used;
vector<int> res;


void rec (int i, int j)
{
    res.push_back (i);
    size_t k;
    for (k=0; k<g[j].size(); ++k)
        if (g[j][k] == i)
            break;
    if (++k == g[j].size())
        k = 0;
    if (!used[j][k])
    {
        used[j][k] = true;
        rec (j, g[j][k]);
    }
}


int main()
{
     int m, n=0;
     cin >> m;
     map < pair<int,int>, int > pt_id;
     for (int i=0; i<m; ++i)
     {
         pair<int,int> a, b;
         cin >> a.first >> a.second >> b.first >> b.second;
         if (pt_id.count(a) == 0)
         {
             pt_id[a] = n++;
             pt.push_back (a);
             g.push_back (vector<int>());
         }
         if (pt_id.count(b) == 0)
         {
             pt_id[b] = n++;
             pt.push_back (b);
             g.push_back (vector<int>());
         }
         int v1 = pt_id[a],  v2 = pt_id[b];
         g[v1].push_back (v2);
         g[v2].push_back (v1);
     }


     for (int i=0; i<n; ++i)
     {
         cur_i = i;
         sort (g[i].begin(), g[i].end(), cmp);
     }

     vector < vector<int> > result;

     used.resize (n);
     for (int i=0; i<n; ++i)
         used[i].resize (g[i].size());
     for (int v=0; v<n; ++v)
     {
         for (size_t i=0; i<g[v].size(); ++i)
             if (!used[v][i])
             {
                 used[v][i] = true;
                 int j = g[v][i];
                 res.clear();
                 rec (v, j);
                 result.push_back (res);
             }
     }

     printf ("%d\n", result.size());
     for (size_t i=0; i<result.size(); ++i)
     {
         printf ("%d\n", result[i].size());
         for (size_t j=0; j<result[i].size(); ++j)
             printf ("%d %d\n", pt[result[i][j]].first, pt[result[i][j]].second);
         printf ("\n");
     }

}


Добавлено через 14 минут и 3 секунды
А в другой задаче, где надо было не выводить внешнюю грань, я отсекал её таким кодом (естественно, это надо делать до основного цикла поиска граней):
Код
         int up = 0;
         for (int i=1; i<n; ++i)
             if (pt[i].second > pt[up].second || pt[i].second == pt[up].second && pt[i].first < pt[up].first)
                 up = i;
         used[up][0] = true;
         rec (up, g[up][0]);

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

Цитата(maxdiver @  7.1.2009,  00:50 Найти цитируемый пост)
я отсекал её таким кодом (естественно, это надо делать до основного цикла поиска граней):

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

Цитата(maxdiver @  7.1.2009,  00:14 Найти цитируемый пост)
И этот велосипед изобретался людьми в процессе контеста неоднократно 

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

Добавлено через 6 минут и 42 секунды
Цитата(maxdiver @  7.1.2009,  00:14 Найти цитируемый пост)
Стартуем из любой вершины по любому непройденному ребру 

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

Автор: maxdiver 8.1.2009, 00:51
Earnest
Идея понятна. Хотя там наверно тоже не менее аккуратно надо подумать и написать. Зато да, с несколькими компонентами связности всё удачно получится.
Цитата
Удачный старт сразу избавляет нас от "лишних" полигонов. Для меня это было очень критично, т.к. число вершин исчисляется десятками тысяч, а то и больше...

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

Автор: Earnest 8.1.2009, 08:51
Цитата(maxdiver @  8.1.2009,  01:51 Найти цитируемый пост)
Ну вряд ли это сильно что-то меняет, граней-то всё равно O(N), хоть с дырками, хоть без

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

Автор: BOB4uK 10.1.2009, 18:12
Спасибо!
А вот еще вопрос:
Есть два многоугольника с координатами, нужно сделать их логическое вычитание…
Как это сделать ума не прилажу!?
Рисунок ниже:
http://ipicture.ru/

Автор: kamre 11.1.2009, 11:32
http://www.cs.man.ac.uk/~toby/alan/software/?

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

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

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

Автор: BOB4uK 19.1.2009, 16:36
GPC Рулит! все получилось!

Автор: skydelver 21.1.2009, 23:32
Вот уж не думал что все будет так сложно.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)