VPF::Поиск многоугольников - Форум программистов

Ferroman

Дата 13.5.2008, 15:06 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код


  0 1 2 3 4 5 6 7 8 9 
0 ○ ○ ○ ○ ○ ○ ○ ○ ○ ○
1 ○ ○ ○ ● ● ● ○ ○ ○ ○
2 ○ ○ ● ○ ○ ○ ● ○ ○ ○
3 ○ ○ ○ ● ○ ○ ● ○ ○ ○
4 ○ ○ ○ ○ ● ● ○ ○ ○ ○
5 ○ ○ ○ ● ○ ● ○ ○ ○ ○
6 ○ ○ ○ ○ ● ○ ○ ○ ○ ○ 
7 ○ ● ○ ● ○ ○ ○ ○ ○ ○ 
8 ○ ○ ● ○ ○ ○ ○ ○ ○ ○
9 ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

Тут - 2 многоугольника
первый (1,3) (1,4) (1,5) (2,6) (3,6) (4,5) (4,4) (3,3) (2,2)
второй (4,4) (4,5) (5,5) (6,4) (5,3)
Ну, и, в принципе, объединение этих 2х - третий многоугольник удовлетворяющий задание, но было бы хорошо, если бы он отбрасывался.
Подскажите пожалуйста куда смотреть? Может есть готовый алгорим/реализация (на любом язике)?
То что я написал работает долго и криво :(

dereyly

Дата 13.5.2008, 16:51 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

maxim1000

Дата 13.5.2008, 16:51 (ссылка)

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

Загрузка ...

Эксперт

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

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

(4,4) (5,4) (5,5) ?

Добавлено через 2 минуты и 43 секунды
можно сформулировать это в виде поиска циклов в графе

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

qqq

Sartorius

Дата 13.5.2008, 17:57 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

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

может составить список пар, для которых расстояние = 1. ну а затем пробовать замкнуть последовательность этих пар (вроде домино smile

)

Ferroman

Дата 13.5.2008, 18:32 (ссылка)

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

Загрузка ...

Новичок

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

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

Код


можно сформулировать это в виде поиска циклов в графе

Я так пробовал - плохо. Ну или я плохо готовлю.

Всем спасибо, всё попробую.

Sartorius

Дата 13.5.2008, 18:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

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

Код


#include <stdio.h>
#include <vector>

using namespace std;

struct SPair {
    SPair(char f, char s)
    {
        first = f; second = s;
        bIncluded = false; // ÷òî áû äóãè íå ïîâòîðÿëèñü
    }
    print()
    {
        printf("(%d -- %d)", first, second);
    }
    char first, second;
    bool bIncluded;
};

vector<SPair> vPairs;
vector<SPair> vSolutionPairs;


void printPoly(int vertex)
{
    static startVertex;
    static level = 0;

    if (level == 0)
    {
        startVertex = vertex;
    }

    level ++;
    for (int i = 0; i < vPairs.size(); i++)
    {
        SPair & pair = vPairs[i];
        if (pair.bIncluded) continue;
        if (pair.first == vertex)
        {
            pair.bIncluded = true;            
            vSolutionPairs.push_back(pair);
            if (pair.second == startVertex)
            {
                printf("Poly found");
                for (int j = 0; j < vSolutionPairs.size(); j++) vSolutionPairs[j].print();
            }
            printPoly(vPairs[i].second);
            vSolutionPairs.pop_back();
            pair.bIncluded = false;
        } 
        else if (pair.second == vertex)
        {
            pair.bIncluded = true;
            vSolutionPairs.push_back(pair);
            if (pair.first == startVertex)
            {
                printf("Poly found");
                for (int j = 0; j < vSolutionPairs.size(); j++) vSolutionPairs[j].print();
            }
            printPoly(vPairs[i].first);
            vSolutionPairs.pop_back();
            pair.bIncluded = false;
        }
    }
    level--;

}

void main()
{
    vPairs.push_back(SPair(0, 1));
    vPairs.push_back(SPair(1, 2));
    vPairs.push_back(SPair(2, 0));
    vPairs.push_back(SPair(2, 3));
    vPairs.push_back(SPair(0, 5));
    vPairs.push_back(SPair(5, 1));


    printPoly(0);
}

может быть пригодиться. Ищем циклы в которые входит вершина, передаваемая в качестве параметра

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