Python implementation of the Ramer-Douglas-Peucker Algorithm

I recently implemented the RDP polygon approximation algorithm in Python and I'm skeptical of whether or not I implemented it correctly of with the greatest efficiency. The algorithm runs in around 0.0003 seconds for a polygon with 30 points on my computer (an Intel Core i5 with 3.8 GHz of RAM), so I'm worried about how it may run on a slower computer. Also, there seems to be a cap as to the number of points that can be removed by the algorithm, or at least there's a cap in my implementation. No matter how high I set the tolerance, the approximation always caps at about \$\frac{2N}{3}\$ points where \$N\$ is the number of points in the input polygon. Could I be doing something wrong?

```
NegInf = float('-inf')

def distance(v1, v2):
"""
Calculate the distance between two points.

PARAMETERS
==========
v1, v2 >> The first and second vertices respectively.
"""
dx = v2[0] - v1[0]
dy = v2[1] - v1[1]
return math.sqrt(dxdx + dydy)

def perpendicular_distance(point, line_start, line_end):
"""
Calculate the perpendicular distance from a point to a line.

PARAMETERS
==========
point >> The point of which to calculate the distance from the line
(must be an (x, y) tuple).

line_start, line_end >> Start and end points defining the line respectively
(must each be an (x, y) tuple).
"""
x1, y1 = line_start
x2, y2 = line_end
vx, vy = point
if x1 == x2:
return abs(x1 - vx)
m = (y2 - y1)/(x2 - x1)
b = y1 - m*x1
return abs(m vx - vy + b)/math.sqrt(mm + 1)

def _rdp_approx(points, tolerance, depth):
"""
Internal Function: Recursively perform the RDP algorithm.
"""
if not points:
# In case the furthest point index discovered is equal to the length of the
# list of points, leading to points[furthest:] sending in an empty list.
return []
elif len(points) max_dist:
max_dist = dist

If you want to calculate the farthest point you don't need to use the square root for 'real' distance calculation. Since you only need the distance for comparison and not the actual distance it is totally sufficient to compare by xx + yy instead of sqrt(xx + yy)

StackExchange Code Review Q#49809, answer score: 8