Вставить набор вершин в выпуклый многоугольник

Я хочу узнать правильный порядок набора вершин в многоугольнике, который задан неупорядоченным образом. Для этой проблемы я разрабатываю алгоритм, основанный на понятиях вычислительной геометрии. Сначала я получаю выпуклую оболочку множества вершин, отсортированных по часовой стрелке. Затем я продолжу работу с оставшимися вершинами, отсортированными по полярному углу, начиная с точки, которая является вершиной с наименьшей координатой X, и я вставлю затем, используя абсолютное значение вычисления перекрестного произведения между вершиной, которую я хочу добавить и две конечные точки ребра в выпуклой оболочке. С помощью этой информации я вставлю соответствующую вершину между двумя точками с наименьшим абсолютным значением на ее перекрестном произведении, как я объяснил выше.

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

Вот фрагмент моего кода, если его недостаточно, спросите меня больше, и используйте C# и.NET 4.5:

var CH = JarvisMarch(P); // P is the set of unsorted vertex of the polygon
            var V = (from v in P where !CH.Contains(v) select v).ToArray();
            var pivot = (from v in V orderby v.Y, v.X select v).FirstOrDefault();                


            if (CH.Count < P.Length)
            {
                QuickSortPolar(ref V, 0, V.Length - 1, pivot);

                foreach (var rm in V)
                {
                    var C = CH.ToArray();
                    var T = new RedBlackTree(); // this is not entirely necessary 
                    var wlk = new List<IComparable>();
                    var min = float.MaxValue;
                    var succ = default(GeometryVertex); // this structure have the X and Y coordenate of the vertex

                    QuickSortCoorX(ref C, 0, C.Length - 1);  // for the sweep plane algorithm

                    for (int i = 0; i < C.Length; i++) // this is just to build the segments in a appropriate way
                    {
                        var j = CH.IndexOf(C[i]) == CH.Count - 1 ?
                            0 : CH.IndexOf(C[i]) + 1;
                        var sgm = new GeometrySegment()
                        {
                            Start = CH[j == 0 ? CH.Count - 1 : j - 1],
                            End = CH[j]
                        };
                        var find = T.Search(sgm);

                        if (find == null || find == RedBlackTree.sentinel)
                            T.Insert(sgm);
                    }

                    T.Inorder(T.root, ref wlk);

                    foreach (var sgm in wlk) // Here is the key of the algorithm
                    {
                        var s = (GeometrySegment)sgm;
                        var curr = (float)Math.Abs(cw(s.Start, rm, s.End));

                        if (curr < min || (curr == min && s.End < succ))
                        {
                            min = curr;
                            succ = s.End;
                        }
                    }

                    CH.Insert(CH.IndexOf(succ), rm);
                }

Заранее спасибо!!

П.Д.: Если какой-либо шаг алгоритма, описанного выше, неясен и требуется дополнительная информация, чтобы помочь мне с этой проблемой, не стесняйтесь спрашивать.

Источник

2 ответа

Решение

Если у вас есть только 2D выпуклые области без отверстий, то вы можете сделать это легко

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

1. вычислить центр области (ваш опорный пункт)

  • просто вычислите средние координаты точки (ваш опорный пункт)

    x0 = (p1.x+p2.x+...pn.x)  / n
y0 = (p1.y+p2.y+...pn.y)  / n

2. вычислить полярные координаты для всех точек

a = atan2(p(i).x-x0,p(i).y-y0)
r = sqrt ((p(i).x-x0)^2,(p(i).y-y0)^2) // ^ is power not xor !!!
  • для скорости вам не нужно г квадрат, вы можете использовать г ^2 таким же образом

3. сортировать все вершины по углу

  • Восходящий или нисходящий будет определять обмотку многоугольника CW/CCW.
  • в соответствии с вашей конфигурацией системы координат

4.Если есть несколько точек под одним углом

  • используйте один с самым высоким г
  • убрать остальное

5. Теперь вы отсортировали вершины

  • что ты и хотел
Источник

Если ваши вершины гарантированно образуют выпуклый многоугольник, этот альтернативный подход сэкономит вычисление углов:

  • сортировать по X; проверить наличие возможных связей в обеих крайностях и отсортировать их по Y;

  • проведите линию через две крайние точки и разделите точки на два подмножества по обе стороны от нее; Вы будете отделять верхнюю и нижнюю части контура;

  • удерживайте точки ниже линии в том же порядке и поменяйте местами остальные. Вы сделали.

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

Источник
Другие вопросы по тегам