Repository files navigation

Trapezoidal Map library — a data structure for fast point location queries.

The problem of planar partitioning and planar point location is a fundamental problem in computational geometry. Given a partition of the plane into disjoint regions, in which region a does a query point lie?

TrapMap pre-processes a partitioning of the plane (given as individual line segments, or polygons), decomposing regions into simpler trapezoidal cells upon which a search structure (a directed acyclic graph) is constructed. This structure facilitates a search of the trapezoid (hence the region) containing a query point inO(log n) time. The trapezoidal map and the search structure are built via randomized incremental construction.

TrapMap is based onTyler Chenhall's trapezoidal mapimplementation. The library has been built for slight interoperability withProcessing; it accepts Processing'sPShape type as polygon input and can output trapezoids of the same type.

TrapMap is available as a Maven artifact viaJitpack.

Construct aTrapMap from a collection of line segments or a list ofPShape polygons. The trapezoidal map and the search structure are built upon instantiation. It can then be queried as follows:

• findNearestTrapezoid(x, y) — Locates the trapezoid which contains a query point.
  • If a query point does not lie inside any trapezoid, this method returns the nearest trapezoid to the point.
• findContainingTrapezoid(x, y) — Locates the trapezoid which contains a query point.
  • If the point does not lie inside any trapezoid, this method returns null.
• findFaceTrapezoids(x, y) — Finds the group of trapezoids that make up the polygonal face that contains a query point.
• findContainingPolygon(x, y) — Locates the polygon which contains a query point.
  • This method has a valid output only when theTrapMap is constructed from polygons.
• getAllTrapezoids() — Returns all the trapezoids contained in the trapezoid map.