RGeometry

RGeometry is a collection of data types such as points, polygons, lines, and segments, and a variety of algorithms for manipulating them. This crate will be of use to you if you've ever wondered if a point is inside a polygon or if a bank is adequately covered by surveillance cameras.

FAQ:

Does RGeometry support 3D objects?: Yes, but most of the algorithms are 2D only.
Can I compile RGeometry to JavaScript?: Yes, that is how the playground and all the interactive examples work.
Any relation to HGeometry?: Yes, there is overlap in both developers and key concepts.

Geometry is inherently visual and the quickest way to intuitively understand this library is to see it in action. Below are interactive examples of most of the algorithms.

Triangulation

\(O(n \log n)\) | wiki | play | api

Earclipping with geometric hashing is expected to run in near-linear time and in practice performs better than more advanced algorithms with lower worse-case complexity bounds.

Convex Hull

\(O(n \log n)\) | wiki | play | api

Graham's scan implementation for finding the convex hull of a set of points.

Random Polygons

\(O(n^4)\) | wiki | play | api

No matter how you move the points around, the polygon is always be valid and have no self-intersections.

Random Monotone Polygons

\(O(n \log n)\) | wiki | play | api

Monotone polygons has at most two intersections when sliced at a given angle. They are used for their properties in many algorithms, and random generation is vital for automated testing.

Random Convex Polygons

\(O(n \log n)\) | wiki | play | api

Unlike regular polygons, convex polygons can be efficiently sampled without bias. Mostly useful for testing. Adjust the slider to control the number of vertices.