Sweep and Prune

Try zooming and panning within the canvas as though it were a map. Overlapping quads are shaded.

This is the web demo for par_sprune.h. It performs sweep-and-prune with 500 bounding boxes using an emscripten web worker. D3 is used for camera control. Canvas2D is used for rendering.

The API is really simple. There's only one important function:

// Takes an array of 4-tuples (minx miny maxx maxy) and performs SaP. Optionally
// takes an existing context to avoid memory churn during animation.  Pass NULL
// for the third argument when calling for the first time.
par_sprune_context* par_sprune_overlap(float const* aabbs,
    int naabbs, par_sprune_context* previous);

This returns a structure that looks like this:

typedef struct {
    int const* const collision_pairs; // list of two-tuples
    int const ncollision_pairs;       // number of two-tuples
} par_sprune_context;

When you're done reading the data, use the provided free function:

void par_sprune_free_context(par_sprune_context* context);

That's it! The API also proffers a function for culling away overlapping boxes, which is potentially useful when drawing labels on a map. See the header file for details.