Shortest distance between surface points (Python)

vegaseat 3 2K Views

One way to find the shortest distance between a series of surface (x, y) points is to let Python module itertools find the non-repeating combinations of point pairs. Now you can apply the Pythagoras' theorem to find all the distances and the minimum distance.

''' distance_shortest101.py
use Python module itertools to get non-repeating combinations
of two points on a surface
calculate the shortest distance between the given surface points
tested with Python27 and Python33  by  vegaseat  30oct2013
'''

import itertools as it
import pprint

def distance_points(two_point_list):
    '''
    calculate distance between two points from the list
    of two point tuples
    return a list of (distance, (point1, point2)) tuples
    '''
    distance_p_list = []
    for p in two_point_list:
        #print(p)  # test
        px1 = p[0][0]
        px2 = p[1][0]
        py1 = p[0][1]
        py2 = p[1][1]
        #print(px1, py1, px2, py2)  # test
        # use Pythagoras' theorem
        distance = ((px1-px2)**2 + (py1-py2)**2)**0.5
        distance_p_list.append((distance, p))
    return distance_p_list

# create a series of surface (x, y) points
point_list = [
(1, 2),
(3, 5),
(4, 6),
(1.5, 7)
]

# make sets of 2 non-repeating points
two_point_list = list(it.combinations(point_list, 2))

print("Non-repeating point combinations:")
pprint.pprint(two_point_list)
print('-'*40)

distance_p_list = distance_points(two_point_list)

print("List of (distance, (point1, point2)) tuples:")
pprint.pprint(distance_p_list)
print('-'*40)

shortest_distance = min(distance_p_list)

# show result
sf = "The shortest distance is {:f} between points {}"
print(sf.format(shortest_distance[0],shortest_distance[1]))

''' result ...
Non-repeating point combinations:
[((1, 2), (3, 5)),
 ((1, 2), (4, 6)),
 ((1, 2), (1.5, 7)),
 ((3, 5), (4, 6)),
 ((3, 5), (1.5, 7)),
 ((4, 6), (1.5, 7))]
----------------------------------------
List of (distance, (point1, point2)) tuples:
[(3.605551275463989, ((1, 2), (3, 5))),
 (5.0, ((1, 2), (4, 6))),
 (5.024937810560445, ((1, 2), (1.5, 7))),
 (1.4142135623730951, ((3, 5), (4, 6))),
 (2.5, ((3, 5), (1.5, 7))),
 (2.692582403567252, ((4, 6), (1.5, 7)))]
----------------------------------------
The shortest distance is 1.414214 between points ((3, 5), (4, 6))
'''
Member Avatar for Gribouillis
Gribouillis 1,391 Programming Explorer

You can also use the key parameter in function min():

import itertools as it

point_list = [
    (1, 2),
    (3, 5),
    (4, 6),
    (1.5, 7),
]

def distance(pair):
    p, q = pair
    return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

print(min(it.combinations(point_list, 2), key = distance))

""" my output -->
((3, 5), (4, 6))
"""
Member Avatar for gerisam
gerisam 0 Newbie Poster

How can I amend the above code in python to solve the nearest neighbor algorithm ? In stead of having a combination of point only to find the mean, but starting at a Star_pt, find the nearest neighbour(min distance) between all the other points, remove the current point and make the nearest neighbour current etc...until end of list. And sum all the min. The code has been handy for my assignment but i can't just find the way to modify it in order to adapt the NNP algorithm. I am an absolute beginner in programming.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview