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

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

Вот что у меня так далеко:

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

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

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

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;
    }

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

Здесь работает

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

 GeoGecco19 июл. 2015 г., 17:03
не могли бы вы предложить мне что-нибудь? Я хочу разделить его на несколько полигонов, но в этом примере показан только шаг для одной ячейки.
 Nicko Po18 июл. 2015 г., 00:46
ИМО, сортировка по углу почти всегда неправильный путь. Кроме того, поскольку ваш многоугольник вогнутый, возможно, что пересечение ячейки вороного и многоугольника приведет к множеству многоугольников. Ваш текущий алгоритм не принимает это во внимание. Оптимальным способом было бы использовать одну из множества библиотек многоугольных клипов и пропустить повторное изобретение колеса.

Ответы на вопрос(1)

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

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);
}
}
 Spi02 сент. 2016 г., 15:40
Всякий раз, когда k <= 1, окончательный результат не должен быть:return hull.Take( vertices.count ).ToArray() ?

Ваш ответ на вопрос