The aim of the Geometry Library is to clean up and unify KiCad's 2D
geometry engine and provide a solid base
for tools demanding more complex geometry operations, such as a
Currently every object on a PCB/Schematic has its own notion of geometric shape.
Different subsystems deal with basic 2D geometry operations in their own
There are at least 5 of such places:
- hit testing
- DRC/polygon processing
- LIB_ITEM derived classes in eeschema.
Adding another pad type could serve as an example of how much existing
code would have to be modified to full support the new pads in all
Need for extra geometry processing functions:
Push & Shove requires spatial indexing and convex hull generation.
Convex partitions may be required for rendering polygons (unless
sophisticated polygon cache is implemented inside the GAL). DRC may
require need them to fully check polygon-to-anything-else clearance
DRC needs many more checks to be implemented - for example
mask/silkscreen clearance, which require any-to-any shape distance
Smart selection (i.e. guessing what the user wanted to select in
clicking over multiple objects, depending on the neighbourhood)
requires fast conversion
of complex shapes to to polygons, clipping and polygon area &
In case of the DRC, geometry functions are very model-specific, so
cannot be easily reused on different types of objects.
This results in artificial limitations, such as inability to stitch
polygons (because DRC redoes them instead of just checking the
clearances) or place arcs on copper layers (e.g. teardrops or
mitered traces, a must-have for high speed designs).
Numerical consistency between subsystems:
Any numerical differences between different geometry implementations
will very likely result with DRC dropping lots of clearance errors
caused by P&S and P&S unnecessarily adjusting objects that have
Current geometry operations take a lot of code to maintain.
... and sometimes they are not very well designed (like
In many places, intersection and distance calculations internally use
(basing all calculations on y=mx + b line equations),
which results with rounding errors for more vertical lines.
The Geometry library incorporates the 3 parts:
basic classes for 2D vector, axis-aligned bounding box, line segment
collection of basic 2D shapes used in schematics and PCB geometry
shape groups (a set of shapes treated as a single solid shape) and
collision and minimum distance queries (with respect to a VECTOR2,
BOX2 or any
interface compatible with STL (iterators)
Numerically stable (explicit specialization for T == int to avoid
overflow on multiplication) 2D vector class.
Provides standard vector arithmentic, product, and distance
operators. Replacement of all wxPoints in the code that is not
related to the GUI.
template class BOX2
Bounding box class, based on EDA_RECT. Intended to replace
EDA_RECT, GAL's BOUNDING_BOX and wxRects in the parts of code that
are not UI-specific.
class ANGLE, implementing a restricted set of angles. Provides
accurate point rotation
and vector->magnitude operators (in certain cases, without floating
point trigonometry and rounding errors
associated with it). For example an ANGLE45 class could be derived
from ANGLE and provide float-less (n * 45 degree) directions for
all other geometry operations.
template class SEG
Class defining a line segment. Provides segment/line/point
intersection, point-to-segment and segment-to-segment distance
Shapes mandatory for the P&S router:
class SHAPE : abstract interface for all SHAPE_ classes.
class SHAPE_RECT: axis-aligned rectangle
class SHAPE_CIRCLE: full circle
class SHAPE_LINE_CHAIN (_POLYLINE): string of line segments
(zero-width polyline). Polygon outline is of type
More complex shapes (for DRC):
class SHAPE_ORIENTED_RECT: rectangle with rotation
class SHAPE_POLYGON: polygon with holes. Outline/hole edges are
stored as SHAPE_LINE_CHAINs
class SHAPE_ARC: circular arc (zero-width)
class SHAPE_BEZIER: quadratic bezier curve (zero-width)
Shape groups and indexes
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 method.
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
P&S will largely depend on spatial indexing and collision
Even partially done geometry library can be used to quickly develop
of new DRC tests: component-to-component, solder/pastemask sliver,
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
DRC would not need to modify zones but only check their clearances,
refilling would be performed when the user requests it.