Last active
December 29, 2023 08:55
-
-
Save sunng87/f4a3b06e77d80f30ddbe8fe034fa3da3 to your computer and use it in GitHub Desktop.
Greptimedb script for Ramer–Douglas–Peucker algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math | |
@coprocessor( | |
returns=["lon", "lat"], | |
) | |
def simplify(**params) -> (vector[f64], vector[f64]): | |
from greptime import query | |
results = query().sql(params["sql"]) | |
lon = results[0] | |
lat = results[1] | |
e = float(params["e"]) | |
line = list(zip(lon, lat)) | |
simplified_line = rdp(line, e) | |
result = list(zip(*simplified_line)) | |
return list(result[0]), list(result[1]) | |
def rdp(line, epsilon): | |
start_idx = 0 | |
end_idx = len(line) - 1 | |
max_dist = 0 # var to store furthest point dist | |
max_id = 0 # var to store furthest point index | |
for i in range(start_idx + 1, end_idx): | |
d = perpendicular_distance(line[i], line[start_idx], line[end_idx]) | |
if d > max_dist: | |
max_dist = d # overwrite max distance | |
max_id = i # overwrite max index | |
if max_dist > epsilon: | |
l = rdp(line[start_idx : max_id + 1], epsilon) | |
r = rdp(line[max_id:], epsilon) | |
results = l[:-1] | |
results.extend(r) | |
return results | |
else: | |
return [line[0], line[end_idx]] | |
def perpendicular_distance(point, start, end): | |
m = (end[1] - start[1]) / (end[0] - start[0]) | |
b = start[1] - m * start[0] # plug in either start or end | |
a = m | |
b = -1 | |
c = b | |
d = abs(a * point[0] + b * point[1] + c) / math.sqrt( | |
a**2 + b**2 | |
) # formula line - point distance | |
return d |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
rdp.py
curl --data-binary "@rdp.py" -XPOST "http://localhost:4000/v1/scripts?name=rdp&db=public"
curl -v -XPOST "http://localhost:4000/v1/run-script?db=public&name=rdp&sql=select%20lon%2Clat%20from%20waypoints%3B&e=4"
, arguments explained:sql
: a sql statement that will return two columnslon
andlat
e
: theepsilon
in RDP algorithm