创建通过所有给定点的非相交多边形

Question

假设我有个的以随机顺序阵列,并且我需要找到一个多边形(由对它们进行排序,使得每对相邻的表示的一侧)穿过所有的点,并且其两侧是不相交的进程.

我尝试通过选择一个点,并将所有点添加到其下面的最终数组,从左到右排序.然后,添加其上方的所有点,从右到左排序.

我被告知我可以添加一个额外的点并自然排序以避免自我交叉..虽然我无法弄明白.有什么简单的方法可以做到这一点？

Answer 1

我们的策略是制定一个计划,我们确定多边形包括所有点,并且我们可以找到一个顺序来连接它们没有任何线相交的地方.

算法:
1.找到最左边的点p
2.找到最右边的点q
3.将点分成A,pq以下的点集,B,pq以上的点集[你可以使用左转点测试( p,q,？)来确定一个点是否在线之上].
4.按x坐标排序A(增加)
5.按x坐标排序B(减少).
6.按顺序返回由p定义的多边形,A中的点,依次为q,B点.

运行时:
步骤1,2,3需要O(n)时间.
步骤4,5需要O(nlogn)时间.
第6步花费O(n)时间.
总运行时间为O(nlogn).

正确性:
通过构造,除了p,q之外的所有点都在集合A或集合B中.因此,来自第6行的输出多边形输出具有所有点的多边形.我们现在需要争论输出多边形中没有任何线段彼此相交.

考虑输出多边形中的每个段.从p到A中第一个点的第一个边不能与任何段相交(因为还没有段).当我们通过x坐标顺序通过A中的点,从每个点开始,下一个段向右移动,所有先前的段都在左侧.因此,当我们从p,通过A的所有点到点q时,我们将没有交叉点.

当我们从q回到B点时也是如此.这些段不能相互交叉,因为它们从右到左.这些线段也不能与A中的任何线相交,因为A中的所有点都在线pq之下,而B中的所有点都在此线之上.

因此,没有任何段相互交叉,我们有一个简单的多边形.

资料来源:http://www.cs.wustl.edu/~pless/546/homeworks/hw1_selectedProblems.pdf

我知道这已经很晚了,但它可能对未来的观众有用.

Answer 2

正如有人所说,最小长度解决方案正是旅行商问题.这是一种非最佳但可行的方法:

计算你的积分的Delauney三角剖分.连续删除边界线段,直到留下插入所有点的边界,或者不再删除任何线段.如果使用该段的三角形的所有点都在边界上,则不要删除边界线段.把这个边界作为你的道路.

我使用40个随机点在Mathematica中实现了这一点.这是典型的结果:

显而易见的反对意见是,您可能会到达一个点,其中并非所有点都是边界点,但是如果不使边界自相交,则无法移除边界线段.这是有效的反对意见.我花了几十次才看到发生这种情况的案例,但最后得到了这个案例:

您可以使用本地拓扑看到一些明显的修复方法,但我会留下详细信息给您!可能有帮助的一点是"边缘翻转",其中你采用两个共享一个边的三角形,比如三角形(p,q,r)和(q,p,s),并用(r,p,s)代替它们( r,s,q)(所有坐标绕三角形逆时针方向).只要此变换中的结果三角形也是逆时针排序,就可以完成此操作.

为了减少修复需求,您需要在每个步骤中对要删除的段进行良好选择.我使用了边界段长度与候选三角形另一侧长度之和(由潜在入射点与段形成的三角形)之比.

Answer 3

您所寻求的在文献中被称为简单的多边形化。例如，请参阅有关该主题的此网页。正如 Miguel 所说，生成星形多边形很容易，但很难找到，例如最小周长多边形，即 Axel Kemper 提到的最小 TSP。对于给定的点集，通常存在指数数量的不同多边形化。

         

对于星形多边形化，有一个问题需要注意：额外的点x（在星的“核”中）不能与现有点重合！这是一种保证x 的算法。找到最近的一对点 ( a,b )，并让x为线段ab的中点。然后按照 Miguel 的帖子进行操作。

Answer 4

这是基于bdean20的answer的 python 3.6代码（需要的库：matplotlib，numpy）。

图片说明：

• 左上方-预定义多边形，其他多边形是随机生成的。
• 虚线-连接绿色（最左侧）和红色（最右侧）多边形的点。
• 黑点位于虚线上。
• 橙色点位于虚线下方。
• 蓝点位于虚线上方。

=========

import random
from operator import itemgetter
import numpy
import matplotlib
import matplotlib.pyplot

