Сортировка вершин ячеек Вороного для вычисления многоугольника

В настоящее время я пытаюсь получить обрезанные ячейки из многоугольника-Вороного-пересечения.

Вот что у меня есть до сих пор:

У меня есть многоугольник, и я вычислил в нем несколько точек для расчета диаграммы Вороного, а красные линии на рисунке ниже — это ребра Вороного. Затем я использовал алгоритм для получения угловых точек из каждой ячейки, и теперь мне нужно получить углы в правильном направлении (по часовой стрелке), чтобы создать многоугольник ячейки.

Найдены углы для одной ячейки Найдены углы для одной ячейки

Сначала я использовал этот метод:

private List<Vector> sortClockwise(List<Vector> points)
    {
        points = points.OrderBy(x => Math.Atan2(x.X, x.Y)).ToList();
        return points;
    }

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

Есть ли у кого-нибудь предложение или намек, как это можно сделать самым простым способом? Учтите, что точки многоугольника уже расположены в правильном порядке, а углы вороного перепутаны и их нужно отсортировать по точкам многоугольника.

Моя идея:

  • Найти первую точку многоугольника в углах ячеек
  • идите вдоль направления многоугольника и смотрите, находится ли точка вершины вороного на этой линии.
  • если да: получить конечную точку найденного ребра Вороного и найти общие ребра Вороного.
  • если найдены общие ребра, всегда брать самое правильное
  • делай, пока не достигнешь кулака

Это единственный способ сделать это?

ИЗМЕНИТЬ – ОБНОВИТЬ

Хорошо, у меня есть какой-то половинчатый ответ.

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

private List<Vector> sortClockwiseBySentroid(List<Vector> points, Vector center)
    {
        points = points.OrderBy(x => Math.Atan2(x.X - center.X, x.Y - center.Y)).ToList();
        return points;
    }

Но это не всегда работает. Вот примеры, когда это работает, а когда нет. Проблема в том, что на вогнутых гранях угол от центроида до угла иногда меньше, чем тот, который мне действительно нужен. Любое предложение о том, как это исправить?

Вот это работает вот это работает

Здесь не работает... здесь не работает


.net c# computational-geometry polygon voronoi
person GeoGecco    schedule 15.07.2015    source источник
comment
ИМО, сортировка по углу почти всегда неправильный путь. Кроме того, поскольку ваш многоугольник вогнутый, может случиться так, что пересечение ячейки Вороного и многоугольника приведет к множеству многоугольников. Ваш текущий алгоритм не принимает это во внимание. Оптимальным способом было бы использовать одну из множества библиотек полигональных клипов и не изобретать велосипед.   -  person Nicko Po    schedule 18.07.2015
comment
не могли бы вы предложить мне что-нибудь? Я действительно хочу разбить его на несколько полигонов, но в этом примере показан только шаг для одной ячейки.   -  person GeoGecco    schedule 19.07.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


public class ConvexHull
{
private List<Vector2> vertices;

public ConvexHull()
{
    vertices = new List<Vector2>();
}

public ConvexHull(Vector2[] vertices)
{
    this.vertices = new List<Vector2>(vertices);
}

public void AddVertices(Vector2[] vertices)
{
    this.vertices.AddRange(new List<Vector2>(vertices));
}

public Vector2[] Generate()
{
    if (vertices.Count > 1)
    {
        int k = 0;
        Vector2[] hull = new Vector2[2 * vertices.Count];

        // Make the list distinct and sorted
        vertices = vertices.Distinct().OrderBy(v => v.x).ToList();
        //vertices.Sort();
        //Array.Sort(vertices);

        // Build lower hull
        for (int i = 0; i < vertices.Count; ++i)
        {
            while (k >= 2 && Cross(hull[k - 2], hull[k - 1], vertices[i]) <= 0)
                k--;
            hull[k++] = vertices[i];
        }

        // Build upper hull
        for (int i = vertices.Count - 2, t = k + 1; i >= 0; i--)
        {
            while (k >= t && Cross(hull[k - 2], hull[k - 1], vertices[i]) <= 0)
                k--;
            hull[k++] = vertices[i];
        }
        if (k > 1)
        {
            hull = hull.Take(k - 1).ToArray();
        }
        return hull;
    }
    if (vertices.Count <= 1)
    {
        return vertices.ToArray();
    }

    return null;
}

private float Cross(Vector2 p1, Vector2 p2, Vector2 p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
}
person Adam H    schedule 16.05.2016
comment
Всякий раз, когда k ‹= 1, не должен ли окончательный возврат быть: return hull.Take( vertices.count ).ToArray() ? - person Spi; 02.09.2016