Nearest Neighbour Simulation

The above applet simulates the plane sweep algorithm to determine the nearest neighbours for each point.

The initial collection of black points are the test points to be processed. They need to be accessible in sorted order, in this case by their x coordinate value.

The red sweep line indicates the order of processing. When the sweep line encounters a black point it becomes the event point and is the trigger to perform some processing.

The green points are members of the active list, initially empty. It is this subset of points that is tested with the event point. After the event point has been processed, it is placed into the active list.

When the sweep line identifies an event point, its proximity to the members of the active list is checked. In this example we are testing for points within a certain radius - indicated by the blue semi-circle centred on the event point. Those points within the semi-circle are neighbours, indicated by a red line between the two points.

By maintaning the active list in sorted order by y value, only those points in the active list which have a y value between the y value of the event point +/- the radius of the test circle used to determine the neighbour relationship need be compared with the event point. This reduces the number of neighbour tests performed for the members of the active list.

The active points that are tested, but which fail the neighbour relationship are termed "false hits". These are indicated by a black line between the two points.

There is another grey sweep line, trailing the red one. This follows the sweep line at a constant distance being the threshold to delete points from the active list.

Cross Matching Demonstration