ST_FrechetDistance#

Table of Contents#

  1. What is ST_FrechetDistance

  2. ST_FrechetDistance Input Data

  3. Using ST_FrechetDistance

[2]:
import bdt
bdt.auth("../bdt.lic")
import bdt.functions as F
BDT has been successfully authorized!

            Welcome to
             ___    _                ___         __             ______             __   __     _   __
            / _ )  (_)  ___ _       / _ \ ___ _ / /_ ___ _     /_  __/ ___  ___   / /  / /__  (_) / /_
           / _  | / /  / _ `/      / // // _ `// __// _ `/      / /   / _ \/ _ \ / /  /  '_/ / / / __/
          /____/ /_/   \_, /      /____/ \_,_/ \__/ \_,_/      /_/    \___/\___//_/  /_/\_\ /_/  \__/
                      /___/

BDT python version: v3.4.0-53-processing-2024-11-g76e56d0a
BDT jar version: v3.4.0-53-processing-2024-11-g76e56d0a

Part 1: What is ST_FrechetDistance#

ST_FrechetDistance is a function that calculates the discrete Frechet distance between two multi-vertex geometries. It provides a measure of similarity between the two geometries that takes into account the location and ordering of the points that make up each geometry.

This metric can be best illustrated by this analogy:

“Imagine a person traversing a finite curved path while walking their dog on a leash, with the dog traversing a separate finite curved path. Each can vary their speed to keep slack in the leash, but neither can move backwards. The Fréchet distance between the two curves is the length of the shortest leash sufficient for both to traverse their separate paths from start to finish.”

For more details about how this is calculated see this paper.

Overview of frechet distance

Part 2: ST_FrechetDistance Input Data#

Input geometries must be multi-vertex. This includes, polylines, polygons, and multipoints.

[9]:
geom1_wkt = "LINESTRING (0.0 0.0, 2.0 0.0)"
geom2_wkt = "LINESTRING (0.0 1.0, 1.0 1.0, 2.0 2.0)"

df = spark.sql(f"""
    SELECT
        ST_FromText('{geom1_wkt}') AS SHAPE1,
        ST_FromText('{geom2_wkt}') AS SHAPE2
    """)

df.show()
+--------------------+--------------------+
|              SHAPE1|              SHAPE2|
+--------------------+--------------------+
|{[01 05 00 00 00 ...|{[01 05 00 00 00 ...|
+--------------------+--------------------+

frechet distance input data

Part 3: Using ST_FrechetDistance#

[10]:
dist_df = (
    df.select(
        F.st_frechet_distance("SHAPE1", "SHAPE2").alias("dist")
    )
)
dist_df.show()
+----+
|dist|
+----+
| 2.0|
+----+

frechet distance result