algorithm - 排序算法从仅具有直角的点创建多边形

Question

给定一组随机顺序的 (x, y) 坐标，是否可以对它们进行排序，以便可以绘制仅具有 90^o 内角或外角的多边形路径。

已知存在这样一条路径，但不知道多边形的边缘点需要按什么顺序连接。

在 SO 中很容易找到的最接近的解决方案是:

• Algorithm to create a polygon from points

• Algorithm to create polygon

这两种方法都使用极坐标对点进行排序，并会生成一个星形多边形，其中只有一些角是 90^o 角。

[注意这是已删除问题的重新发布:Sort algorithm to create a polygon from points with only right angle 。我已经制定了一个解决方案并发布它，却发现该问题已被删除。我将其重新发布在这里，因为其他人可能会发现它有用。]

Answer 1

要将随机排序的 (x, y) 直角点排序为直角多边形顺序:

1. 找到点的中心
2. 找到最远的点
3. 找到距离最远点最近的点
4. 求最远点和最近远程点与 x/y 轴之间的角度(可能是任意两个“最近”点，但最远最近点 点应该减少任何歧义的可能性)
5. 旋转所有点，使其与 x-y 轴对齐
6. 选择任意点作为起点作为第一个踏步点
7. 找到最近的点作为下一个点
8. 如果步进点和下一个点在 x 轴上对齐，则查找 下一个最近的 y 轴对齐点
9. 如果步进点和下一个点是 y 轴对齐的，则查找 下一个最近的 x 轴对齐点
10. 如果没有下一个轴对齐点，则回溯某一点 时间，暂时从可用的回溯点中删除 下一个点，直到另一个下一个回溯轴对齐点是 找到，然后将回溯点添加回可用的点 下一点(回溯是必要的，因为有可能进入 没有路径的飞地，但这不是一个有效的多边形)
11. 将下一个点作为步进点
12. 在 x 轴和 y 轴之间交替排列下一个最近的点
13. 从 10 点开始重复，直到所有点都用完
14. 将点旋转回原来的对齐方式

下面的代码是Python的粗略实现。它将生成多个 SVG 文件进行比较。

points = [(156.40357183517773, 23.19316100057085), (83.97002318399646, 188.27914171909507), (518.4511031561435, 60.897074118366035), (799.3826769425817, 214.44658030407507), (304.1247347870089, -2.8540656494687013), (593.7387174567936, 199.93582818685073), (773.3354502925422, 66.72541735224387), (625.6142873407109, 92.7726440022834), (428.65273673826925, 127.50227953566946), (379.41234908765887, 136.184688419016), (446.0175545049623, 225.98305483689026), (448.871620154431, 530.1077896238992), (509.768694272797, 11.65668646775564), (373.58400585378104, 391.06903555541453), (602.4211263401401, 249.17621583746111), (182.45079848521726, 170.91432395240204), (616.9318784573643, 43.53225635167299), (165.08598071852424, 72.43354865118125), (312.80714367035546, 46.3863220011417), (225.86284290194985, 417.1162622054541), (399.63123250382057, 538.7901985072457), (66.60520541730344, 89.79836641787429)]

def genSVG(points):
    path = "M " + str(points[0][0]) + " " + str(points[0][1]) + " "
    minX = points[0][0]
    minY = points[0][1]
    maxX = minX
    maxY = minY
    for point in points[1:]:
        path += "L " + str(point[0]) + " " + str(point[1]) + " "
        if point[0] < minX:
            minX = point[0]
        elif point[0] > maxX:
            maxX = point[0]
        if point[1] < minY:
            minY = point[1]
        elif point[1] > maxY:
            maxY = point[1]
    path += "Z"
    path = '<path fill="grey" d="' + path + '"/>'

    viewbox = ' viewbox="' + str(minX-1) + ' ' + str(minY-1) + ' ' + str(maxX+1) + ' ' + str(maxY+1) + '"'
    
    width = ' width="' + str((maxX - minX + 2)) + '"'
    height = ' height="' + str((maxY - minY + 2)) + '"'

    return '<svg ' + 'xmlns="http://www.w3.org/2000/svg"' + width + height + viewbox + '>' + path + '</svg>'

