Chamfer Distance Between Point Sets | Dataford Interview Questions

Amazon Development Center U.S. may compare two 2D point clouds produced by different perception or imaging pipelines. Implement the symmetric Chamfer distance between the point sets.

For every point in set A, find the Euclidean distance to its nearest point in B. Average these distances. Repeat in the opposite direction, then return the average of the two directional distances.

Formal Specification

Implement chamfer_distance(A, B), where A and B are non-empty lists of 2D points. Each point is represented as a two-element list or tuple [x, y], and coordinates are integers or floats. Return a floating-point number:

0.5 * (average nearest distance from A to B + average nearest distance from B to A)

The result should be accurate within 1e-6.

Constraints

1 <= len(A), len(B) <= 2,000
Each point has exactly two coordinates
-10^6 <= x, y <= 10^6
Duplicate points are allowed
The result must be accurate within 1e-6

Function Signature

def chamfer_distance(A, B):

Your question is Chamfer Distance Between Point Sets. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem