找到覆盖网格中一组点的最小多边形

Question

首先,我不是要求代码,我只想澄清我的方法.

其次,如果这不完全与SO相关,我会将问题转移到最相关的Stack Exchange站点.我很确定这是一个图论相关的问题.

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

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

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

约束:

• 积分数小于100,000
• 这些点不能位于多边形的周长上.
• 多边形的边可以仅对应于网格中的垂直/水平线,或者对应于单个正方形中的对角线.

我猜这是一个与图论相关的问题.就像旅行推销员一样,我首先需要使用提供最佳解决方案的算法找到所有点之间的最短路径.然后我需要在每个点之间执行相同的算法,以找到点之间沿网格的最佳路径.

我为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)