lib/geometry/README.md

   1 Basic geometry data structures and services.
   2
   3 # Points and Lines
   4
   5 The very basics of geometry needs, for two and three-dimensional space.
   6
   7 # Boxes and detection collision
   8
   9 Boxes module introduces Bounding boxes for Points and Lines and services to detect collision or inclusion between boxes.
  10 It means a simple and fast way to test collision but not really accurate since it uses bounding boxes.
  11
  12 # Quadtrees
  13
  14 A QuadTree is a tree data structure in which each internal node has exactly four children
  15 They're most often used to partition two-dimensional space by recursively subdividing
  16 it into four quadrants or regions.
  17
  18 * They decompose space into adaptable cells
  19 * Each cell has a maximum capacity. When maximum is reached, the cell splits.
  20
  21 Quadtrees are using Boxed objects to determine their distribution in the 2D space.
  22
  23 This API provides two different types of Quadtree : Static and Dynamic (respectively `SQuadTree` and `DQuadTree`).
  24
  25 * Static: When you create the QuadTree, you need to specify the region that it will cover
  26
  27 * Dynamic: You just need to fill the quadtree with objects, and when the threshold is reached,
  28 it will automatically divide the current region, depending on the distribution of objects already in the region.
  29
  30 # Polygons
  31
  32 Some basic polygon services.
  33
  34 This module contains interesting algorithms for `ConvexPolygon`only at the moment. A Convex polygon can be defined as follow :
  35
  36 * All its interior angles are less than 180°. this means that all the vertices of the polygon
  37 will point outwards, away from the interior of the shape.
  38
  39 * Every point on every line segment between two points inside or on the boundary of the polygon
  40 remains inside or on the boundary.
  41
  42 * The polygon is entirely contained in a closed half-plane defined by each of its edges.
  43
  44 * For each edge, the interior points are all on the same side of the line that the edge defines.
  45
  46 * The angle at each vertex contains all other vertices in its edges and interior.
  47
  48 A polygon which is not convex is called concave. Convex polygon are used because most
  49 geometric problems are simpler and faster on convex objects than on non-convex ones.
  50
  51 Services provided :
  52
  53 * Point in convex polygon
  54 * Intersection of convex polygon
  55 * Convex hull of a set of points
  56 * Triangulation of polygon