# Chamfer distance visualization in Python and JS

Exploring how Chamfer distance works in both Python and JS using dash.

Explore this project live at:

https://www.oliver-ernst.com/chamfer-viz

Example visualization.

## Explanation of Chamfer distance

1. Given two sets of points or shapes, usually referred to as Set A and Set B.
2. For each point in Set A, find the closest point in Set B and calculate the distance between them.
3. For each point in Set B, find the closest point in Set A and calculate the distance between them.
4. Sum up all these distances from steps 2 and 3 to obtain the Chamfer distance.

Mathematically, the Chamfer distance can be expressed as:

Chamfer distance = Σ(min(dist(A_i, B_j)) + Σ(min(dist(B_i, A_j)))


Where:

• A_i represents a point in Set A.
• B_j represents a point in Set B.
• dist(A_i, B_j) is the distance between point A_i and its closest point in Set B.
• dist(B_i, A_j) is the distance between point B_i and its closest point in Set A.

## Implementation

Chamfer distance uses a KDTree. A KDTree is a data structure that organizes points in a way that enables fast nearest-neighbor queries. Computing the structure for Set B makes it faster to find the nearest neighbors in Set B for each point in Set A (and vice versa).

The use of the KDTree data structure significantly speeds up the computation of nearest neighbors for each point in Sets A and B. Without KDTree, you would need to perform a brute-force search, which can be computationally expensive, especially for large point sets. KDTree organizes the points in a way that allows for efficient nearest-neighbor queries and is commonly used in computational geometry and various data science tasks.

It’s important to note that while KD-Trees offer efficient nearest neighbor and range search capabilities, their performance can degrade for very high-dimensional data (often referred to as the “curse of dimensionality”). In such cases, other data structures like ball trees or approximate nearest neighbor algorithms may be more suitable. Nevertheless, KD-Trees remain a valuable tool for solving a wide range of problems involving multi-dimensional data.

## Running

### Javascript

Navigate to the js directory and run using VSCode’s Live Server extension or any other web server of your choice. For example:

cd js
python -m http.server


### Python

Navigate to the python directory and install the requirements:

pip install -r requirements.txt


Then run the app:

python app.py


Optionally: specify the port with --port flag or debug mode with --debug flag.

Example visualization.

Example visualization.

## Live demo

See the live demo here: https://www.oliver-ernst.com/chamfer-viz

## References

Oliver K. Ernst
December 15, 2023