# Specification¶

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 Push&Shove router.

## Rationale¶

### 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 way.

There are at least 5 of such places:

- drawing

- plotting

- 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 subsystems.

### Need for extra geometry processing functions:¶

- Push & Shove requires spatial indexing and convex hull generation.
- Convex partitions may be required for rendering polygons (unless some

sophisticated polygon cache is implemented inside the GAL). DRC may also

require need them to fully check polygon-to-anything-else clearance (including

graphical objects). - DRC needs many more checks to be implemented - for example

mask/silkscreen clearance, which require any-to-any shape distance check. - Smart selection (i.e. guessing what the user wanted to select in case of

clicking over multiple objects, depending on the neighbourhood) requires fast conversion

of complex shapes to to polygons, clipping and polygon area & coverage calculation.

In case of the DRC, geometry functions are very model-specific, so they

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 passed

the DRC.

### Current geometry operations take a lot of code to maintain.¶

... and sometimes they are not very well designed (like polygon/math_for_graphics.cpp).

In many places, intersection and distance calculations internally use floating point

(basing all calculations on *y=mx + b* line equations),

which results with rounding errors for more vertical lines.

## Functional requirements¶

The Geometry library incorporates the 3 parts:- basic classes for 2D vector, axis-aligned bounding box, line segment and angle.
- collection of basic 2D shapes used in schematics and PCB geometry
- shape groups (a set of shapes treated as a single solid shape) and indexes.

- 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.

- Perpendicular projection of a point on a line/segment.
- Segment collinearity check.
- Line chain simplification (remove duplicate vertices and collinear segments).

- a cleaned up version of CPolyLine class, following coding standards
- boolean operations
- chamfered/filleted/offset polygon generation
- hatching

- 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**

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 Vec> 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 Vec> class SEG**

Class defining a line segment. Provides segment/line/point intersection, point-to-segment and segment-to-segment distance operators.

### Supported shapes¶

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 SHAPE_LINE_CHAIN.

**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.

## 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.

- 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.