グリッド内の点の集合をカバーする最小のポリゴンを見つける

Question

まず、コードを要求していないので、私のアプローチについて明確にしたいだけです。

第2に、これが完全にSO関連でない場合、私は最も関連性の高いスタックエクスチェンジサイトに質問を移します。私はこれがグラフ理論に関連した問題だと確信しています。

だからグリッドで定義された点（0,0）

垂直/水平線との間の各交点を無限大グリッドを有するが（原点からの行数によって与えられる）別のポイントを定義します。

点集合(x,y)ここで、各x,yは整数です。点を囲む最小ポリゴンの周囲を返します。

制約：

• 点の数が100,000未満
• 点はポリゴンの境界上に位置することができないです。
• 多角形の辺は、グリッド内の垂直/水平線、または単一の正方形内の対角線にのみ対応できます。

私はGraph Theory関連の問題だと思います。トラベリングセールスマンのように、私はまず、最適な解を与えるアルゴリズムを使って、すべてのポイント間の最短経路を見つける必要があります。次に、ポイント間のグリッドに沿った最適なパスを見つけるために、各ポイント間で同じアルゴリズムを実行する必要があります。

私はTraveling Salesmanのために80の町が与えられたアルゴリズムを書いています。

この質問には100,000点があります。そのような膨大な数のノードを解決するアルゴリズムが存在するかどうかは疑問です。

別の方法がありますか？私はこれを間違った方法で考えていますか？

ありがとうございました！

Answer 1

Convex hullは、この問題を解決するために実際には必要ありません。

最も時間効率的convex hullアルゴリズムはn全体点の数であり、そしてhが船体上の点の数であるO(nlogh)、です。

上記のコメントを見て、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)