The longest path between two points from the array

Question

I have a code that, using the algorithm of rotating calipers, defines two points with the longest distance.

The code takes in the first line the number of points N. And then N times takes the coordinates of the points X, Y. After displays the length of the longest distance.

For example:

INPUT
6
1 1
-1 0
-3 -1
-2 -2
2 3
4 -2

OUTPUT
7.0710678119

INPUT
6
2 2
0 -3
5 7
3 3
2 1
-1 1

OUTPUT
4.47213595499958 #my comment: from (3,3) to (5,7)

But there may be cases when 3 or more points are located on one straight line. And then how should I act?

from math import *

def rast(x1, x2, y1, y2):
        x = x2-x1
        y = y2-y1
        l = sqrt(pow(fabs(x), 2)+pow(fabs(y), 2));
        return l

def orientation(p,q,r):
    '''Return positive if p-q-r are clockwise, neg if ccw, zero if colinear.'''
    return (q[1]-p[1])*(r[0]-p[0]) - (q[0]-p[0])*(r[1]-p[1])

def hulls(Points):
    '''Graham scan to find upper and lower convex hulls of a set of 2d points.'''
    U = []
    L = []
    Points.sort()
    for p in Points:
        while len(U) > 1 and orientation(U[-2],U[-1],p) <= 0: U.pop()
        while len(L) > 1 and orientation(L[-2],L[-1],p) >= 0: L.pop()
        U.append(p)
        L.append(p)
    return U,L

def rotatingCalipers(Points):
    '''Given a list of 2d points, finds all ways of sandwiching the points
between two parallel lines that touch one point each, and yields the sequence
of pairs of points touched by each pair of lines.'''
    U,L = hulls(Points)
    i = 0
    j = len(L) - 1
    while i < len(U) - 1 or j > 0:
        yield U[i],L[j]

        # if all the way through one side of hull, advance the other side
        if i == len(U) - 1: j -= 1
        elif j == 0: i += 1

        # still points left on both lists, compare slopes of next hull edges
        # being careful to avoid divide-by-zero in slope calculation
        elif (U[i+1][1]-U[i][1])*(L[j][0]-L[j-1][0]) > \
                (L[j][1]-L[j-1][1])*(U[i+1][0]-U[i][0]):
            i += 1
        else: j -= 1

def diameter(Points):
    '''Given a list of 2d points, returns the pair that's farthest apart.'''
    diam,pair = max([((p[0]-q[0])**2 + (p[1]-q[1])**2, (p,q))
                     for p,q in rotatingCalipers(Points)])
    return pair

n=int(input())
dots = []
for i in range(n):
    tmp = [int(j) for j in input().split()]
    dots.append([tmp[0],tmp[1]])
tmp = diameter(dots)
d1,d2=tmp[0],tmp[1]
print(rast(d1[0],d2[0],d1[1],d2[1]))

Answer 1

Once you have made the convex hull, you will need to sort the lines by the longest. In my example you will have the red line and after this the blue with arrow.

Take the longest line (red) and get its angle. Foreach point in the convex hull, check if the line between S and P is equal to the angle. If so calculate the distance of both lines SP & EP, if one is longer than the blue line, that is the longest line, you can stop. Else, ignore the red line and take the next longest. When there are no equal angles, you can stop.