cg.locators — Locators

The cg.locators module provides ....

New in version 1.0.

Computational geometry code for PySAL: Python Spatial Analysis Library.

class pysal.cg.locators.BruteForcePointLocator(points)

A class which does naive linear search on a set of Point objects.

Methods

nearest
proximity
region

nearest(query_point)

Returns the nearest point indexed to a query point.

nearest(Point) -> Point

Parameters:query_point : a point to find the nearest indexed point to

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = BruteForcePointLocator(points)
>>> n = pl.nearest(Point((1, 1)))
>>> str(n)
'(0.0, 0.0)'

proximity(origin, r)

Returns the indexed points located within some distance of an origin point.

proximity(Point, number) -> Point list

Parameters:

origin : the point to find indexed points near

r : the maximum distance to find indexed point from the origin point

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = BruteForcePointLocator(points)
>>> neighs = pl.proximity(Point((1, 0)), 2)
>>> len(neighs)
1
>>> p = neighs[0]
>>> isinstance(p, Point)
True
>>> str(p)
'(0.0, 0.0)'

region(region_rect)

Returns the indexed points located inside a rectangular query region.

region(Rectangle) -> Point list

Parameters:region_rect : the rectangular range to find indexed points in

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = BruteForcePointLocator(points)
>>> pts = pl.region(Rectangle(-1, -1, 10, 10))
>>> len(pts)
3

class pysal.cg.locators.Grid(bounds, resolution)

Representation of a binning data structure.

Methods

add
bounds
in_grid
nearest
proximity
remove

add(item, pt)

Adds an item to the grid at a specified location.

add(x, Point) -> x

Parameters:

item – the item to insert into the grid :

pt – the location to insert the item at :

Examples

>>> g = Grid(Rectangle(0, 0, 10, 10), 1)
>>> g.add('A', Point((4.2, 8.7)))
'A'

bounds(bounds)

Returns a list of items found in the grid within the bounds specified.

bounds(Rectangle) -> x list

Parameters:

item : the item to remove from the grid

pt : the location the item was added at

Examples

>>> g = Grid(Rectangle(0, 0, 10, 10), 1)
>>> g.add('A', Point((1.0, 1.0)))
'A'
>>> g.add('B', Point((4.0, 4.0)))
'B'
>>> g.bounds(Rectangle(0, 0, 3, 3))
['A']
>>> g.bounds(Rectangle(2, 2, 5, 5))
['B']
>>> sorted(g.bounds(Rectangle(0, 0, 5, 5)))
['A', 'B']

in_grid(loc)

Returns whether a 2-tuple location _loc_ lies inside the grid bounds.

Test tag: <tc>#is#Grid.in_grid</tc>

nearest(pt)

Returns the nearest item to a point.

nearest(Point) -> x

Parameters:pt : the location to search near

Examples

>>> g = Grid(Rectangle(0, 0, 10, 10), 1)
>>> g.add('A', Point((1.0, 1.0)))
'A'
>>> g.add('B', Point((4.0, 4.0)))
'B'
>>> g.nearest(Point((2.0, 1.0)))
'A'
>>> g.nearest(Point((7.0, 5.0)))
'B'

proximity(pt, r)

Returns a list of items found in the grid within a specified distance of a point.

proximity(Point, number) -> x list

Parameters:

pt : the location to search around

r : the distance to search around the point

Examples

>>> g = Grid(Rectangle(0, 0, 10, 10), 1)
>>> g.add('A', Point((1.0, 1.0)))
'A'
>>> g.add('B', Point((4.0, 4.0)))
'B'
>>> g.proximity(Point((2.0, 1.0)), 2)
['A']
>>> g.proximity(Point((6.0, 5.0)), 3.0)
['B']
>>> sorted(g.proximity(Point((4.0, 1.0)), 4.0))
['A', 'B']

remove(item, pt)

Removes an item from the grid at a specified location.

remove(x, Point) -> x

Parameters:

item – the item to remove from the grid :

pt – the location the item was added at :

Examples

>>> g = Grid(Rectangle(0, 0, 10, 10), 1)
>>> g.add('A', Point((4.2, 8.7)))
'A'
>>> g.remove('A', Point((4.2, 8.7)))
'A'

class pysal.cg.locators.IntervalTree(intervals)

