ADN Open CIS
Сообщество программистов Autodesk в СНГ

15/02/2015

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

Мне нужно определить полигон, определяющий границу мебели и оборудования для манипуляций с ним на мобильном устройстве.

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

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

Например, я проанализировал класс ExtrusionAnalyzer на столе Desk 1525 x 762mm, входящего в стандартную поставку Revit. На плане этажа оно выглядит примерно вот так:

 

Стол содержит большое количество внутренней геометрии, которая не видна на плане этажа:

 

В результате, информация, возвращаемая ExtrusionAnalyzer гораздо более сложная, чем просто прямоугольник. Фактически, я получаю 10 различных замкнутых полигонов. Первый из них содержит 8 кривых.

Для проверки я вывел координаты конечных точек кривых:

Код - XML: [Выделить]
  1.   (2.74,8.38,0) --> (2.74,8.46,0)
  2.   (2.74,8.38,0) --> (2.76,8.38,0)
  3.   (2.76,8.38,0) --> (2.76,8.44,0)
  4.   (2.76,8.44,0) --> (3.05,8.44,0)
  5.   (3.05,8.44,0) --> (3.05,8.38,0)
  6.   (3.05,8.38,0) --> (3.08,8.38,0)
  7.   (3.08,8.46,0) --> (3.08,8.38,0)
  8.   (2.74,8.46,0) --> (3.08,8.46,0)

Не трудно заметить, что кривые не последовательны. К примеру, конечная точка первой кривой (2.74,8.46) является начальной точкой последней кривой.

Если посмотреть еще более внимательно, то заметите, что координаты некоторых точек необходимо поменять местами, для соединения их с соседними кривыми.

Эти наблюдения и соображения привели к следующей реализации сортировки и упорядочивания кривых.

Сравнение координат конечных точек основывается на той же точности, что применяется в Revit, которое равно 1/16 дюйма. А так как значение длин в базе данных Revit хранится в футах, то для получения значения точности используется следующее значение:

Код - C#: [Выделить]
  1.   const double _inch = 1.0 / 12.0;
  2.   const double _sixteenth = _inch / 16.0;

Инвертирование координат кривой реализуется путем создания новой кривой:

Код - C#: [Выделить]
  1. /// <summary>
  2. /// Создание новой кривой
  3. /// с той же самой геометрией, но с обратным направлением
  4. /// </summary>
  5. /// <param name="orig">Исходная кривая</param>
  6. /// <returns>Инвертированная кривая</returns>
  7. /// <throws cref="NotImplementedException">Если тип кривой не поддерживается.</throws>
  8. static Curve CreateReversedCurve(
  9.   Autodesk.Revit.Creation.Application creapp,
  10.   Curve orig )
  11. {
  12.   if( !IsSupported( orig ) )
  13.   {
  14.     throw new NotImplementedException(
  15.       "CreateReversedCurve for type "
  16.       + orig.GetType().Name );
  17.   }
  18.  
  19.   if( orig is Line )
  20.   {
  21.     return creapp.NewLineBound(
  22.       orig.GetEndPoint( 1 ),
  23.       orig.GetEndPoint( 0 ) );
  24.   }
  25.   else if( orig is Arc )
  26.   {
  27.     return creapp.NewArc( orig.GetEndPoint( 1 ),
  28.       orig.GetEndPoint( 0 ),
  29.       orig.Evaluate( 0.5, true ) );
  30.   }
  31.   else
  32.   {
  33.     throw new Exception(
  34.       "CreateReversedCurve - Unreachable" );
  35.   }
  36. }

С использованием этого метода, можно уже реализовать метод SortCurvesContiguous для сортировки кривых и создания замкнутого контура:

