Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Kirkpatrick's Algorithm for Log(n) point location in planar subdivisions.
Python
branch: master

README.md

point-location

Kirkpatrick's Algorithm for Log(n) point location in planar subdivisions. The original paper is freely available as [Kirkpatrick 83], with a more accessible walkthrough available here.

Usage

An example can be found in PointLocation.ipynb.

All shape primitives (including points and polygons) can be found in geo.shapes, while the implementation of Kirkpatrick's Algorithm is in kirkpatrick.

from geo.generator import randomConvexTiling, randomPoint
from kirkpatrick import Locator

# generate a convex subdivison
subdivision = randomConcaveTiling(randomConvexPolygon(100))

# run Kirkpatrick's
locator = Locator(subdivision)
point = randomPoint()
region = locator.locate(point)

Minimum Enclosing Triangle

In addition, an implementation of a Theta(n) algorithm for computing the bounding triangle of minimum area on a convex point set is implemented in min_triangle. For more detail, see the original paper on which it is based: [O'Rourke 86].

As an example case:

from geo.generator import randomConvexPolygon
from geo.drawer import plot, show
from min_triangle import minTriangle

polygon = randomConvexPolygon(100)
triangle = minTriangle(polygon)
plot(polygon, style='g-')
show(triangle, style='ro--')

While OpenCV includes an existing implementation of this algorithm in C++, this is the first of its kind in Python.

Dependencies

  • Numpy, Scipy: for computing convex hulls and more.
  • Poly2Tri: for computing triangulations of polygons (with holes).
  • matplotlib: for visualizations.
Something went wrong with that request. Please try again.