Representation of an interval tree. An interval tree is a data structure which is used to quickly determine which intervals in a set contain a value or overlap with a query interval.

Reference: de Berg, van Kreveld, Overmars, Schwarzkopf. Computational Geometry: Algorithms and Application. 212-217. Springer-Verlag, Berlin, 2000.

Methods

Node
query

class Node(val, left_list, right_list, left_node, right_node)

Private class representing a node in an interval tree.

Methods

add
query
remove

add(i)

Adds an interval to the IntervalTree node.

remove(i)

Removes an interval from the IntervalTree node.

IntervalTree.query(q)

Returns the intervals intersected by a value or interval.

query((number, number) or number) -> x list

Parameters:q : a value or interval to find intervals intersecting

Examples

>>> intervals = [(-1, 2, 'A'), (5, 9, 'B'), (3, 6, 'C')]
>>> it = IntervalTree(intervals)
>>> it.query((7, 14))
['B']
>>> it.query(1)
['A']

class pysal.cg.locators.PointLocator(points)

An abstract representation of a point indexing data structure.

Methods

nearest
proximity
region

nearest(query_point)

Returns the nearest point indexed to a query point.

nearest(Point) -> Point

Parameters:query_point : a point to find the nearest indexed point to

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = PointLocator(points)
>>> n = pl.nearest(Point((1, 1)))
>>> str(n)
'(0.0, 0.0)'

proximity(origin, r)

Returns the indexed points located within some distance of an origin point.

proximity(Point, number) -> Point list

Parameters:

origin : the point to find indexed points near

r : the maximum distance to find indexed point from the origin point

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = PointLocator(points)
>>> len(pl.proximity(Point((1, 0)), 2))
1

region(region_rect)

Returns the indexed points located inside a rectangular query region.

region(Rectangle) -> Point list

Parameters:region_rect : the rectangular range to find indexed points in

Examples

>>> points = [Point((0, 0)), Point((1, 6)), Point((5.4, 1.4))]
>>> pl = PointLocator(points)
>>> pts = pl.region(Rectangle(-1, -1, 10, 10))
>>> len(pts)
3

class pysal.cg.locators.PolygonLocator(polygons)

An abstract representation of a polygon indexing data structure.

Methods

nearest
proximity
region

nearest(query_point, rule='vertex')

Returns the nearest polygon indexed to a query point based on various rules.

nearest(Polygon) -> Polygon

Parameters:

query_point : a point to find the nearest indexed polygon to

rule : representative point for polygon in nearest query.

vertex – measures distance between vertices and query_point centroid – measures distance between centroid and query_point edge – measures the distance between edges and query_point

Examples

>>> p1 = Polygon([Point((0, 1)), Point((4, 5)), Point((5, 1))])
>>> p2 = Polygon([Point((3, 9)), Point((6, 7)), Point((1, 1))])
>>> pl = PolygonLocator([p1, p2])
>>> n = pl.nearest(Point((-1, 1)))
>>> str(min(n.vertices()))
(0.0, 1.0)

proximity(origin, r, rule='vertex')

Returns the indexed polygons located within some distance of an origin point based on various rules.

proximity(Polygon, number) -> Polygon list

Parameters:

origin : the point to find indexed polygons near

r : the maximum distance to find indexed polygon from the origin point

rule : representative point for polygon in nearest query.

vertex – measures distance between vertices and query_point centroid – measures distance between centroid and query_point edge – measures the distance between edges and query_point

Examples

>>> p1 = Polygon([Point((0, 1)), Point((4, 5)), Point((5, 1))])
>>> p2 = Polygon([Point((3, 9)), Point((6, 7)), Point((1, 1))])
>>> pl = PolygonLocator([p1, p2])
>>> len(pl.proximity(Point((0, 0)), 2))
2

region(region_rect)

Returns the indexed polygons located inside a rectangular query region.

region(Rectangle) -> Polygon list

Parameters:region_rect : the rectangular range to find indexed polygons in

Examples

>>> p1 = Polygon([Point((0, 1)), Point((4, 5)), Point((5, 1))])
>>> p2 = Polygon([Point((3, 9)), Point((6, 7)), Point((1, 1))])
>>> pl = PolygonLocator([p1, p2])
>>> n = pl.region(Rectangle(0, 0, 4, 10))
>>> len(n)
2