From 154bf28c0d065bd81558e8fbdaea0047a1207788 Mon Sep 17 00:00:00 2001 From: BlackMinou Date: Tue, 15 Sep 2015 09:13:36 +0200 Subject: [PATCH] geometry: Adds a README Signed-off-by: BlackMinou --- lib/geometry/README.md | 56 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) create mode 100644 lib/geometry/README.md diff --git a/lib/geometry/README.md b/lib/geometry/README.md new file mode 100644 index 0000000..3e20f59 --- /dev/null +++ b/lib/geometry/README.md @@ -0,0 +1,56 @@ +Basic geometry data structures and services. + +# Points and Lines + +The very basics of geometry needs, for two and three-dimensional space. + +# Boxes and detection collision + +Boxes module introduces Bounding boxes for Points and Lines and services to detect collision or inclusion between boxes. +It means a simple and fast way to test collision but not really accurate since it uses bounding boxes. + +# Quadtrees + +A QuadTree is a tree data structure in which each internal node has exactly four children +They're most often used to partition two-dimensional space by recursively subdividing +it into four quadrants or regions. + +* They decompose space into adaptable cells +* Each cell has a maximum capacity. When maximum is reached, the cell splits. + +Quadtrees are using Boxed objects to determine their distribution in the 2D space. + +This API provides two different types of Quadtree : Static and Dynamic (respectively `SQuadTree` and `DQuadTree`). + +* Static: When you create the QuadTree, you need to specify the region that it will cover + +* Dynamic: You just need to fill the quadtree with objects, and when the threshold is reached, +it will automatically divide the current region, depending on the distribution of objects already in the region. + +# Polygons + +Some basic polygon services. + +This module contains interesting algorithms for `ConvexPolygon`only at the moment. A Convex polygon can be defined as follow : + +* All its interior angles are less than 180°. this means that all the vertices of the polygon +will point outwards, away from the interior of the shape. + +* Every point on every line segment between two points inside or on the boundary of the polygon +remains inside or on the boundary. + +* The polygon is entirely contained in a closed half-plane defined by each of its edges. + +* For each edge, the interior points are all on the same side of the line that the edge defines. + +* The angle at each vertex contains all other vertices in its edges and interior. + +A polygon which is not convex is called concave. Convex polygon are used because most +geometric problems are simpler and faster on convex objects than on non-convex ones. + +Services provided : + +* Point in convex polygon +* Intersection of convex polygon +* Convex hull of a set of points +* Triangulation of polygon -- 1.7.9.5