README.md

@anntopia/geometry

Document

Curve

• cubic spline
• cubic parameter spline
• hermite spline
• cardinal spline
• catmull rom spline
• lagrange spline
• akima spline
• bezier spline
• b-spline
• NURBS

Bounding Box

• axis aligned box
• minimum area box
• minimum perimeter box

Convex Hull

• chan convex hull
• jarvis march convex hull
• graham scan convex hull

Triangulation

• delaunay triangulation
• polygon triangulation [bug]
• min weight triangulation

Boolean Operation

• line
  • line intersection
  • line segments intersection
• polygon
  • point in polygon
  • line-polygon intersection
  • polygon intersection
  • polygon clipping
  • polygon union

Distance

• closest pair of points
• farthest pair of points
• gilbert-johnson-keerthi
• shortest path

Area

• largest empty circle
• voronoi diagram
• shoelace algorithm
• half plane intersection [bug]

Query

• point location
• range searching
• nearest neighbor

Primitive

• point
• triangle
• circle
• polygon

Spatial Data Structure

• grid
• bsp tree
• quad tree
• octree
• kdtree
• range tree
• r tree
• bounding volume hierarchies

Ref

• https://en.wikipedia.org/wiki/Computational_geometry#Problem_classes
• https://en.wikipedia.org/wiki/List_of_algorithms#Geometry