(изменено: Владимир Яджак, 23 февраля 2010г. 13:16:13)

Тема: Определение замкнутых контуров из набора объектов

Постановка задачи.

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

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

Я где то слышал что этот алгоритм в 10 автокаде вынесен в документации. Найти я его не могу.
Может какие примеры посоветуете.

Мои идеи:
Алгоритм определения замкнутых областей с использованием графа.
1.    Определить диапазон формирования замкнутой области.
2.    Найти все объекты, которые входят в пределы диапазона.
3.    Обрезать объекты по диапазону.
4.    Сформировать узлы графа:

  • a.    Добавить отрезки (точки) в граф, по линиях пересечений, на пределах диапазона.
    b.    Пройтись по каждой полилинии входящей в диапазон, и добавить отрезки в граф.

5.    Найти самый краткий путь к определенной точке. Подсветить на рисунке.
6.    Исключить из графа точки которые попадают в предыдущий контур.
7.    И так до тех пор пока в графе все точки не будут исключены.

Алгоритм с использованием wykobi. http://www.codeproject.com/KB/recipes/Wykobi.aspx
Пока ничего не придумал.

Уже существующий алгоритм.
Пока его не нашел. Может кто подскажет.

Re: Определение замкнутых контуров из набора объектов

как можно найти контур вокруг указанной точки, или все замкнутые контура в пределах некого диапазона

1. как-то не совсем понятно. сама эта указанная точка/точки уже есть, или ее нада высчитать програмно?
2. этот вопрос наверно лучше увидеть чем прочитать, так что прикрепи сюда две картинки: начальное положение дел, конечный результат. A то что-то совсем грустно :) вникать в постановку задачи.

(изменено: Владимир Яджак, 1 марта 2010г. 18:57:46)

Re: Определение замкнутых контуров из набора объектов

В 2011 AutoCAD существует такой метод:

Acad::ErrorStatus acedTraceBoundary(const AcGePoint3d& seedPoint, bool detectIslands, AcDbVoidPtrArray& resultingBoundarySet);

Пока в документации описания нигде нет!!!
Увы. :cry:

Re: Определение замкнутых контуров из набора объектов

Что нужно сделать мне?

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

От такая от незадача. Мучаюсь уже неделю.
Имеются некоторые наработки. Но конца еще не видно. :)

Re: Определение замкнутых контуров из набора объектов

м-да, сказал как отрезал :)

В 2011 AutoCAD существует такой метод:

а как же на счет хотя бы 2010, т.к. они из одной линейки? я уже не говорю про 2008 и 2009.

ладно, попробуем без картинок.
ты так и не ответил

1. как-то не совсем понятно. сама эта указанная точка/точки уже есть, или ее нада высчитать програмно?

вот что у меня получилось, если я правильно понял вопрос.

//-> отключаем вывод в окне левых акадовских строк        
        struct resbuf cmdechoVar;
        cmdechoVar.restype = RTSHORT;
        cmdechoVar.resval.rint = 0;
        acedSetVar(_T("cmdecho"), &cmdechoVar);
//<-

        AcGePoint3d p;
        AcGePoint3dArray points;
        ads_name plBoundary, plBoundaryPreviousStep;
        if ( acdbEntLast(plBoundaryPreviousStep) != RTNORM )
        {
            acutPrintf(_T("\nЧертеж пустой"));
            return;
        }
        AcDbObjectId id;
        AcDbEntity * pEnt;
        while(acedGetPoint(0,_T("\nВнутренняя точка: "),asDblArray(p)) == RTNORM)
        {
            points.append(p);
        }
        if(points.length() > 0) 
        {
            for(int i= 0;i<points.length();i++)
            {
                /*
                    предпочтительней второй вариант, т.к. первый постоянно выбирает видимые объекты экрана, 
                    и если точек больше одной, то:
                        - создаваемые контура будут включаться в последующие наборы, что может привести к неправильной работе команды
                        - посточнный выбор всех видимых объектов тормозит комп. 
                    так что если надо включить все видимые объекты, то лучше их сразу собрать в ads_name и потом просто подствалять в команду.
                */
                acedCommand(
                    RTSTR, _T("_.-boundary"), 
                    RTSTR, _T("_a"), // дополнительные данные
                    RTSTR, _T("_o"), // тип объекта для контура
                    RTSTR, _T("_p"), // создаваемый контур будет полилинией
                    RTSTR, _T("_i"), // нужно ли искать островки
                    RTSTR, _T("_y"), // нужно, либо _T("_n") - не нужно
                    RTSTR, _T("_b"), // объекты которые будут участвовать в формировании контуров
                    /*1*/RTSTR, _T("_e"), // это будут все видимые на экране объекты, либо вместо этого варианта выбрать /*2*/
                    /*2
                    RTSTR, _T("_n"), // новый набор
                    RTPICKS, mas, // указываем ads_name объектов, которые будут участвовать в команде
                    RTSTR, _T(""),// подтверждение
                    */
                    RTSTR,_T(""), // возвращаемся к указанию точки
                    RTPOINT, asDblArray(points.at(i)), // наша точка, указанная пользователем
                    RTSTR,_T(""), // подтверждаем ввод точки
                    RTNONE // конец команды
                    );

                acdbEntLast(plBoundary);
                if (plBoundaryPreviousStep[0] == plBoundary[0] && plBoundaryPreviousStep[1] == plBoundary[1])
                {
                    acutPrintf(_T("  %d-я точка поганая\n"),i+1);
                    continue; 
                }
                // перекинули последний добавленный в акад объект
                plBoundaryPreviousStep[0] = plBoundary[0];
                plBoundaryPreviousStep[1] = plBoundary[1];

                ::acdbGetObjectId(id,plBoundary);
                if(acdbOpenObject(pEnt,id,AcDb::kForWrite) == Acad::eOk)
                {
                    pEnt->setColorIndex(i+1);
                    pEnt->downgradeOpen();
                    pEnt->draw();
                    pEnt->close();
                }
            }
        }

//-> возвращаем все в зад :)
        cmdechoVar.resval.rint = 1;
        acedSetVar(_T("cmdecho"), &cmdechoVar);
//<-

PS: сделай команду в acrxEntryPoint.cpp и вставь это все в неё.

(изменено: Владимир Яджак, 2 марта 2010г. 11:00:25)

Re: Определение замкнутых контуров из набора объектов

Спасибо сейчас попробую.

а как же на счет хотя бы 2010, т.к. они из одной линейки? я уже не говорю про 2008 и 2009.

У меня сейчас есть библиотеки objectarx_2011_rc_beta из релиз кандидата 2011 автокада так эта комманда только в них определена. arx скомпилированный с библиотеками 2010 автокада в 2011 не запускается. Обратной совместимости также нет.

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

Re: Определение замкнутых контуров из набора объектов

У меня сейчас есть библиотеки objectarx_2011_rc_beta из релиз кандидата 2011 автокада так эта комманда только в них определена. arx скомпилированный с библиотеками 2010 автокада в 2011 не запускается. Обратной совместимости также нет.

естественно. значит, если это не лабораторная работа :), то функция acedTraceBoundary на..., короче говоря не подходит совсем, т.к. прийдется все-равно танцевать с бубном для поддержки хотя бы всей текущей ветки, а не только 2011 акада. кстати, не факт, что эта функция приживется в 2012 :). Сейчас у автодеска колоссальные планы по распиливанию ядра, и можно чего-то и недосчитаться.

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

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

PS: чем меньше будет сетка, тем больше вероятность того, что у тебя обработабтся даже самые маленькие контура пересечений, но 100% гарантии отбработки получится с ОООООчень маленьким шагом сетки, например, 0.0001, следовательно на больших объемах данных комп может и умереть. Если придумаешь что-то получше, напиши, вдруго кому пригодится.

Re: Определение замкнутых контуров из набора объектов

Владимир Яджак пишет:

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

Специальных средств в API нет. Так что алгоритмы придумывай сам.

Re: Определение замкнутых контуров из набора объектов

Спасибо.

Я придумал такое:
1. Собираем все объекты на определенном слое.
2. Превращаем все что возможно в полилинии. И записываем их в некий масив полилиний.
3. Создаем масив точек. Пишем туда все вершины всех полилиний и все точки пересечений всех полилинии. Имеем все точки всех объектов на чертеже.
4. Добавляем точки пересечений как вершины полилиний. Для всех полилиний.
5. Создаем масив отрезков.(только две точки начало и конец). Проходимся по масиве полилиний и каждый отрезок полилинии добавляем в масив отрезко.
6. Сортируем отрезки по Х первой точки.
7. Теперь будем создавать замкнутые контура. Это будет происходит таким образом:
7.1. Проходимся по всех точках. И для каждой точки будем пробовать создать замкнутый контур.
7.2. Контур создавать будем только в том случае если точка уже не присутствует в некотором другом контуре.
7.3. Выбираем из набора отрезков те отрезки которые начинаются с текущей точки.
7.4. Для каждого отрезка измеряем угол к оси Х. Если угол больше 180 то изменяем этот угол так угол = угол - 360
7.5. Среди этих углов ищем найбольшый угол и соответствующий отрезок.
7.6. Повторяем шаги 7.3, 7.4, 7.5, 7.6 для второй точки отрезка.

И так до тех пор пока от следующей точки не будут идти отрезки, или точка не совпадет с точкой начала контура. Тоесть контур замкнут. Записваем ети точки в масив, и например строим по этих точках полилинию...
:)
Возможно не все детально описал, но суть надеюсь будет понятна.

(изменено: Александр, 27 января 2011г. 01:44:26)

Re: Определение замкнутых контуров из набора объектов

Владимир Яджак пишет:

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

1) ToolPack-->Draw-->Boundary Multiple, но она обладает всеми косяками Boundary.
2) Сторонняя программа FlashPlayer - специально создана для этой задачи.
3) В сторонней же GeoTools тоже есть такая команда (кажется ;) - у меня кончился срок демонстрации).
4) В Autocad Map 3D есть инструмент создания площадных топологических моделей - "топологий", "topology", из которых в одно действие выгружаются замкнутые полилинии. Но для его работы необходимо исходные линии основательнейше обработать: разбить на пересечениях, удалить дубликаты, "висячие концы", замкнуть и пр.

(изменено: Владимир Азарко, 25 февраля 2011г. 17:54:25)

Re: Определение замкнутых контуров из набора объектов

Есть такая тема на форуме (требуется регистрация) To find each closed boundary of selected object Может поможет с алгоритмом
Определение замкнутых контуров из набора объектов
Определение замкнутых контуров из набора объектов

Re: Определение замкнутых контуров из набора объектов

Владимир Азарко,
Она основана на всё той же команде _BPOLY (или _BOUNDARY).

(изменено: Александр, 26 февраля 2011г. 01:17:37)

Re: Определение замкнутых контуров из набора объектов

FlashPlayer создаст все возможные замкнутые контуры явно без испльзования BOUNDARY.
Как и Autocad Map 3D.
"Явно", т.к. всегда срабатывают, не виснут на бесконечное время, и не искажают геометрию контуров - как BOUNDARY.