def genSVGover(points, overs, center):
    path = "M " + str(points[0][0]) + " " + str(points[0][1]) + " "
    minX = points[0][0]
    minY = points[0][1]
    maxX = minX
    maxY = minY
    for point in points[1:]:
        path += "L " + str(point[0]) + " " + str(point[1]) + " "
        if point[0] < minX:
            minX = point[0]
        elif point[0] > maxX:
            maxX = point[0]
        if point[1] < minY:
            minY = point[1]
        elif point[1] > maxY:
            maxY = point[1]
    path += "Z"
    path = '<path stroke="black" stroke-width="7" fill="none" d="' + path + '"/>'

    viewbox = ' viewbox="' + str(minX-4) + ' ' + str(minY-4) + ' ' + str(maxX+4) + ' ' + str(maxY+4) + '"'
    
    width = ' width="' + str((maxX - minX + 8)) + '"'
    height = ' height="' + str((maxY - minY + 8)) + '"'

    over = "M " + str(overs[0][0]) + " " + str(overs[0][1]) + " "
    for point in overs:
        over += "L " + str(point[0]) + " " + str(point[1]) + " "
    over += "Z"
    over = '<path stroke="red" stroke-width="2" fill="none" d="' + over + '"/>'
        
    return '<svg ' + 'xmlns="http://www.w3.org/2000/svg"' + width + height + viewbox + '>' + path + over + '<circle fill="blue" cx="' + str(center[0]) + '" cy="' + str(center[1]) + '" r="7" />' + '</svg>'

import math
def rotate(points, theta):
    rotated = []
    cosTheta = math.cos(theta)
    sinTheta = math.sin(theta)
    for point in points:
        rotated.append(( cosTheta * point[0] + sinTheta * point[1], -sinTheta * point[0] + cosTheta * point[1] ))
    return rotated

def closest(focus, points):
    if ( points[0] != focus ):
        closestPoint = points[0]
    else:
        closestPoint = points[1]
    closestDist = ( focus[0] - closestPoint[0] )**2 + ( focus[1] - closestPoint[1] )**2
    for point in points:
        if point != focus:
            dist = ( focus[0] - point[0] )**2 + ( focus[1] - point[1] )**2
            if dist < closestDist:
                closestDist = dist
                closestPoint = point
    return closestPoint

def rotangle(points):
    focus = remotest(points)
    closestPoint = closest(focus, points)
    if abs(focus[0] - closestPoint[0]) < tolerance or abs(focus[1] - closestPoint[1]) < tolerance:
        return 0
    else:
        return math.atan2(focus[1] - closestPoint[1], focus[0] - closestPoint[0])

tolerance = 0.000000000001
def rightSort(points):
    sorted = [ points[0] ]
    nextPoint = closest(sorted[-1], points)
    x = abs( sorted[-1][0] - nextPoint[0]) < tolerance
    popped = []
    del points[0]
    while len(points) > 0:
        ndxes = []
        if x:
            for ndx in range(len(points)):
                if abs(points[ndx][0] - sorted[-1][0]) < tolerance:
                    ndxes.append(ndx)
            if len(ndxes) == 0:
                popped.append(sorted.pop())
                x = False
            else:
                closestDist = abs(points[ndxes[0]][1] - sorted[-1][1])
                ndxClosest = ndxes[0]
                for ndx in ndxes[1:]:
                    if abs(points[ndx][1] - sorted[-1][1]) < closestDist:
                        ndxClosest = ndx
                sorted.append(points[ndxClosest])
                del points[ndxClosest]
                x = False
                if popped:
                    points += popped
                    popped = []
        else:
            for ndx in range(len(points)):
                if abs(points[ndx][1] - sorted[-1][1]) < tolerance:
                    ndxes.append(ndx)
            if len(ndxes) == 0:
                popped.append(sorted.pop())
                x = True
            else:
                closestDist = abs(points[ndxes[0]][0] - sorted[-1][0])
                ndxClosest = ndxes[0]
                for ndx in ndxes[1:]:
                    if abs(points[ndx][0] - sorted[-1][0]) < closestDist:
                        ndxClosest = ndx
                sorted.append(points[ndxClosest])
                del points[ndxClosest]
                x = True
                if popped:
                    points += popped
                    popped = []
    if popped:
        sorted += popped
    return sorted

def center(points):
    return ( sum(point[0] for point in points) / len(points),
                sum(point[1] for point in points) / len(points) )

def remotest(points):
    centerPoint = center(points)
    print( "center", centerPoint )
    remotestPoint = points[0]
    remotestDist = ( centerPoint[0] - remotestPoint[0] )**2 + ( centerPoint[1] - remotestPoint[1] )**2
    for point in points[1:]:
        dist = ( centerPoint[0] - point[0] )**2 + ( centerPoint[1] - point[1] )**2
        if dist > remotestDist:
            remotestDist = dist
            remotestPoint = point
    print( "remotest", remotestPoint )
    return remotestPoint

def squaredPolar(point, centerPoint):
    return ( math.atan2(point[1] - centerPoint[1], point[0] - centerPoint[0]),
            ( point[0] - centerPoint[0] )**2 + ( point[1] - centerPoint[1] )**2 )

def polarSort(points):
    centerPoint = center(points)
    presorted = []
    for point in points:
        presorted.append(( squaredPolar(point, centerPoint), point ))
    presorted.sort()
    sorted = []
    for point in presorted:
        sorted.append(point[1])
    return sorted
    
