如何在非凸多边形中对顶点排序(如何找到许多解决方案之一)

本文介绍了如何在非凸多边形中对顶点排序(如何找到许多解决方案之一)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我和这里有同样的问题:如何在简单的非凸多边形中排列顶点 但没有我可以使用的解决方案.

我有点的坐标，需要找到一些多边形.没关系，一个点列表有更多解决方案.我需要一些算法来找到其中之一.没关系的哪一个.我真的不知道该怎么解决.

(我已将坐标存储在数组中，并且想在Javascript中使用某种算法)

非常感谢.

解决方案

首先，找到包含所有顶点的边界框的中心.我们将这一点称为C.

根据每个点相对于C的角度对顶点列表进行排序.您可以使用 atan2 (point.y - C.y, point.x - C.x)查找角度.如果两个或两个以上的顶点具有相同的角度，则应首先接近C.

然后，按照它们在列表中出现的顺序绘制它们.您将最终得到不相交且可能不凸的星爆图案.示例:

I have the same problem as here: how to order vertices in a simple, non-convex polygon but there is no solutions I can use.

I have coordinates of points and need to find some polygon. Does not matter that there is more solutions for one list of dots. I need some algorithm to find one of them. Does not matter which one. I really don't know how to solve this.

(I have stored coordinates in array and I want to use some algorithm in Javascript)

Thanks a lot.

解决方案

First, find the center of the bounding box that contains all of your vertices. We'll call this point C.

Sort your list of vertices based on each point's angle with respect to C. You can use atan2(point.y - C.y, point.x - C.x) to find the angle. If two or more vertices have the same angle, the one closer to C should come first.

Then, draw your points in the order they appear in the list. You will end up with a starburst pattern that is non-intersecting and probably non-convex. Example: