Сообщество программистов Autodesk в СНГ :: Сортировка и расположение кривых для создания замкнутого контура

Сообщество программистов Autodesk в СНГ
Revit API
Сортировка и расположение кривых для создания замкнутого контура

15/02/2015

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

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

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

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

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

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

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

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

Код - XML: [Выделить]

  (2.74,8.38,0) --> (2.74,8.46,0)
  (2.74,8.38,0) --> (2.76,8.38,0)
  (2.76,8.38,0) --> (2.76,8.44,0)
  (2.76,8.44,0) --> (3.05,8.44,0)
  (3.05,8.44,0) --> (3.05,8.38,0)
  (3.05,8.38,0) --> (3.08,8.38,0)
  (3.08,8.46,0) --> (3.08,8.38,0)
  (2.74,8.46,0) --> (3.08,8.46,0)

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

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

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

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

Код - C#: [Выделить]

  const double _inch = 1.0 / 12.0;
  const double _sixteenth = _inch / 16.0;

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

Код - C#: [Выделить]

/// <summary>
/// Создание новой кривой
/// с той же самой геометрией, но с обратным направлением
/// </summary>
/// <param name="orig">Исходная кривая</param>
/// <returns>Инвертированная кривая</returns>
/// <throws cref="NotImplementedException">Если тип кривой не поддерживается.</throws>
static Curve CreateReversedCurve(
  Autodesk.Revit.Creation.Application creapp,
  Curve orig )
{
  if( !IsSupported( orig ) )
  {
    throw new NotImplementedException(
      "CreateReversedCurve for type "
      + orig.GetType().Name );
  }
 
  if( orig is Line )
  {
    return creapp.NewLineBound(
      orig.GetEndPoint( 1 ),
      orig.GetEndPoint( 0 ) );
  }
  else if( orig is Arc )
  {
    return creapp.NewArc( orig.GetEndPoint( 1 ),
      orig.GetEndPoint( 0 ),
      orig.Evaluate( 0.5, true ) );
  }
  else
  {
    throw new Exception(
      "CreateReversedCurve - Unreachable" );
  }
}

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

Код - C#: [Выделить]

/// <summary>
/// Сортирует список кривых для создания  
/// замкнутой кривой
/// </summary>
public static void SortCurvesContiguous(
  Autodesk.Revit.Creation.Application creapp,
  IList<Curve> curves,
  bool debug_output )
{
  int n = curves.Count;
 // Проходим по всем кривым
 // для проверки на правильность сортировки
 
  for( int i = 0; i < n; ++i )
  {
    Curve curve = curves[i];
    XYZ endPoint = curve.GetEndPoint( 1 );
 
    if( debug_output )
    {
      Debug.Print( "{0} endPoint {1}", i,
        Util.PointString( endPoint ) );
    }
 
    XYZ p;
   // Находим кривую, у которых координаты начальной точки равны координате конечной точки текущей кривой
    bool found = (i + 1 >= n);
 
    for( int j = i + 1; j < n; ++j )
    {
      p = curves[j].GetEndPoint( 0 );
      // Если координаты соответствуют,
     // то это и есть нужная нам следующая кривая
 
      if( _sixteenth > p.DistanceTo( endPoint ) )
      {
        if( debug_output )
        {
          Debug.Print(
            "{0} start point, меняем с кривой  {1}",
            j, i + 1 );
        }
 
        if( i + 1 != j )
        {
          Curve tmp = curves[i + 1];
          curves[i + 1] = curves[j];
          curves[j] = tmp;
        }
        found = true;
        break;
      }
 
      p = curves[j].GetEndPoint( 1 );
      
      // Если же конечная точка соответствует конечной точки текущей кривой
      // то инвертируем кривую
      if( _sixteenth > p.DistanceTo( endPoint ) )
      {
        if( i + 1 == j )
        {
          if( debug_output )
          {
            Debug.Print(
              "{0} end point, меняем направление {1}",
              j, i + 1 );
          }
 
          curves[i + 1] = CreateReversedCurve(
            creapp, curves[j] );
        }
        else
        {
          if( debug_output )
          {
            Debug.Print(
              "{0} end point, заменяем и меняем направление {1}",
              j, i + 1 );
          }
 
          Curve tmp = curves[i + 1];
          curves[i + 1] = CreateReversedCurve(
            creapp, curves[j] );
          curves[j] = tmp;
        }
        found = true;
        break;
      }
    }
    if( !found )
    {
      throw new Exception( "SortCurvesContiguous:"
        + " non-contiguous input curves" );
    }
  }
}

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

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

Код - XML: [Выделить]

  0 endPoint (2.74,8.46,0)
  7 start point, меняем с 1
  1 endPoint (3.08,8.46,0)
  6 start point, меняем с 2
  2 endPoint (3.08,8.38,0)
  5 end point, заменяем и меняем направление 3
  3 endPoint (3.05,8.38,0)
  4 end point, меняем направление 4
  4 endPoint (3.05,8.44,0)
  5 end point, меняем направление 5
  5 endPoint (2.76,8.44,0)
  6 end point, меняем направление 6
  6 endPoint (2.76,8.38,0)
  7 end point, меняем направление 7
  7 endPoint (2.74,8.38,0)

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

Код - XML: [Выделить]

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