VPF::Контур без самопересечений. - Форум программистов

makartetsky

Дата 11.2.2008, 20:52 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 6.1.2008

Репутация: нет
Всего: нет

Привет. Такая задача.
Есть 2d контур с самопересечениями, заданный отрезками и дугами. Необходимо удалить имеющиеся самопересечения, то оставить только внешние линии контура.

Akina

Дата 11.2.2008, 21:54 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

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

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

makartetsky

Дата 11.2.2008, 23:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 6.1.2008

Репутация: нет
Всего: нет

То есть надо сделать граф. А как программно поворачивать в одну и ту же сторону?

Akina

Дата 11.2.2008, 23:31 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Цитата(makartetsky @ 12.2.2008, 00:14

)

А как программно поворачивать в одну и ту же сторону?

Eujk между двумя векторами (0...2*пи) посчитать можешь? дальше двигаться по ребру с минимальным углом

--------------------

makartetsky

Дата 11.2.2008, 23:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 6.1.2008

Репутация: нет
Всего: нет

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

maxdiver

Дата 15.2.2008, 18:27 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Кстати, эта задача - классическая, и называется она "нахождение внешней грани плоского графа" smile

P.S. в принципе могу выложить код на C++, есть уже написанный и проверенный на олимпиадных задачах smile

makartetsky

Дата 15.2.2008, 21:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 6.1.2008

Репутация: нет
Всего: нет

maxdiver, выкладывай. smile

maxdiver

Дата 17.2.2008, 00:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

Входные данные
Целое n (1 <= n <= 100) -- количество вершин в многоугольнике. Затем координаты вершин. Все его вершины различны. Никакие две подряд идущие стороны не лежат на одной прямой. Все стороны имеют положительную длину.

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

Код

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <vector>

using namespace std;


typedef pair<double,double> point;
vector<point> pt;
int cur_i;


const double EPS = 1E-7;


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

bool cmp_pt (point a, point b)
{
    return a.first < b.first-EPS || abs (a.first-b.first) < EPS && a.second < b.second-EPS;
}

bool eq_pt (point a, point b)
{
    return abs (a.first-b.first) < EPS && abs (a.second-b.second) < EPS;
}

bool in (double n, double a, double b)
{
    return n >= min(a,b)-EPS && n <= max(a,b)+EPS;
}


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 n;
     cin >> n;
     if (n < 3)  throw;
     vector<point>a (n);
     for (int i=0; i<n; ++i)
         cin >> a[i].first >> a[i].second;

     vector < pair<point,point> > b (n);
     for (int i=0; i<n; ++i)
     {
         point left = a[i],  right = a[i==n-1 ? 0 : i+1];
         if (cmp_pt (right, left))
             swap (left, right);
         b[i] = make_pair (left, right);
     }

     map<point,int> pt_id;
     for (int i=0; i<n; ++i)
     {
         point left = b[i].first,  right = b[i].second;
         vector<point> inters;
         inters.push_back (left);
         inters.push_back (right);
         for (int j=0; j<n; ++j)
             if (i != j)
             {
                point left2 = b[j].first,  right2 = b[j].second;
                 double a1 = left.second-right.second,  b1 = right.first-left.first,
                     c1 = right.first*left.second-left.first*right.second;
                 double a2 = left2.second-right2.second,  b2 = right2.first-left2.first,
                     c2 = right2.first*left2.second-left2.first*right2.second;
                 if (abs (a1*b2-a2*b1) < EPS)
                 {
                     if (abs (a1*c2-a2*c1) < EPS && abs (b1*c2-b2*c1) < EPS)
                     {
                         if (in (left2.first, left.first, right.first) && in (left2.second, left.second, right.second))
                             inters.push_back (left2);
                         if (in (right2.first, left.first, right.first) && in (right2.second, left.second, right.second))
                             inters.push_back (right2);
                     }
                 }
                 else
                 {
                     double x = (c1*b2-c2*b1) / (a1*b2-a2*b1);
                     double y = (a1*c2-a2*c1) / (a1*b2-a2*b1);
                     if (in (x, left.first, right.first) && in (x, left2.first, right2.first) &&
                         in (y, left.second, right.second) && in (y, left2.second, right2.second))
                         inters.push_back (point (x, y));
                 }
             }
         sort (inters.begin(), inters.end(), cmp_pt);
         inters.erase (unique (inters.begin(), inters.end(), eq_pt), inters.end());
         for (size_t j=0; j<inters.size()-1; ++j)
         {
             point a = inters[j],  b = inters[j+1];
             if (!pt_id.count(a))  {  pt_id[a] = pt_id.size(); g.push_back (vector<int>());  }
             if (!pt_id.count(b))  {  pt_id[b] = pt_id.size(); g.push_back (vector<int>());  }
             int ia = pt_id[a],  ib = pt_id[b];
             while (pt.size() < pt_id.size())
                 pt.push_back (point());
             pt[ia] = a;
             pt[ib] = b;
             g[ia].push_back (ib);
             g[ib].push_back (ia);
         }
     }

     n = pt_id.size();

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

     int result = 0;

     used.resize (n);
     for (int i=0; i<n; ++i)
         used[i].assign (g[i].size(), false);

     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]);

     for (size_t i=0; i<res.size(); ++i)
     {
         point b = pt[res[i]],  c = pt[res[(i+1)%res.size()]],  a = pt[res[i?i-1:res.size()-1]];
         if (abs ( (b.first-a.first)*(c.second-a.second) - (b.second-a.second)*(c.first-a.first) ) < EPS)
             res.erase (res.begin()+i--);
     }

     cout << res.size() << '\n';
     for (size_t i=0; i<res.size(); ++i)
         cout << pt[res[i]].first << ' ' << pt[res[i]].second << '\n';

}

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »