Как рассечь замкнутый сплайн?

Автор Тема: Как рассечь замкнутый сплайн?  (Прочитано 14962 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #15 : 04-05-2017, 11:59:16 »
На сколько частей нужно разбить этот сплайн, чтобы гарантировано найти точки самопересечения:
Это всё понятно... возможна масса таких примеров. Хотелось бы отработать для начала простые случаи...

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Re: Как рассечь замкнутый сплайн?
« Ответ #16 : 04-05-2017, 12:02:19 »
Хотелось бы отработать для начала простые случаи...
А как ты определишь грань между простыми и непростыми случаями?
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #17 : 04-05-2017, 12:05:42 »
А как ты определишь грань между простыми и непростыми случаями?
Всё субъективно. На мой взгляд чем меньше разбиений на равномерные куски тем случай проще.

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Re: Как рассечь замкнутый сплайн?
« Ответ #18 : 04-05-2017, 12:13:09 »
Всё субъективно. На мой взгляд чем меньше разбиений на равномерные куски тем случай проще.
Именно поэтому (IMHO) задачу следует решать в общем случае.
Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #19 : 04-05-2017, 12:47:23 »
Именно поэтому (IMHO) задачу следует решать в общем случае.
И это не вызывает возражений. Просто я привык двигаться рудиментарным способом с общим вектором движения - от простого к сложному.

Оффлайн Николай Горлов

  • ADN
  • *
  • Сообщений: 238
  • Карма: 34
Re: Как рассечь замкнутый сплайн?
« Ответ #20 : 04-05-2017, 14:39:51 »
м-да... я ж не с пустого места взял, что делить нужно не на 3-4 куска а по максимуму. в общем задача сводится к:
0. выяснить, есть ли вообще самопересечения :)
1. поделить на максимум возможных точек наш сплайн
2. две соседние точки = отрезок. прогнать на пересечение всех со всеми (если совпадают в узловой точке - игнорим)
3. из пункта 2 набираем точки пересечения. возможно их еще придется сортирнуть по возрастанию длины сплайна (лишним не будет)
4. через getClosestPointTo притянуть точки из пункта 3 на сплайн (все-таки была апроксимация, вдруг лежат не на исходном сплайне)
5. рвать сплайн на куски по точкам из пункта 4

с первым пунктом помогу, остальное просто
Код - C++ [Выбрать]
  1. AcGePoint3dArray pts;
  2. if (pSpline != NULL)
  3. {
  4.         // если сплайн 2D, то он рисуетсяили дуговыми или линейными сегментами в зависимости от переменной PLINECONVERTMODE
  5.         // если сплайн 3D, то рисуется только линейными сегментами. изначально переставить переменную проще, чем выяснять 2D или 3D
  6.         // так что в общем случае для начала нужно убедиться, что в полученном варианте не будет дуговых сегментов, геморно играться с булгами
  7.         // а это значит, что PLINECONVERTMODE должна быть равна 0
  8.         struct resbuf rbPLINECONVERTMODE;
  9.         acedGetVar(_T("PLINECONVERTMODE"), &rbPLINECONVERTMODE);
  10.         struct resbuf rbPLINECONVERTMODEtemp;
  11.         rbPLINECONVERTMODEtemp.restype = RTSHORT;
  12.         rbPLINECONVERTMODEtemp.resval.rint = 1;
  13.         acedSetVar(_T("PLINECONVERTMODE"), &rbPLINECONVERTMODEtemp);
  14.         AcDbCurve * pSplineConvertedCurve = NULL;
  15.         if (Acad::eOk == pSpline->toPolyline(pSplineConvertedCurve,99) )
  16.         {// 99 это что-то типа максимальной точности. выше ставить не стоит, ниже - хуже результат
  17.                 pSplineConvertedCurve->getStretchPoints(pts); // вот тут и лежат все точки сплайна
  18.                 delete pSplineConvertedCurve;
  19.                 pSplineConvertedCurve = NULL;
  20.         }
  21.         acedSetVar(_T("PLINECONVERTMODE"), &rbPLINECONVERTMODE);// вернуть системную переменную, больше она не нужна
  22. }
  23.  

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Re: Как рассечь замкнутый сплайн?
« Ответ #21 : 05-05-2017, 06:55:58 »
Вот, что значит решать задачу, без знания теории. У сплайна есть "Control points" и "Control polygon" и сплайн всегда лежит внутри "Control polygon". Соответственно если есть самопересечения "Control polygon" - то там может быть и самопересечение сплайна

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #22 : 05-05-2017, 08:32:45 »
... Соответственно если есть самопересечения "Control polygon" - то там может быть и самопересечение сплайна
И как нам средствами ObjectARX получить Control polygon?

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Re: Как рассечь замкнутый сплайн?
« Ответ #23 : 05-05-2017, 08:40:16 »
Цитировать
И как нам средствами ObjectARX получить Control polygon?
без понятия
public Autodesk.AutoCAD.Geometry.Point2d GetControlPointAt(int index)
у SplineEntity есть Knots, нет это веса, а "Control points" это ControlPoints, каждые три Knot ControlPoint образуют треугольник, все эти треугольники вместе и называются "Control polygon".
А надо просто найти пересечение этих треугольников

теория, вся книга, ещё

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #24 : 05-05-2017, 09:01:40 »
А надо просто найти пересечение этих треугольников
Это всё конечно сильно (с точки зрения теории) но давайте рассмотрим конкретный пример:



Маленькие синенькие кружки - это Control Points. А теперь поясните, как из этого рисунка нам найти точку взаимного пересечения?

Оффлайн trir

  • ADN Club
  • ****
  • Сообщений: 470
  • Карма: 63
Re: Как рассечь замкнутый сплайн?
« Ответ #25 : 05-05-2017, 09:54:48 »
1. Находим пересекающиеся треугольники
2. Получаем полилинии для соответствующих кусочков сплайна
3. Находим пересечения этих полилиний

profit: сильно уменьшаем объём вычислений

Цитировать
сплайн всегда лежит внутри "Control polygon".
это называется convex hull property

Оффлайн Николай Горлов

  • ADN
  • *
  • Сообщений: 238
  • Карма: 34
Re: Как рассечь замкнутый сплайн?
« Ответ #26 : 05-05-2017, 14:11:02 »
1. Находим пересекающиеся треугольники
2. Получаем полилинии для соответствующих кусочков сплайна
3. Находим пересечения этих полилиний

1. треугольники пересекаются по линии а не в одной точке
2. каким образом из линий пересечения треугольников получаются ПОЛИЛИНИИ кусочков сплайна? полилинии = апроксимация, с чего мы собственно и начали
3. ну, тут вообще писать можно долго, но лениво, так что этот пункт опустим до выяснения первых двух.

а теперь по сути:

так работает то, что предлагал я. на видео есть и длина сплайнов и время, затраченное на проведение вычислений (от выбора сплайна до отрисовки точек пересечения)
PS: вот как задача решается без знания теории  :P. кстати, работает и 2D и 3D вариант поиска пересечений.

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #27 : 05-05-2017, 16:15:28 »
3. ну, тут вообще писать можно долго, но лениво, так что этот пункт опустим до выяснения первых двух.
Боюсь мы с Вами не получим внятных объяснений от г-на trir'a. Сей тезис вытекает из пространных, квазинаучных ответов указанного господина на вполне конкретные вопросы. Кроме того (как я вижу) г-н trir склонен цитировать самого себя - подобное возвышение вряд ли позволит ему снизойти из мира абстракции до наших земных проблем...

А теперь в продолжении темы.
Поиск точек взаимного пересечения является второстепенной задачей. Так или иначе она решается вполне успешно. Гораздо интереснее стоит задача получить именно расчленённые куски сплайна по известным уже точкам.
Я например (как уже писал выше) в качестве математической модели сплайна использую экземпляр AcGeNurbCurve2d.
Используя доступные средства ObjectARX его можно расчленить (как мне представляется) только посредством AcGeCurve2d::getSplitCurves, в качестве входного параметра которого используется величина param - соответствующая определённой точке на кривой.
Зная координаты точки взаимного пересечения мы можем получить значение параметра посредством AcGeCurve2d::paramOf. Вот тут и возникает "заковыка", т.к. данная функция возвращает лишь одно значение (о чем я писал раньше). А в нашем случае одной точке должно соответствовать как минимум двум значения параметра.
Можно конечно пробежаться по сплайну и поискать точку итерируя параметр с определённым шагом, но как-то это "грязновато" и неточно.

Отмечено как Решение Debalance 05-05-2017, 21:53:07

Оффлайн Александр Ривилис

  • Administrator
  • *****
  • Сообщений: 13829
  • Карма: 1784
  • Рыцарь ObjectARX
  • Skype: rivilis
Re: Как рассечь замкнутый сплайн?
« Ответ #28 : 05-05-2017, 20:57:55 »
Почти не тестировал и не уверен, что удовлетворит тебя во всех случаях. Но для начала сойдёт:

