lq

README

golq : 2D Locality Queries

2D locality queries in Go

This utility is a spatial database which stores objects each of which is associated with a 2D point (a location in a 2D space). The points serve as the search key for the associated object. It is intended to efficiently answer circle inclusion queries, also known as range queries, basically questions like:

Which objects are within a radius R of the location L?

In this context, efficiently means significantly faster than the naive, brute force O(n) testing of all known points. Additionally it is assumed that the objects move along unpredictable paths, so that extensive preprocessing (for example, constructing a Delaunay triangulation of the point set) may not be practical.

The implementation is a bin lattice: a 2D rectangular array of brick-shaped (rectangles) regions of space. Each region is represented by a pointer to a (possibly empty) doubly-linked list of objects. All of these sub-bricks are the same size. All bricks are aligned with the global coordinate axes.

Usage example

TODO

Benchmarks

This logarithmic scale plot shows the numbers obtained in the following benchmarks. The brute-force method computes squared distances between every object and the randomly chosen search query point. It doesn't even include the additional time that would be taken to sort them in order to extract the nearest (or K nearest).

BenchmarkBruteForce10-2                          2000000               819 ns/op
BenchmarkBruteForce50-2                           500000              3570 ns/op
BenchmarkBruteForce100-2                          200000              6958 ns/op
BenchmarkBruteForce200-2                          100000             13564 ns/op
BenchmarkBruteForce500-2                           50000             33037 ns/op
BenchmarkBruteForce1000-2                          20000             66053 ns/op
BenchmarkNearestNeighbourLq10Radius2-2           3000000               546 ns/op
BenchmarkNearestNeighbourLq50Radius2-2           2000000               788 ns/op
BenchmarkNearestNeighbourLq100Radius2-2          1000000              1025 ns/op
BenchmarkNearestNeighbourLq200Radius2-2          1000000              1434 ns/op
BenchmarkNearestNeighbourLq500Radius2-2           500000              2431 ns/op
BenchmarkNearestNeighbourLq1000Radius2-2          300000              4242 ns/op
BenchmarkNearestNeighbourLq10Radius4-2           2000000               987 ns/op
BenchmarkNearestNeighbourLq50Radius4-2           1000000              1480 ns/op
BenchmarkNearestNeighbourLq100Radius4-2          1000000              1985 ns/op
BenchmarkNearestNeighbourLq200Radius4-2           500000              2974 ns/op
BenchmarkNearestNeighbourLq500Radius4-2           300000              5427 ns/op
BenchmarkNearestNeighbourLq1000Radius4-2          200000              9927 ns/op
BenchmarkObjectsInLocalityLq10Radius2-2          3000000               410 ns/op
BenchmarkObjectsInLocalityLq50Radius2-2          3000000               570 ns/op
BenchmarkObjectsInLocalityLq100Radius2-2         2000000               731 ns/op
BenchmarkObjectsInLocalityLq200Radius2-2         1000000              1051 ns/op
BenchmarkObjectsInLocalityLq500Radius2-2         1000000              1854 ns/op
BenchmarkObjectsInLocalityLq1000Radius2-2         500000              3418 ns/op
BenchmarkObjectsInLocalityLq10Radius4-2          2000000               808 ns/op
BenchmarkObjectsInLocalityLq50Radius4-2          1000000              1102 ns/op
BenchmarkObjectsInLocalityLq100Radius4-2         1000000              1440 ns/op
BenchmarkObjectsInLocalityLq200Radius4-2         1000000              2169 ns/op
BenchmarkObjectsInLocalityLq500Radius4-2          300000              4000 ns/op
BenchmarkObjectsInLocalityLq1000Radius4-2         200000              7881 ns/op
PASS
ok      github.com/arl/golq        53.587s

Credits

This library is loosely inspired by the C language lq utility in OpenSteer.

License

• MIT License

Documentation

Overview

Package lq implements a spatial database which stores objects each of which is associated with a 2D point (a location in a 2D space). The points serve as the "search key" for the associated object. It is intended to efficiently answer "circle inclusion" queries, also known as "range queries": basically questions like:

Which objects are within a radius R of the location L?

In this context, "efficiently" means significantly faster than the naive, brute force O(n) testing of all known points. Additionally it is assumed that the objects move along unpredictable paths, so that extensive preprocessing (for example, constructing a Delaunay triangulation of the point set) may not be practical.

The implementation is a "bin lattice": a 2D rectangular array of brick-shaped (rectangles) regions of space. Each region is represented by a pointer to a (possibly empty) doubly-linked list of objects. All of these sub-bricks are the same size. All bricks are aligned with the global coordinate axes.

Terminology used here: the region of space associated with a bin is called a sub-brick. The collection of all sub-bricks is called the super-brick. The super-brick should be specified to surround the region of space in which (almost) all the key-points will exist. If key-points move outside the super-brick everything will continue to work, but without the speed advantage provided by the spatial subdivision. For more details about how to specify the super-brick's position, size and subdivisions see NewDB below.

