Sorting voronoi cell vertices to compute polygon

Question

I'm currently trying to get the clipped cells from a Polygon-Voronoi-Intersection.

Here is what I've got so far:

I have a polygon and computed some points in it to calculate a voronoi diagram and the red lines on the figure below are the voronoi edges. Then I used an algorithm to get the corner points from every cell and now I need to get the corners in the right direction (clockwise) to generate the cell polygon.

Found Corners for one cell

First I was using this method:

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

but in some special concave polygons this doesn't work and the right order gets mixed up.

Does anyone have a suggetion or hint how this could be done the most simplest way? Consider that the polygon points are in the right order already and the voronoi corners are mixed up and need to get sorted to the polygon points.

My idea:

• Find first polygon point in cell corners
• go along polygon direction and look if point of voronoi vertices is on that line.
• if yes: get endpoint of found voronoi edge and look for shared voronoi edges.
• if shared edges found, always take the most right one
• do until you reach fist point

Is that the only way I could do that?

EDIT - UPDATE

Okay I have some sort of half answer now.

As I said, I have all the vertices which belong to one of the voronoi's cells but the order is still messed up so I thought I could sort them by angle from the centroid like so:

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

But this doesn't always work. Here are the examples when its working and when not. The problem is that on concave edges the angle from the centorid to the corner is sometimes smaller than the one I really need. Any suggestion on how to fix this?

Here its working

Here its not working...

Answer 1

This is how is sort the list of vertices in clockwise order for a cell in my Voronoi generation. Assuming you know which vertices you need to sort this code should do the job.

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