Код - C++ [Выбрать]
  1. //-----------------------------------------------------------------------------
  2. //----- acrxEntryPoint.cpp
  3. //-----------------------------------------------------------------------------
  4. #include "StdAfx.h"
  5. #include "resource.h"
  6.  
  7. //-----------------------------------------------------------------------------
  8. #define szRDS _RXST("")
  9.  
  10. //-----------------------------------------------------------------------------
  11. //----- ObjectARX EntryPoint
  12. class CSplitSplineApp : public AcRxArxApp {
  13.  
  14. public:
  15.   CSplitSplineApp() : AcRxArxApp() {}
  16.  
  17.   virtual AcRx::AppRetCode On_kInitAppMsg(void *pkt) {
  18.     AcRx::AppRetCode retCode = AcRxArxApp::On_kInitAppMsg(pkt);
  19.     return (retCode);
  20.   }
  21.  
  22.   virtual AcRx::AppRetCode On_kUnloadAppMsg(void *pkt) {
  23.     AcRx::AppRetCode retCode = AcRxArxApp::On_kUnloadAppMsg(pkt);
  24.     return (retCode);
  25.   }
  26.  
  27.   virtual void RegisterServerComponents() {     }
  28.  
  29.   static void RivilisSplitSpline() {
  30.  
  31.     ads_name en; ads_point pt;
  32.     if (acedEntSel(L"\nВыберите самопересекающийся сплайн: ", en, pt) != RTNORM)
  33.       return;
  34.     AcDbObjectId id; acdbGetObjectId(id, en);
  35.     AcDbObjectPointer<AcDbSpline> pSpline(id, AcDb::kForRead);
  36.     Acad::ErrorStatus es = pSpline.openStatus();
  37.     if (es == Acad::eNotThatKindOfClass)
  38.     {
  39.       acutPrintf(L"\nЭто не сплайн!");
  40.       return;
  41.     }
  42.     else if (es != Acad::eOk)
  43.     {
  44.       acutPrintf(L"\nОшибка pSpline.openStatus() = %s", acadErrorStatusText(es));
  45.       return;
  46.     }
  47.     AcGeCurve3d *pgSpline = nullptr;
  48.     if ((es = pSpline->getAcGeCurve(pgSpline)) != Acad::eOk)
  49.     {
  50.       acutPrintf(L"\nОшибка pSpline->getAcGeCurve(pgSpline) = %s", acadErrorStatusText(es));
  51.       return;
  52.     }
  53.     AcGeCurveCurveInt3d cci3d;
  54.     cci3d.set(*pgSpline, *pgSpline);
  55.     int nInt = cci3d.numIntPoints();
  56.     if (nInt > 0)
  57.     {
  58.       std::set<double> parms;
  59.       double param = 0;
  60.       pSpline->getStartParam(param);
  61.       parms.insert(param);
  62.       for (int i = 0; i < nInt; i++)
  63.       {
  64.         if (cci3d.isTangential(i)) continue;
  65.         AcGePoint3d p = cci3d.intPoint(i);
  66.         double par1 = 0, par2 = 0;
  67.         cci3d.getIntParams(i, par1, par2);
  68.         acutPrintf(L"\nInt(%d)=(%g %g %g), par1=%g par2=%g", i, p.x, p.y, p.z, par1, par2);
  69.         parms.insert(par1); parms.insert(par2);
  70.       }
  71.       pSpline->getEndParam(param);
  72.       parms.insert(param);
  73.       AcGeDoubleArray parmsa;
  74.       parmsa.setPhysicalLength((int)parms.size());
  75.       for (std::set<double>::iterator it = parms.begin(); it != parms.end(); ++it)
  76.       {
  77.         parmsa.append(*it);
  78.       }
  79.       AcDbVoidPtrArray ents;
  80.       if (pSpline->getSplitCurves(parmsa, ents) == Acad::eOk)
  81.       {
  82.         AcDbBlockTableRecordPointer pCurrSpace(acdbCurDwg()->currentSpaceId(), AcDb::kForWrite);
  83.         if (pCurrSpace.openStatus() == Acad::eOk)
  84.         {
  85.           for (int i = 0; i < ents.length(); i++)
  86.           {
  87.             AcDbEntity *pEnt = static_cast<AcDbEntity *>(ents[i]);
  88.             pCurrSpace->appendAcDbEntity(pEnt);
  89.             pEnt->close();
  90.           }
  91.         }
  92.       }
  93.     }
  94.     else
  95.     {
  96.       acutPrintf(L"\nЭто не самопересекающийся сплайн!");
  97.     }
  98.   }
  99. };
  100.  
  101. //-----------------------------------------------------------------------------
  102. IMPLEMENT_ARX_ENTRYPOINT(CSplitSplineApp)
  103.  
  104. ACED_ARXCOMMAND_ENTRY_AUTO(CSplitSplineApp, Rivilis, SplitSpline, SplitSpline, ACRX_CMD_MODAL, NULL)

Результат работы:

Не забывайте про правильное Форматирование кода на форуме
Создание и добавление Autodesk Screencast видео в сообщение на форуме
Если Вы задали вопрос и на форуме появился правильный ответ, то не забудьте про кнопку Решение

Оффлайн DebalanceАвтор темы

  • ADN Club
  • ****
  • Сообщений: 421
  • Карма: 16
    • Advanced software for AutoCAD
  • Skype: Debalance
Re: Как рассечь замкнутый сплайн?
« Ответ #29 : 05-05-2017, 21:20:47 »
Почти не тестировал и не уверен, что удовлетворит тебя во всех случаях. Но для начала сойдёт:
Интересное решение!
Я даже не не догадывался, что создание экземпляра AcGeCurveCurveInt3d с указанием одной и той же кривой в качестве аргументов может привести к желаемому эффекту!
Я так полагаю сие возможно только в случае взаимопересекающихся кривых?