Код - C#: [Выделить]
  1. /// <summary>
  2. /// Сортирует список кривых для создания  
  3. /// замкнутой кривой
  4. /// </summary>
  5. public static void SortCurvesContiguous(
  6.   Autodesk.Revit.Creation.Application creapp,
  7.   IList<Curve> curves,
  8.   bool debug_output )
  9. {
  10.   int n = curves.Count;
  11.  // Проходим по всем кривым
  12.  // для проверки на правильность сортировки
  13.  
  14.   for( int i = 0; i < n; ++i )
  15.   {
  16.     Curve curve = curves[i];
  17.     XYZ endPoint = curve.GetEndPoint( 1 );
  18.  
  19.     if( debug_output )
  20.     {
  21.       Debug.Print( "{0} endPoint {1}", i,
  22.         Util.PointString( endPoint ) );
  23.     }
  24.  
  25.     XYZ p;
  26.    // Находим кривую, у которых координаты начальной точки равны координате конечной точки текущей кривой
  27.     bool found = (i + 1 >= n);
  28.  
  29.     for( int j = i + 1; j < n; ++j )
  30.     {
  31.       p = curves[j].GetEndPoint( 0 );
  32.       // Если координаты соответствуют,
  33.      // то это и есть нужная нам следующая кривая
  34.  
  35.       if( _sixteenth > p.DistanceTo( endPoint ) )
  36.       {
  37.         if( debug_output )
  38.         {
  39.           Debug.Print(
  40.             "{0} start point, меняем с кривой  {1}",
  41.             j, i + 1 );
  42.         }
  43.  
  44.         if( i + 1 != j )
  45.         {
  46.           Curve tmp = curves[i + 1];
  47.           curves[i + 1] = curves[j];
  48.           curves[j] = tmp;
  49.         }
  50.         found = true;
  51.         break;
  52.       }
  53.  
  54.       p = curves[j].GetEndPoint( 1 );
  55.       
  56.       // Если же конечная точка соответствует конечной точки текущей кривой
  57.       // то инвертируем кривую
  58.       if( _sixteenth > p.DistanceTo( endPoint ) )
  59.       {
  60.         if( i + 1 == j )
  61.         {
  62.           if( debug_output )
  63.           {
  64.             Debug.Print(
  65.               "{0} end point, меняем направление {1}",
  66.               j, i + 1 );
  67.           }
  68.  
  69.           curves[i + 1] = CreateReversedCurve(
  70.             creapp, curves[j] );
  71.         }
  72.         else
  73.         {
  74.           if( debug_output )
  75.           {
  76.             Debug.Print(
  77.               "{0} end point, заменяем и меняем направление {1}",
  78.               j, i + 1 );
  79.           }
  80.  
  81.           Curve tmp = curves[i + 1];
  82.           curves[i + 1] = CreateReversedCurve(
  83.             creapp, curves[j] );
  84.           curves[j] = tmp;
  85.         }
  86.         found = true;
  87.         break;
  88.       }
  89.     }
  90.     if( !found )
  91.     {
  92.       throw new Exception( "SortCurvesContiguous:"
  93.         + " non-contiguous input curves" );
  94.     }
  95.   }
  96. }

Наверняка это не самый оптимальный в мире алгоритм, но он вполне меня устраивает для моей задачи.

В текущей реализации метод включает опцию для вывода результата в окно Output Visual Studio. Вот что получилось в результате:

Код - XML: [Выделить]
  1.   0 endPoint (2.74,8.46,0)
  2.   7 start point, меняем с 1
  3.   1 endPoint (3.08,8.46,0)
  4.   6 start point, меняем с 2
  5.   2 endPoint (3.08,8.38,0)
  6.   5 end point, заменяем и меняем направление 3
  7.   3 endPoint (3.05,8.38,0)
  8.   4 end point, меняем направление 4
  9.   4 endPoint (3.05,8.44,0)
  10.   5 end point, меняем направление 5
  11.   5 endPoint (2.76,8.44,0)
  12.   6 end point, меняем направление 6
  13.   6 endPoint (2.76,8.38,0)
  14.   7 end point, меняем направление 7
  15.   7 endPoint (2.74,8.38,0)

Результат для всех 10 контуров геометрии стола после упорядочивания и перевода координат в миллиметры:

Код - XML: [Выделить]
  1. FamilyInstance Furniture Desk <212646 1525 x 762mm> имеет 10 контуров:
  2.   0: (836,2555), (836,2580), (937,2580), (937,2555), (931,2555), (931,2574), (842,2574), (842,2555)
  3.   1: (1954,2580), (1954,2555), (1961,2555), (1961,2574), (2050,2574), (2050,2555), (2056,2555), (2056,2580)
  4.   2: (683,2542), (683,1780), (2208,1780), (2208,2542), (1802,2542), (1802,1831), (1090,1831), (1090,2542)
  5.   3: (664,2561), (664,1761), (2227,1761), (2227,2561)
  6.   4: (683,2440), (785,2440), (785,2542), (683,2542)
  7.   5: (785,1780), (785,1882), (683,1882), (683,1780)
  8.   6: (2107,1882), (2107,1780), (2208,1780), (2208,1882)
  9.   7: (2107,2542), (2107,2440), (2208,2440), (2208,2542)
  10.   8: (702,2542), (702,2555), (1071,2555), (1071,2542)
  11.   9: (1821,2542), (1821,2555), (2189,2555), (2189,2542)

Источник: http://thebuildingcoder.typepad.com/blog/2013/03/sort-and-orient-curves-to-form-a-contiguous-loop.html

Обсуждение: http://adn-cis.org/forum/index.php?topic=1864

Опубликовано 15.02.2015