排序Voronoi单元的顶点来计算多边形 [英] Sorting voronoi cell vertices to compute polygon

问题描述

目前我试图从一个多边形的Voronoi相交的裁剪细胞

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

下面是我到目前为止有：

Here is what I've got so far:

我有一个多边形，并在其计算某些点来计算Voronoi图并在图中的红线下面是沃罗努瓦边缘。
然后我用一个算法从每一个细胞得到的角点，现在我需要在正确的方向（顺时针）的角落产生细胞多边形。

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

首先，我用这个方法：

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.

有没有人有一个suggetion或暗示怎么可以这样做的最简单的方法是什么？ 。考虑到多边形点以正确的顺序已经和Voronoi图角落都混合起来，需要获得分类到多边形点

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.

我的想法：

• 找到在小区的角落


• 第一多边形点沿多边形的方向去看看，如果Voronoi图顶点的点上行


• 如果是：得到的Vor​​onoi找到边缘端点，查找共享的Voronoi边。


• 如果共享边发现，始终把最合适的人


• 做，直到你到达拳头点

• 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?

修改 - 更新

好吧，我有某种现在一半的答案。

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

但是，这并不总是工作。下面是例子，当其工作时不会。问题是，在凹边从centorid到角的角度有时比我确实需要小。关于如何解决此问题的任何建议。

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

在这里，它不工作...
< IMG SRC =htt​​p://i.stack.imgur.com/z1I1d.pngALT =这行不通>

Here its not working...

推荐答案

这是怎么样的顶点以顺时针方向在我的Voronoi生成单元格的列表。 。假设你知道你需要排序的代码应该做的工作哪些顶点

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

这篇关于排序Voronoi单元的顶点来计算多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！