Блог

У меня есть набор трехмерных точек, которые все лежат в одной плоскости. Точки — это просто записи «x y z» в текстовом файле. Я хотел бы найти способ сортировки этих точек, чтобы я мог нарисовать простой многоугольник по всем точкам. У меня было несколько идей:

Идея 1. выберите точку, которая, как известно, находится внутри многоугольника, определенного набором точек, и проведите луч к произвольной точке в наборе. Затем используйте какую-либо угловую функцию, чтобы найти ближайшую точку по углу к первой, затем так далее для всех остальных. Проблема с этой идеей заключается в том, что я не знаю, как найти точку, которая гарантированно находится внутри области. Я хотел использовать центроид, но не все эти наборы будут выпуклыми. Они могут выглядеть как одно из следующих двух изображений:

Как вы можете видеть на втором изображении, центр тяжести может не лежать внутри многоугольника, и на самом деле, если точка поворота слишком крутая в углу, угловая функция, которую я имел в виду, может также не работать.

Идея 2: это похоже на одну из самых простых задач, которые можно было бы решить в соответствии с чем-то вроде задачи коммивояжера. Но я знаю, что существует множество различных конкретных решений и приближений к решению TSP, и я немного не знаю, с чего начать.

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

Я был бы признателен за любую информацию о наилучшем способе решения этой проблемы и о том, пропускаю ли я еще более простой метод. Я программирую это на C , поэтому другим хорошим ответом будут библиотеки или функции, которые могут выполнять такие действия, как поиск 3D-центроида или решение TSP и т. Д. Заранее спасибо за вашу помощь.

это сложная проблема, если вы добавляете ограничение, что вогнутый / выпуклый зазор всегда больше, чем максимальное расстояние между любыми 2 соседними точками

затем вам следует:

1. для каждой точки добавьте 2 индекса

   Я бы использовал для хранения точек что-то вроде этого:

    struct point
    {
    float x,y,z; // point coordinates
    int i0,i1; // index to 2 closest neighbors
    int tmp; // temp for computation purposes 
    };
   point pnt[n]; // n is number of points you got
     

   и очистите их i0,i1=-1; , есть хорошая идея также добавить временную переменную, чтобы у вас было место для флагов во время последней обработки

2. поиск ближайших соседей

   итак, для каждой точки пройдите по всем точкам и запомните 2 ближайшие к ней точки. установите их индексы i0,i1 равными . остерегайтесь этого O(n^2) , если только ваши точки не упорядочены в пространстве. Я вижу это так:

    for (i=0;i<n;i  ) pnt[i].tmp=0;
   for (i=0;i<n;i  )
    {
    i0=-1; l0=-1;
    i1=-1; l1=-1;
    for (j=0;j<n;j  )
     if (i!=j)
      {
      x=pnt[i].x-pnt[j].x; x*=x;
      y=pnt[i].y-pnt[j].y; y*=y;
      z=pnt[i].z-pnt[j].z; z*=z;
      l=x y z;
           if ((l0<0.0)||(l<=l0)) { i1=i0; l1=l0; i0=j; l0=l; }
      else if ((l1<0.0)||(l<=l1)) {               i1=j; l1=l; }
      }
    pnt[i].i0=i0; pnt[i0].tmp  ;
    pnt[i].i1=i1; pnt[i1].tmp  ;
    }
     

   Теперь i0,i1>=0 и temp==2 для всех допустимых точек. Все точки должны быть действительными, если нет, то ограничение не было выполнено или вы неправильно сгруппировали точки (с одной стороны точки высокая плотность, с другой низкая, поэтому оба соседа находятся только с одной стороны)

3. сформируйте ломаную линию

   итак, начните с первой найденной вами допустимой точки и используйте ее в качестве первой точки вашей полилинии / полигона. Затем посмотрите, используйте его i0 и так далее, пока не достигнете начальной точки или недопустимой i0 . Что-то вроде этого (при условии, что все точки действительны):

     for (i0=0,i=0;;i  )
     {
     if (i<0) break; // not valid point
     // here add pnt[i] to polyline
     i=pnt[i].i0;
     if (i==i0) break; // end of polyline/polygon
     }
     

В случае, если вы получили также недопустимые точки, вам следует рекурсивно выполнить это для оставшихся точек (не включая уже действительные точки), а также использовать некоторые максимальные ограничения для расстояний, чтобы вы не объединяли точки, которые не принадлежат друг другу. После этого у вас должно получиться несколько полилиний, поэтому соедините их, если их конечные точки близки…

Для улучшения # 2 вы можете добавить условие, чтобы соседние точки не были в одинаковом направлении, но это может повлиять на острые края.

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