Python: Ramer-Douglas-Peucker (RDP) Algorithmus mit der Anzahl der Punkte anstelle von Epsilon

Question

Ich möchte dieses folgende Python-Skript für RDP algorithm mit dem Ziel ändern, nicht mit Epsilon, sondern um die Anzahl der Punkte, die ich behalten möchte wählen beim Finale:

class DPAlgorithm(): 

    def distance(self, a, b): 
     return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) 

    def point_line_distance(self, point, start, end): 
     if (start == end): 
      return self.distance(point, start) 
     else: 
      n = abs(
       (end[0] - start[0]) * (start[1] - point[1]) - (start[0] - point[0]) * (end[1] - start[1]) 
      ) 
      d = sqrt(
       (end[0] - start[0]) ** 2 + (end[1] - start[1]) ** 2 
      ) 
      return n/d 

    def rdp(self, points, epsilon): 
     """ 
     Reduces a series of points to a simplified version that loses detail, but 
     maintains the general shape of the series. 
     """ 
     dmax = 0.0 
     index = 0 
     i=1 
     for i in range(1, len(points) - 1): 
      d = self.point_line_distance(points[i], points[0], points[-1]) 
      if d > dmax : 
       index = i 
       dmax = d 

     if dmax >= epsilon : 
      results = self.rdp(points[:index+1], epsilon)[:-1] + self.rdp(points[index:], epsilon) 
     else: 
      results = [points[0], points[-1]] 
     return results 

fand ich einen Java-Skript in diesem Sinne: https://gist.github.com/msbarry/9152218

Kennt jemand eine Version für Python 3.X?

Dank momow

Answer 1

Portieren JS-Code aus dem obigen Link Python zu [2.7]:

# -*- coding: utf-8 -*- 

import math 
import time 


def timenow(): 
    return int(time.time() * 1000) 

def sqr(x): 
    return x*x 

def distSquared(p1, p2): 
    return sqr(p1[0] - p2[0]) + sqr(p1[1] - p2[1]) 

class Line(object): 
    def __init__(self, p1, p2): 
     self.p1 = p1 
     self.p2 = p2 
     self.lengthSquared = distSquared(self.p1, self.p2) 

    def getRatio(self, point): 
     segmentLength = self.lengthSquared 
     if segmentLength == 0: 
      return distSquared(point, p1); 
     return ((point[0] - self.p1[0]) * (self.p2[0] - self.p1[0]) + \ 
     (point[1] - self.p1[1]) * (self.p2[1] - self.p1[1]))/segmentLength 

    def distanceToSquared(self, point): 
     t = self.getRatio(point) 

     if t < 0: 
      return distSquared(point, self.p1) 
     if t > 1: 
      return distSquared(point, self.p2) 

     return distSquared(point, [ 
      self.p1[0] + t * (self.p2[0] - self.p1[0]), 
      self.p1[1] + t * (self.p2[1] - self.p1[1]) 
     ]) 

    def distanceTo(self, point): 
     return math.sqrt(self.distanceToSquared(point)) 


def simplifyDouglasPeucker(points, pointsToKeep): 
    weights = [] 
    length = len(points) 

    def douglasPeucker(start, end): 
     if (end > start + 1): 
      line = Line(points[start], points[end]) 
      maxDist = -1 
      maxDistIndex = 0 

      for i in range(start + 1, end): 
       dist = line.distanceToSquared(points[i]) 
       if dist > maxDist: 
        maxDist = dist 
        maxDistIndex = i 

      weights.insert(maxDistIndex, maxDist) 

      douglasPeucker(start, maxDistIndex) 
      douglasPeucker(maxDistIndex, end) 

    douglasPeucker(0, length - 1) 
    weights.insert(0, float("inf")) 
    weights.append(float("inf")) 

    weightsDescending = weights 
    weightsDescending = sorted(weightsDescending, reverse=True) 

    maxTolerance = weightsDescending[pointsToKeep - 1] 
    result = [ 
     point for i, point in enumerate(points) if weights[i] >= maxTolerance 
    ] 

    return result