htmlFile = open("polygon.html", "w")
htmlFile.write("<html><body>")
htmlFile.write(genSVG(points))
htmlFile.write("</body></html>")
htmlFile.close()

angle = rotangle(points)
print( "angle", angle * 180 / math.pi )

htmlFile = open("rightgon.html", "w")
htmlFile.write("<html><body>")
htmlFile.write(genSVGover(rotate(rightSort(rotate(points, angle)), -angle), polarSort(points), center(points)))
htmlFile.write("</body></html>")
htmlFile.close()

htmlFile = open("polargon.html", "w")
htmlFile.write("<html><body>")
htmlFile.write(genSVG(polarSort(points)))
htmlFile.write("</body></html>")
htmlFile.close()

下图是未排序的点“多边形”。

<svg xmlns="http://www.w3.org/2000/svg" width="734.7774715252783" height="543.6442641567144" viewbox="65.60520541730344 -3.8540656494687013 800.3826769425817 539.7901985072457"><path fill="grey" d="M 156.40357183517773 23.19316100057085 L 83.97002318399646 188.27914171909507 L 518.4511031561435 60.897074118366035 L 799.3826769425817 214.44658030407507 L 304.1247347870089 -2.8540656494687013 L 593.7387174567936 199.93582818685073 L 773.3354502925422 66.72541735224387 L 625.6142873407109 92.7726440022834 L 428.65273673826925 127.50227953566946 L 379.41234908765887 136.184688419016 L 446.0175545049623 225.98305483689026 L 448.871620154431 530.1077896238992 L 509.768694272797 11.65668646775564 L 373.58400585378104 391.06903555541453 L 602.4211263401401 249.17621583746111 L 182.45079848521726 170.91432395240204 L 616.9318784573643 43.53225635167299 L 165.08598071852424 72.43354865118125 L 312.80714367035546 46.3863220011417 L 225.86284290194985 417.1162622054541 L 399.63123250382057 538.7901985072457 L 66.60520541730344 89.79836641787429 Z"/></svg>

下图是一个输出文件的渲染。它显示:

• 蓝点是(x，y)坐标的中心
• 红色多边形是极坐标排序的多边形
• 黑色多边形是直角排序多边形

<svg xmlns="http://www.w3.org/2000/svg" width="740.7774715252784" height="549.6442641567145" viewbox="62.60520541730345 -6.854065649468694 803.3826769425818 542.7901985072458"><path stroke="black" stroke-width="7" fill="none" d="M 156.40357183517776 23.19316100057085 L 165.08598071852424 72.43354865118125 L 66.60520541730345 89.7983664178743 L 83.97002318399647 188.2791417190951 L 182.4507984852173 170.91432395240207 L 225.86284290194988 417.1162622054542 L 373.5840058537811 391.0690355554146 L 399.63123250382057 538.7901985072458 L 448.87162015443107 530.1077896238993 L 379.41234908765887 136.184688419016 L 428.65273673826937 127.50227953566947 L 446.01755450496233 225.9830548368903 L 593.7387174567937 199.93582818685076 L 602.4211263401402 249.17621583746114 L 799.3826769425818 214.44658030407507 L 773.3354502925423 66.72541735224388 L 625.614287340711 92.7726440022834 L 616.9318784573644 43.532256351673 L 518.4511031561435 60.89707411836606 L 509.76869427279706 11.656686467755648 L 312.8071436703555 46.3863220011417 L 304.1247347870089 -2.8540656494686942 Z"/><path stroke="red" stroke-width="2" fill="none" d="M 182.45079848521726 170.91432395240204 L 182.45079848521726 170.91432395240204 L 66.60520541730344 89.79836641787429 L 165.08598071852424 72.43354865118125 L 156.40357183517773 23.19316100057085 L 379.41234908765887 136.184688419016 L 312.80714367035546 46.3863220011417 L 304.1247347870089 -2.8540656494687013 L 428.65273673826925 127.50227953566946 L 509.768694272797 11.65668646775564 L 518.4511031561435 60.897074118366035 L 616.9318784573643 43.53225635167299 L 625.6142873407109 92.7726440022834 L 773.3354502925422 66.72541735224387 L 799.3826769425817 214.44658030407507 L 593.7387174567936 199.93582818685073 L 602.4211263401401 249.17621583746111 L 446.0175545049623 225.98305483689026 L 448.871620154431 530.1077896238992 L 399.63123250382057 538.7901985072457 L 373.58400585378104 391.06903555541453 L 225.86284290194985 417.1162622054541 L 83.97002318399646 188.27914171909507 Z"/><circle fill="blue" cx="409.6874424591604" cy="177.00212769986794" r="7" /></svg>