class Create_random_polygon:

    def __init__(self, array, min_rand_coord = None, max_rand_coord = None, points_num = None):        
        self.array = array
        self.min_rand_coord = min_rand_coord 
        self.max_rand_coord = max_rand_coord
        self.points_num = points_num

    def generate_random_points(self):
        random_coords_list = []
        for x in range(self.points_num):
            coords_tuple = (random.randint(self.min_rand_coord, self.max_rand_coord),
                            random.randint(self.min_rand_coord, self.max_rand_coord))
            random_coords_list.append(coords_tuple)
        self.array = random_coords_list
        return random_coords_list

    def close_line_to_polygon(self):
        a = self.array[0]
        b = self.array[len(self.array)-1]
        if a == b:
            pass
        else:
            self.array.append(a)    

    def find_leftmost_point(self):
        leftmost_point = None
        leftmost_x = None
        for point in self.array:
            x = point[0]
            if leftmost_x == None or x < leftmost_x:
                leftmost_x = x
                leftmost_point = point
        return leftmost_point

    def find_rightmost_point(self):
        rightmost_point = None
        rightmost_x = None
        for point in self.array:
            x = point[0]
            if rightmost_x == None or x > rightmost_x:
                rightmost_x = x
                rightmost_point = point
        return rightmost_point

    def is_point_above_the_line(self, point, line_points):
        """return 1 if point is above the line
           return -1 if point is below the line
           return  0 if point is lays on the line"""
        px, py = point
        P1, P2 = line_points
        P1x, P1y = P1[0], P1[1]
        P2x, P2y = P2[0], P2[1]
        array = numpy.array([
            [P1x - px, P1y - py],
            [P2x - px, P2y - py],
            ])
        det = numpy.linalg.det(array)
        sign = numpy.sign(det)
        return sign

    def sort_array_into_A_B_C(self, line_points):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points
        A_array, B_array, C_array = [], [], []
        for point in self.array:
            x, y = point
            sing = self.is_point_above_the_line( (x, y), line_points)
            if sing == 0:
                C_array.append(point)
            elif sing == -1:
                A_array.append(point)
            elif sing == 1:
                B_array.append(point)
        return A_array, B_array, C_array

    def sort_and_merge_A_B_C_arrays(self, A_array, B_array, C_array):
        A_C_array = [*A_array, *C_array]
        A_C_array.sort(key=itemgetter(0))
        B_array.sort(key=itemgetter(0), reverse=True)        
        merged_arrays = [*A_C_array, *B_array]
        self.array = merged_arrays

    def show_image(self, array, line_points, A_array, B_array, C_array):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points        
        x = [x[0] for x in array]
        y = [y[1] for y in array]
        Ax = [x[0] for x in A_array]
        Ay = [y[1] for y in A_array]
        Bx = [x[0] for x in B_array]
        By = [y[1] for y in B_array]
        Cx = [x[0] for x in C_array]
        Cy = [y[1] for y in C_array]          
        matplotlib.pyplot.plot(Ax, Ay, 'o', c='orange') # below the line
        matplotlib.pyplot.plot(Bx, By, 'o', c='blue') # above the line
        matplotlib.pyplot.plot(Cx, Cy, 'o', c='black') # on the line
        matplotlib.pyplot.plot(x_lm, y_lm, 'o', c='green') # leftmost point
        matplotlib.pyplot.plot(x_rm, y_rm, 'o', c='red') # rightmost point
        x_plot = matplotlib.pyplot.plot([x_lm, x_rm], [y_lm, y_rm], linestyle=':', color='black', linewidth=0.5) # polygon's division line
        x_plot = matplotlib.pyplot.plot(x, y, color='black', linewidth=1) # connect points by line in order of apperiance        
        matplotlib.pyplot.show()

    def main(self, plot = False):
        'First output is random polygon coordinates array (other stuff for ploting)'
        print(self.array)
        if self.array == None:
            if not all(
                [isinstance(min_rand_coord, int),
                 isinstance(max_rand_coord, int),
                 isinstance(points_num, int),]
                ):
                print('Error! Values must be "integer" type:', 'min_rand_coord =',min_rand_coord, ', max_rand_coord =',max_rand_coord, ', points_num =',points_num)
            else:                
                self.array = self.generate_random_points()            

        print(self.array)
        x_lm, y_lm = self.find_leftmost_point()
        x_rm, y_rm = self.find_rightmost_point()
        line_points = [(x_lm, y_lm), (x_rm, y_rm)]

        A_array, B_array, C_array = self.sort_array_into_A_B_C(line_points)
        self.sort_and_merge_A_B_C_arrays(A_array, B_array, C_array)
        self.close_line_to_polygon()
        if plot:
            self.show_image(self.array, line_points, A_array, B_array, C_array)
        return self.array

if __name__ == "__main__":
    # predefined polygon
    array = [ 
        (0, 0),
        (2, 2),
        (4, 4),
        (5, 5),
        (0, 5),        
        (1, 4),
        (4, 2),
        (3, 3),
        (2, 1),
        (5, 0),
        ]    
    array = None # no predefined polygon
    min_rand_coord = 1
    max_rand_coord = 10000
    points_num = 30

    crt = Create_random_polygon(array, min_rand_coord, max_rand_coord, points_num)
    polygon_array = crt.main(plot = True)    

==========

Answer 5

我刚刚遇到了同样的问题，并提出了一些非常简单的解决方案，也是 n*log(n) 复杂度。

首先取图形内部的一些点，哪个点都没有关系，将它作为中心点是有意义的，无论是在最远点的中间还是所有点的平均值（如重心）。

然后根据从中心点看到的角度对所有点进行排序。排序键相当于点和中心的 atan2。

就是这样。假设 p 是一个点数组 (x, y)，这是 Python 代码。

center = reduce(lambda a, b: (a[0] + b[0], a[1] + b[1]), p, (0, 0))
center = (center[0] / len(p), (center[1] / len(p)))
p.sort(key = lambda a: math.atan2(a[1] - center[1], a[0] - center[0]))