algorithm - 查找覆盖网格中一组点的最小多边形

Question

首先，我不是要代码，我只是想澄清一下我的方法。

其次，如果这不是完全相关，我会将问题移至最相关的 Stack Exchange 站点。我很确定这是一个与图论相关的问题。

所以我有一个无限大的网格，其中有一个定义点 (0,0)

网格中水平/垂直线之间的每个交点都定义了另一个点(由距原点的线数给出)。

给定一组点 (x,y)，其中每个 x,y 都是一个整数:返回围绕这些点的最小多边形的周长。

约束:

• 积分数小于10万
• 点不能位于多边形的周长上。
• 多边形的边只能对应于网格中的垂直/水平线，或单个正方形中的对角线。

我猜这是一个图论相关的问题。就像旅行商一样，我首先需要使用给出最优解的算法找到所有点之间的最短路径。然后我需要在每个点之间执行相同的算法以找到沿着点之间网格的最佳路径。

我已经为给定 80 个城镇的旅行商编写了一个算法。

这道题可以有100,000分。所以这让我想知道是否存在一种可能的算法来解决如此庞大数量的节点。

还有其他方法吗？我是不是想错了？

感谢您的帮助!

Answer 1

Convex hull 实际上并不是解决这个问题所必需的。

时间效率最高的convex hull算法是O(nlogh)，其中n是整体的点数， h 是船体上的点数。

看了上面的评论，m69 搞定了!他描述的算法(顶部有一点额外)可以在 O(n) 时间内实现。废弃 Convex Hull 想法!!

• 画出包围所有给定点的最小正方形。这是使用点列表上的最大值和最小值完成的
• 对于正方形中的每个角，绘制最接近最外点的允许对角线。这是通过遍历点并使用欧氏垂直距离公式来完成的。这是O(n)
• 使用原始正方形和对角线之间的交点，计算多边形的总周长。

这是我的算法版本(用 Python 编写)。人们可以根据需要自由评论或优化它。这是一个有趣的问题。

from math import *
N = int(raw_input())
pts = []

for i in xrange(N):
    p1,p2 = map(int, raw_input().split(' '))
    pts.append((p1,p2))

def isBetween(a, b, c):
    ab = sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
    ac = sqrt((a[0]-c[0])**2 + (a[1]-c[1])**2)
    bc = sqrt((b[0]-c[0])**2 + (b[1]-c[1])**2)
    return abs(ac + bc - ab) < 0.01  # epsilon precision, needs < 1 in grid case

def getPoints(c):

    lines = [(-1, c[0][1]+c[0][0]),(1, c[1][1]-c[1][0]),(-1,c[2][1]+c[2][0]),(1,c[3][1]-c[3][0])]
    maxes = [[0,0],[0,0],[0,0],[0,0]]

    for count, line in enumerate(lines):

        pdist = (abs(line[0]*CH[0][0] - CH[0][1] + line[1]))/(sqrt((line[0]*line[0]) + 1 ))
        maxes[count][0] = pdist
        maxes[count][1] = CH[0]

    for elem in CH[1:]:

        for count, line in enumerate(lines):

            pdist = (abs(line[0]*elem[0] - elem[1] + line[1]))/(sqrt((line[0]*line[0]) + 1 ))
            if pdist < maxes[count][0]: 
                maxes[count][0] = pdist
                maxes[count][1] = elem

    for greg in range(4):
        maxes[greg][1] = list(maxes[greg][1])

    maxes[0][1][0] -=1
    maxes[1][1][0] +=1
    maxes[2][1][0] +=1
    maxes[3][1][0] -=1

    gregarr = []

    for i in range(4):

        y = lines[i][0]*(c[i][0]-maxes[i][1][0]) + maxes[i][1][1]
        cornerdist = abs(c[i][1] - y)

        if i == 0:
            gregarr.append((c[i][0], c[i][1]+cornerdist))
            gregarr.append((c[i][0]+cornerdist, c[i][1]))
        elif i == 1:
            gregarr.append((c[i][0]-cornerdist, c[i][1]))
            gregarr.append((c[i][0], c[i][1]+cornerdist))
        elif i == 2:
            gregarr.append((c[i][0], c[i][1]-cornerdist))
            gregarr.append((c[i][0]-cornerdist, c[i][1]))
        else:
            gregarr.append((c[i][0]+cornerdist, c[i][1]))
            gregarr.append((c[i][0], c[i][1]-cornerdist))

    return gregarr

def distance(p0, p1):

    return ((p0[0] - p1[0])*(p0[0] - p1[0]) + (p0[1] - p1[1])*(p0[1] - p1[1]))**(0.5)

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if not (x in seen or seen_add(x))]

CH = pts
H = len(CH)

if H == 0:
    print('0.000')
elif H == 1:
    print('5.656')
else:
    per = 0
    minx = min(CH, key = lambda x: x[0])[0]-1
    miny = min(CH, key = lambda x: x[1])[1]-1
    maxx = max(CH, key = lambda x: x[0])[0]+1
    maxy = max(CH, key = lambda x: x[1])[1]+1
    corners = [(minx,miny),(maxx, miny),(maxx,maxy),(minx,maxy)]
    arr = getPoints(corners)
    arr = f7(arr)
    arr.append(arr[0])
    T = len(arr)

    for i in range(1,T):

        per += distance(arr[i-1], arr[i])

    print(per)