Cross Match Simulation

The above applet simulates the plane sweep algorithm to perform cross matching between two collections of points.

The different point sets are coloured red and black: the red points are tested against the black points. The points need to be accessible in sorted order, in this case by their x coordinate value.

The two gray sweep lines indicate the bounds for the active list.

As the first gray line passes over a black point, it is included into the active list, indicated by changing its colour from black to green. When the second gray sweep line passes over a green active point, it is removed from the active list. This ensures the active list remains a manageble size.

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

For cross matching, this processing is to test the event point's proximity to the members of the active list. Testing is performed in two stages. First, check the y coordinate value of the active points as being within the radius of the test circle relative to the event point's y coordinate value. This reduces the number of full proximity tests to be performed.

Only those green points within the blue "bounds" are tested as being a cross match. Those within the blue circle are a cross match, indicated by a red line between the two points. Those outside the blue circle are not a cross match, indicated by a black line between the two points (these are termed "false hits").

Nearest Neighbour Demonstration