Overview of usage: an application using this facility to perform locality queries over objects of type myStruct would first create a database with:

db := NewDB[myObject]()

Then, call Attach for each objects to attach to the database. Attach returns a 'proxy' object, which is a link between the user object and its representation in the locality database.

p := db.Attach(obj)

When a client object moves, the application calls Update with the new location. Update is a method of the lq.Proxy object, that's why the the proxy object is generally kept within the user object, though it can be managed separately:

db.Update(123, 456)

To perform a query, DB.ForEachWithinRadius is passed a user function which will be called for all client objects in the locality. See Func below for more detail.

func myFunc(obj T, sqDist float64) {
    // do something with obj
}
DB.ForEachWithinRadius(x, y, radius, myFunc, nil)

The DB.FindNearestInRadius function can be used to find a single nearest neighbor using the database. Note that "locality query" is also known as neighborhood query, neighborhood search, near neighbor search, and range query.

Author: Aurélien Rainone

Based on original work of: Craig Reynolds

Index

• type DB
  • func NewDB[T comparable](xorg, yorg, xsize, ysize float64, xdiv, divy int) *DB[T]
  • func (db *DB[T]) Attach(t T, x, y float64) *Proxy[T]
  • func (db *DB[T]) Detach(obj *Proxy[T])
  • func (db *DB[T]) DetachAll()
  • func (db *DB[T]) FindNearestInRadius(x, y, radius float64, ignored T) (T, bool)
  • func (db *DB[T]) ForEachObject(f Func[T])
  • func (db *DB[T]) ForEachWithinRadius(x, y, radius float64, f Func[T])
  • func (db *DB[T]) Update(obj *Proxy[T], x, y float64)
• type Func
• type Proxy

Types

type DB

type DB[T comparable] struct {
	// contains filtered or unexported fields
}

DB represents the spatial database.

Typically one of these would be created (by a call to DB.NewDB) for a given application.

func NewDB

func NewDB[T comparable](xorg, yorg, xsize, ysize float64, xdiv, divy int) *DB[T]

NewDB creates a new database, allocates the bin array, and returns the DB object.

The six parameters define the properties of the 'super-brick':

• xorg/yorg: x/y coordinates of one corner of the super-brick, its minimum x and y extent.
• xsize/ysize: the width and height of the super-brick.
• xdiv/ydiv: the number of subdivisions (sub-bricks) along each axis.

func (*DB[T]) Attach

func (db *DB[T]) Attach(t T, x, y float64) *Proxy[T]

Attach attaches a new object to the database and returns a proxy object.

func (*DB[T]) Detach

func (db *DB[T]) Detach(obj *Proxy[T])

Detach detaches the given proxy object from the database.

func (*DB[T]) DetachAll

func (db *DB[T]) DetachAll()

DetachAll detaches all proxy objects from the database.

func (*DB[T]) FindNearestInRadius

func (db *DB[T]) FindNearestInRadius(x, y, radius float64, ignored T) (T, bool)

FindNearestInRadius searches the database to find the object whose key-point is nearest to a given location yet within a given radius.

That is, it finds the object (if any) within a given search circle which is nearest to the circle's center. The ignored argument can be used to exclude an object from consideration. This is useful when looking for the nearest neighbor of an object in the database, since otherwise it would be its own nearest neighbor. The function returns the nearest object and true, or if there was no object with the provided radius, it returns the zero value of T, and false.

func (*DB[T]) ForEachObject

func (db *DB[T]) ForEachObject(f Func[T])

ForEachObject applies a user-supplied function to all objects in the database, regardless of locality (see DB.ForEachWithinRadius). Since there's no search locality, the squared distance argument to f is undefined.

func (*DB[T]) ForEachWithinRadius

func (db *DB[T]) ForEachWithinRadius(x, y, radius float64, f Func[T])

ForEachWithinRadius applies an application-specific ObjectFunc to all objects in a certain locality.

The locality is specified as a circle with a given center and radius. All objects whose location (key-point) is within this circle are identified and the f ObjectFunc function is applied to them. This method uses the lq database to quickly reject any objects in bins which do not overlap with the circle of interest. Incremental calculation of index values is used to efficiently traverse the bins of interest.

func (*DB[T]) Update

func (db *DB[T]) Update(obj *Proxy[T], x, y float64)

Update updates the location of a proxy object in the database.

It should be called for each client object every time its location changes. For example, in an animation application, this would be called each frame for every moving object.

type Func

type Func[T any] func(obj T, sqDist float64)

Func is the function called, for each proxy object, when iterating over a set of proxies. Func gets called with the object in question and the squared distance from the center of the search locality circle (x,y) to the object's key-point (when applicable).

type Proxy

type Proxy[T any] struct {
	// contains filtered or unexported fields
}

Proxy is a proxy for a client (application) object in the spatial database.

One of these should be created for each client object. This might be included within the structure of a client object, or could be allocated separately.