No commit message

geometryspec.md

@@ -78,6 +78,46 @@ The Geometry library incorporates the 3 parts:
   - shape groups (a set of shapes treated as a single solid shape) and
     indexes.
 
+Features required for all shapes:
+
+  - Basic geometry operations: mirror/rotate/translate
+  - Axis-aligned bounding box generation. Each shape must provide a
+    BoundingBox() method.
+  - Potential intersection test (using bounding boxes).
+  - Convex hull generation. For shapes that incorporate curves, the
+    convex hull can be approximated by first converting the shape to a
+    polygon.
+  - Intersection test, returning list of intersecting points. 
+  - Minimum distance between shapes, returing the segment connecting the
+    closest points in both shapes.
+  - Point inside test.
+  - Area calculation.
+  - Conversion to a polygon (closed shapes or shapes with thickness) or
+    a line chain, with user-defined approximation accuracy.
+  - Serialization/deserialization in s-expression format.
+
+Segments/line chains:
+
+  - Perpendicular projection of a point on a line/segment.
+  - Segment collinearity check.
+  - Line chain simplification (remove duplicate vertices and collinear
+    segments).
+
+Polygons:
+
+  - a cleaned up version of CPolyLine class, following coding standards
+  - boolean operations
+  - chamfered/filleted/offset polygon generation
+  - hatching
+
+Containers / Indexes:
+
+  - add/remove, owning (container) / non-owning(index)
+  - collision and minimum distance queries (with respect to a VECTOR2,
+    BOX2 or any  
+    other SHAPE)
+  - interface compatible with STL (iterators)
+
 ### Basic classes
 
   - **template<typename T> VECTOR2**  
@@ -98,8 +138,9 @@ The Geometry library incorporates the 3 parts:
     from ANGLE and provide float-less (n \* 45 degree) directions for
     all other geometry operations.
   - **template<class Vec> class SEG**  
-    Class defining a line segment. Provides segment/line intersection,
-    point-to-segment and segment-to-segment operators.
+    Class defining a line segment. Provides segment/line/point
+    intersection, point-to-segment and segment-to-segment distance
+    operators.
 
 ### Supported shapes
 
@@ -107,23 +148,54 @@ Shapes mandatory for the P\&S router:
 
   - **class SHAPE** : abstract interface for all **SHAPE\_** classes.
   - **class SHAPE\_RECT**: axis-aligned rectangle
-  - **class SHAPE\_ORIENTED\_RECT**: rectangle with rotation
   - **class SHAPE\_CIRCLE**: full circle 
-  - **class SHAPE\_LINE\_STRING**: string of line segments (a polyline)
+  - **class SHAPE\_LINE\_STRING**: string of line segments (a polyline,
+    with optional thickness)
 
-More complex shapes (for DRC)
+More complex shapes (for DRC):
 
+  - **class SHAPE\_ORIENTED\_RECT**: rectangle with rotation
   - **class SHAPE\_POLYGON**: polygon with holes. Cleaned-up version of
     CPolyLine.
-  - **class SHAPE\_ARC**: circular arc
-  - \*class SHAPE\_BEZIER: quadratic bezier curve.
+  - **class SHAPE\_ARC**: circular arc (with optional thickness)
+  - \*class SHAPE\_BEZIER: quadratic bezier curve (with optional
+    thickness)
 
 ### Shape groups and indexes
 
-  - class SHAPE\_GROUP: group of shapes, behaving as a single body. Each
-    shape can have an individual offset (a vector) wrs to the group
-    origin.
+  - class SHAPE\_GROUP: group of shapes, behaving as a single solid
+    body. Each member shape can have an individual offset (a vector)
+    with respect to the group origin.
   - class SHAPE\_INDEX: class for spatial indexing of shapes. Internally
     implements an R/R\*/Bounding Volume/Bounding Interval Tree. Provides
     fast distance/collision query operator.
 
+## Implementation
+
+To consider:
+
+  - whether to design and write something from scratch (lots of  
+    GPL/LGPL/BSD/MIT code available),
+  - or rely on a library (consider builing and integration issues).
+    **boost::geometry** seems to be worth checking out,  
+    **clipper** already does all what we need regarding polygons.
+  - first clients/test targets: new graphics subsystem and C** P\&S
+    implementation.
+
+Targets:
+
+  - P\&S will largely depend on spatial indexing and collision
+    detection.
+  - Even partially done geometry library can be used to quickly develop
+    a number  
+    of new DRC tests: component-to-component, solder/pastemask sliver,
+    and  
+    silkscreen-over-pads test. 
+  - As soon as polygon support is available, the DRC could be improved
+    with a proper  
+    solution to the polygon stitching issue. With the new geometry
+    code,  
+    DRC would not need to modify zones but only check their clearances,
+    and zone  
+    refilling would be performed when the user requests it.
+