Finding smallest polygon covering a set of points in a grid

Question

Firstly, I'm not asking for code, I just want clarification about my approach.

Secondly, if this isn't totally SO related, I will move the question to the most relevant Stack Exchange site. I'm pretty sure this is a graph theory related problem.

So I have an infinitely large grid with a defined point (0,0)

Each intersection between horizontal/vertical lines in the grid defines another point (given by the number of lines from the origin).

Given a set of points (x,y) where each x,y is an Integer: return the perimeter of the smallest polygon surrounding the points.

Constraints:

• The number of points is less than 100,000
• The points cannot lie on the perimeter of the polygon.
• The sides of the polygon can only correspond to vertical/horizontal lines in the grid, or a diagonal line in a single square.

My guess that the is a Graph Theory related problem. Just like the Travelling Salesman, I first need to find the shortest path between all points using an algorithm which gives an optimal solution. Then I need to perform the same algorithm between each point to find the optimal path along the grid between the points.

I have written an algorithm for the Travelling Salesman given 80 towns.

In this question there can be 100,000 points. So that makes me wonder if a possible algorithm even exists to solve such a huge number of Nodes.

Is there another approach. Am I thinking about this the wrong way?

Thanks for any help!

Answer 1

The Convex hull is not actually necessary to solve this problem.

The most time efficient convex hull algorithm is O(nlogh), where n is the number of points overall, and h is the number of points on the hull.

Looking through the comments above, m69 nailed it! The algorithm he describes (with a bit extra on top) can be achieved in O(n) time. Scrap the Convex Hull idea!!

• Draw the minimum square such that it surrounds all the points given. This is done using max & min on the list of points
• For each corner in the square, draw the allowed diagonal line which is closest to the most outer point. This is done by looping through the points and using the euclidean perpendicular distance formula. This is O(n)
• Using the intersections between the original square and the diagonal lines, calculate the overall perimeter of the polygon.

Here is my version of the algorithm (written in python). People are free to comment or optimise it if they wish. It was a fun problem to solve.

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)