Home page: github.com/skramm/homog2d

This is the user manual for the current master branch of homog2d. For stable releases, see https://github.com/skramm/homog2d/releases .

To get the reference manual (requires Doxygen), you can either type $ make doc or $ doxygen misc/doxyfile (online here

If you are interested in code, check the page homog2d_devinfo.md.

Index is available here.

1. Introduction
2. Lines and points
3. Other geometric primitives
4. 2D transformation (aka homographies)
5. Intersections and enclosings determination
6. Misc. features
7. Bindings
8. Drawing things
9. Numerical data types
10. SVG import
11. Technical details
12. Runtime polymorphism
13. FAQ
14. History

All the code is in the namespace h2d, so either add using namespace h2d;, either use it as a prefix on each type (There are a lot of sub-namespaces, but unneeded for the end-user).

This library provides several main data types: lines, points, segments, circles, ellipses, polyline and homography matrices. These can be used to transform one of the basic types (planar transformation). It is implemented as a homogeneous 3x3 matrix.

All the data types implement a comparison operator ( == and !=).

This library does not provide exact arithmetic, it relies instead on basic floating-point types for storage and computations, but user can select the underlying type. The types are fully templated by the underlying numerical type. If more precision is required, an external library providing arbitrary binary size for numerical values can be used, see here.

To make things simple, we introduce here only the default type, based on double (see Numerical data types for details).

The API is exposed both as member functions and as free functions. Say for example you have a type AAA on which you can apply the foo() operation. Both of these are possible:

AAA thing;
auto v1 = thing.foo();
auto v2 = foo( thing );
BBB some_argument;
auto z1 = thing.foo( some_argument );
auto z2 = foo( thing, some_argument );

• Create or edit a 2D point:

Point2d pt1;       // 0,0
Point2d pt2(3,4);
pt1.set( 5, 6 );

• Create a 2D line:

Line2d li1;             // vertical line at x=0
Line2d li2( 3, 4 );     // line passing through (0,0) and (3,4)
Line2d li3( LineDir::H, 15 ); // horizontal line at y=15
Line2d li4( LineDir::V, -2 ); // vertical line at x=-2

• For horizontal or vertical lines, you can also just provide a point, the constructor will handle it:

Point pt(x,y)
Line2d liH( LineDir::H, pt );
Line2d liV( LineDir::V, pt );

• Create a point from two lines, and a line from two points:

Point2d pt3( li1, li2 );
Line2d  li3( pt1, pt2 );

• Get a line from two points, and a point from two lines:

auto pt = li1 * li2;
auto li = pt1 * pt2;

Beware, two parallel lines will never cross, and two identical points do not define a line. So if your code attempts to do so, this will trigger a std::runtime_error exception.
If you are unsure, you can check first:

if( li1.isParallelTo(li2) )
	cout << "Lines are parallel !\n";
if( pt1 == pt2  )
	cout << "Points are identical !\n";

For the numerical considerations on this, check below, section Numerical data types.

• To get the euclidean coordinates of a point, two member functions are provided:

auto x = pt.getX();
auto y = pt.getY();

Or use the equivalent free functions:

auto x = getX(pt);
auto y = getY(pt);

• To get the 3 components of a line as a homogeneous array, one may use:

auto v = line.get();
std::cout << '[' << v[0] << ',' << v[1] << ',' << v[2] << '\n';

But if its about printing, then the easiest is to use the overloaded operators:

Line2d li;
std::cout << li << '\n';

(BTW: this is the same for all the other primitives, points and others).

• Compute distances from line to point or from point to point:

Line2d li;        // some line
Point2d pt1, pt2; // some points
auto dist1 = li1.distTo( pt1 );   // distance from line to point
auto dist2 = pt1.distTo( li1 );   // but you can do this too
auto dist2 = pt2.distTo( pt1 );   // distance from point to point

Line2d li2;
// auto dist = li.distTo( li2 );   // this does not build !

For points, you may also use the corresponding free function:

Point2d pt1, pt2;          // some points
auto d = dist( pt1, pt2 );

• You can compute the segment generated by a point and a line, using the shortest distance:

Line2d line;
Point2d pt;
auto seg_orth = line.getOrthogSegment( pt );

This is illustrated on this figure, showing a rotating point and the computed orthogonal segment to a line (source):

To get a point lying on a line, you can provide one of its coordinates and get the other coordinate value, using the enum GivenCoord. For example, if you build the line going through (0,0)-(4,2) with:

Line2d li(4,2);

You can compute the coordinate of y for x=2 with:

auto y = li.getCoord( GivenCoord::X, 2 );

or get the coordinate of x for y=1 with:

auto x = li.getCoord( GivenCoord::Y, 1 );

You can also get directly the point with:

Point2d pt2 = li.getPoint( GivenCoord::X, 2 );

Some care has to be taken with these functions, because they will throw if unable to provide a result. For example, if you try to get the 'y' coordinate from a vertical line, this will fail. The following code will throw:

Line2d li;    // vertical line at x=0
auto y = li.getCoord( GivenCoord::X, 0 );

You can compute the two points that are lying on a line and at a given distance from a point.

The API provides two ways to get these:

1 - either you provide the x or y coordinate of p0:

Line2d li( ..., ... ); // some line
auto ppts = li.getPoints( GivenCoord::X, coord, dist ); // returns a std::pair
Point2d p1 = ppts.first;
Point2d p2 = ppts.second;

The drawback is same as the above paragraph: if line is vertical and you provide a 'x' coordinate, this will throw (and similarly with an horizontal line and a 'y' coordinate).

2 - either you provide directly the point:

Line2d li( ..., ... ); // some line
Point2d pt_on_line;
auto ppts = li.getPoints( pt_on_line, dist ); // returns a std::pair

The drawback is that you need to be sure that this point is truely on the line. This will be checked for, and library will throw if not (except if error checking is disabled, see build options).

Upon return, the "first" point will hold the one with smallest 'x' coordinates, or the smallest 'y' coordinates if x coordinates are equal.

You can compute a line orthogonal to another one at a given coordinate, using the above enum. For example, this:

auto lB = lA.getOrthogonalLine( GivenCoord::X, x1 );

will build lB so that it is orthogonal to lA at x=x1.

Similarly, you can also directly use as input a point on the line:

Line2d liB = lA.getOrthogonalLine( p1 );

Again, point is checked and this will throw if distance from point to line is above some threshold (see "numerical issues").

You can get a line parallel to another one with the member function getParallelLine(). This function takes as argument a point that the line will intersect.

Line2d li1; // some line
Point2d pt; // some point
auto li2 = li1.getParallelLine( pt ); // pt will be lying on li2, wich is parallel to li1

If you need a parallel line to another at a given distance, then you can use getParallelLines(), provided either as a free function or as a member function. They both return a pair (std::pair) of lines, one on one side, and the other on the other side of the input line:

Line2d li; // some line
auto p_lines1 = li.getParallelLines( 100 );
auto p_lines2 = getParallelLines( li, 50 ); // free function
auto liA = p_lines1.first;
auto liB = p_lines1.second;

If you know that two lines are parallel and you want the distance between them, then you have:

auto dist = getParallelDistance( li1, li2 );

This will throw if lines are not parallel (unless error checking is disabled).

You can compute the angle in Radians between two lines, either with a member function or with a free function:

auto angle1 = li2.getAngle( li1 );
auto angle2 = getAngle( li1, li2 ); // free function

You can rotate a line at a given point (must be lying on the line):

auto li1 = pt1 * pt2;
auto li2 = li1.getRotatedLine( pt1, angle /* in rads */ );

The function side( Point2d, Line2d ); will return an int value, either -1, 1 or 0 if point lies on the line.

The tipping point is the horizontal line.

See showcase16 for an example.

As points and lines are stored with homogeneous coordinates, one can also build theses using 3 values:

// horizontal line at y=0
auto li1 = Line2d( 0, 1, 0 );  // or: Line2d li( 0, 1, 0 );

// a point at x=1, y=1
auto pt1 = Point2d( 1, 1, 1 ); //: or Point2d pt1( 1, 1, 1 );

It is also possible to initialize existing variables with homogeneous coordinates:

li1.set( 1, 2, 3 );
pt1.set( 4, 6, 2 );  // point lies at x=2, y=3

A container such as std::vector or std::array can be used too:

std::vector<float> vec{1,2,3};
Line2d li( vec );

std::array<double,3> arr{1,2,3};
Point2d pt( arr );

Storing points and lines with homogeneous coordinates allows us to handle points at infinity:

Point2d pt(1,2,0);
assert( pt.isInf() );

Such points can still be used, for example to build a line or a segment:

Point2d pt(1,0,0);
Line2d li = pt * Point2d();

Besides points and lines, the following primitives are provided:

• segment
• flat rectangle
• circle
• polyline
• ellipse

The ones that may cover some area (polyline, rectangle, ellipse, circle) provide a function getBB() that returns a flat rectangle holding the bounding box. This is not available for points, lines, and segments (as a segment can be vertical or horizontal, it does not have an area).

On this figure, you can see a circle, a polyline and and ellipse, along with their corresponding bounding boxes. For the ellipse, you can get both the axis-aligned bounding box (shown in blue here), and the ellipse-axis aligned bounding box, shown in green.

Besides these, you can also get the bounding box of two arbitrary primitives p1,p2, even of different types, with a free function:

auto bb = getBB( p1, p2 );

On this figure, you can see three combinations of bounding boxes for some objects.

source

A segment is implemented internally as a pair of points. Usage is straightforward:

Segment s1( Point2d(12,34), Point2d(45,67) );
Segment s2; // default value
std::cout << s2;  // prints "(0,0) - (1,1)"
s2.set( Point2d(12,34), Point2d(45,67) );

You can also build the segment by giving the 4 coordinates, x1,y1 and x2, y2 of the two points. The only constraint is that they must be all of the same type (no int/float/double mix):

Segment s1( x1, y1, x2, y2 );

It can also be initialized (or set) with a pair of points:

auto ppts = std::make_pair( Point2d(4,5), Point2d(2,1) );
Segment s1( ppts );
s1.set( ppts );

Besides using a homography matrix, translating the segment can be done with a member function:

Segment s1( ... );
s1.translate( dx, dy );

You can get the pair of points (as an std::pair) with getPts(). Internally, the points are stored with the "smallest" one as first (using x coordinate, or, if equal, using y coordinate):

Segment s1( Point2d(100,100), Point2d(10,10) );
auto pair = s1.getPts();
std::cout << pair.first; // will print (10,10)

Many operations available with lines apply to segments too:

Segment s1( Point2d(12,34), Point2d(45,67) );
Line2d l1  = s1.getLine();  // get supporting line
Line2d l12 = getLine(s1);   // or with free function
bool b1 = l1.isParallelTo( s1 );
bool b2 = s1.isParallelTo( l1 );  // also works
auto a1 = l1.getAngle( s1 );
auto a2 = s1.getAngle( l1 );

You can get the point lying in the middle of the segment:

Segment s1( Point2d(1,2), Point2d(3,4) );
auto p_middle = s1.getCenter(); // or: getCenter(s1)

This middle point can be used to split a segment into two equal length segments, returned as a std::pair:

Segment seg( Point2d(1,2), Point2d(3,4) );
auto p_segs = seg.split(); // or: split(seg)

The bisector line is available, using a member or free function:

Segment seg( Point2d(1,2), Point2d(3,4) );
auto line1 = seg.getBisector(); // or: getBisector(seg)

You can generates a std::pair of two parallel segments, lying at a distance dist, with:

Segment seg( pt1 , pt2 );
auto p_segs = seg.getParallelSegs(dist); // or: getParallelSegs(seg,dist)

See for a demo.

The length is available with a member function or a free function:

Segment seg( Point2d(1,2), Point2d(3,4) );
auto length  = seg.length(); // or: length(seg)

The extended segment is available with a free of member function:

Segment seg( pt1, pt2 );
auto seg_ext = seg.getExtended(); // or getExtended(seg);

The extended segment has the same support line, but is "extended" on both sides with the length of the segment. Thus its length is three times the original segments length. On the figure below, the original segment is blue and the extended segment is red. The support line is gray.

You can fetch the orthogonal segments or points with getOrthogPts() and getOrthogSegs() (member or free functions). These two member functions return an std::array of size 4, the latter filled with the 4 orthogonal segments, and the first filled with the associated 4 points.

Due to the unoriented nature of the Segment type, these two member functions return points or segments in an unpredictable order.

The distance between a segment and a point can be computed. The code considers the different situations: shortest distance can be the orthogonal distance to the supporting line, or the distance to one the two points defining the segment.

Point2d pt;
Segment seg;
auto dist = set.dist( pt );

This function has an optional second argument: a pointer to an int, that will hold upon return one of these three values:

• 0: distance is the orthogonal distance to the support line
• +1: distance is the one between point and smallest point of the segment
• -1: distance is the one between point and largest point of the segment

See showcase8 for an illustration.

A flat rectangle is provided through the class FRect. It is modeled by its two opposite points.

FRect r1; // (0,0) (1,1)
FRect r2( Point2d(0,0), Point2d(10,10) );
FRect r3( 1,5,3,4 ); // (1,4) - (3,4) - (3,5) - (1,5)
r1.set( pt1, pt2 );
r2.set( 1,2, 3,4 );

When using the constructor or the set() member function, there is no constraint on the points themselves: the library will automatically adjust the points to store the two opposite ones, with the one with smallest coordinates as "first".

This means you can give either (p0,p1) or (p2,p3), only p0 and p1 will be stored:

The only constraint is that no coordinate can be equal. The function will throw if it is not enforced.

You can also build the rectangle by giving the 4 coordinates x1,y1 and x2,y2. The only constraint is that they must be all of the same type (no int/float/double mix).

FRect r1( x1, y1, x2, y2 );

Or by giving the center point and width and height:

FRect r1( p0, w, h );

Or by providing a std::pair of points:

std::pair<Point2d,Point2d> ppts = std::make_pair( Point2d(0,0), Point2d(10,10) );
FRect rect( ppts );

You can get the points with two different member functions:

FRect rect( pt1, pt2 );
auto pair_pts  = rect.getPts();  // returns the 2 points p0,p1 in a std::pair
auto pair_pts2 = getPts(rect);   // or use the free function
auto pts  = rect.get4Pts();      // return a std::array of 4 points
auto pts2 = get4Pts(rect);       // or use the free function

A call to the get4Pts() member or free function will return the points in the following order:

 p[1] +------+ p[2]
      |      |
      |      |
      |      |
 p[0] +------+ p[3]

You can also fetch the 4 segments of the rectangle, with a member function or a free function:

FRect rect( pt1, pt2 );
auto segs = rect.getSegs(); // returns a std::array of 4 segments.
auto segs2 = getSegs(rect); // your choice

The returned array holds the segments in the following order:

        s[1]
     +-------+
     |       |
s[0] |       | s[2]
     |       |
     +-------+
        s[3]

The two diagonal segments can be fetched as a pair of segments:

FRect rect( pt1, pt2 );
auto psegs = rect.getDiagonals();  // or: getDiagonals(rect);

The first element will hold the segment holding the point with minimal coordinates (p[0] and p[2] on above drawing).

And of course, its width, height, length, and enclosed area. This is available through member functions or free functions.

FRect rect;
auto w = rect.width();  // or: width(rect);
auto h = rect.height(); // or: height(rect);
auto a = rect.area();   // or: area(rect);
auto l = rect.length(); // or: length(rect);

You can gets its size as a pair of values (member function or free function), with the width as first element and height as second element:

FRect rect;
auto s1 = rect.size();   // or: size(rect);

It is possible to translate the rectangle using some dx,dy offset:

FRect rect;
rect.translate( dx, dy );

Full step rotation (+90°,-90°,180° or vertical/horizontal mirroring) is available with the rotate() member or free function:

FRect rect;
rect.rotate( Rotate::CCW ); // or: rotate( rect, Rotate::CCW );

This will proceed a rotation around origin point (0,0). But most of the times, you want to rotate around some specific point, so you can use this:

FRect rect;
Point2d pt(x,y);
rect.rotate( Rotate:CCW, pt ); // or: rotate( rect, Rotate:CCW, pt );

See related polyline function for details.

You can get both the the bounding circle and the inscribed circle:

FRect r1(...); // whatever
auto c1 = r1.getBoundingCircle();  // or: getBoundingCircle(r1);
auto c2 = r1.getInscribedCircle(); // or: getInscribedCircle(r1);

The extended flat rectangle is available with a free of member function:

FRect  r1( pt1, pt2 );
auto rect_ext = r1.getExtended(); // or getExtended(r1);

The extended flat rectangle will have an area 9 times the area of original rectangle.

The diagonal segments are available with a call to a member or free function:

FRect  r1( pt1, pt2 );
auto p_diags = = r1.getDiagonals(); // or getDiagonals(r1);

The figure below shows the extended rectangle and the diagonals. red: the original rectangle, blue: the extended one, green: the diagonal segments, and gray: the supporting lines (source file).

Check this section about union and intersection area of two rectangles.

These are modeled by their center point and radius. Creation is straightforward, whatever your needs:

Circle c1;                          // at (0,0), radius = 1
Circle c2( center_point );          // radius = 1
Circle c3( center_point, radius );
Circle c4( x0, y0, radius );

Similarly, you can assign values to an existing circle:

c1.set( x0, y0, radius );
c2.set( center_pt, radius );
c3.set( radius );            // center doesn't change
c4.set( center_pt );         // radius doesn't change

You can also compute the unique circle from points, either from 2 points (that define the diameter), or from 3 points:

Circle c1( pt1, pt2, pt3 );
// or
c1.set( pt1, pt2, pt3 );

Circle c2( pt1, pt2 );
// or
c2.set( pt1, pt2 );

For these latter functions, the 2 (or 3) points must be different, and not colinear (for 3 points). This is checked for and will throw if not the case (unless the "no checking" build option is activated, see here).

Minimum Enclosing Circle (MEC)

To compute the Minimum Enclosing Circle of a set of points, you can use either a constructor, or the equivalent set() function:

std::vector vpts( ... some points ...  );
Circle c1( vpts);
// or
c1.set( vpts );

See showcase13 for an example. It uses the Welzl algorithm, that require O(n) time and O(n) memory (recursive technique). The input container can be std::vector, std::array, or std::list. It requires a least 2 points in the container, and will throw if condition not met.

Center and radius can be accessed (read/write) with provided member functions:

Circle c1;
c1.radius() = 100;
std::cout << c1.radius();  // prints '100'
c1.center() = Point2d(12,34);
std::cout << c1.center(); // prints '[12,34]'

Corresponding free functions are also provided:

radius(c1) = 100;
std::cout << radius(c1);  // prints '100'
center(c1) = Point2d(12,34);
std::cout << center(c1); // prints '[12,34]'

You can get area and perimeter with member or free functions. The perimeter function has the name "length" for consistency with other primitives.

auto area  = c1.area();   // or: area(c1)
auto perim = c1.length(); // or: length(c1)

Two additional free functions provide the segment (or line) between the centers of two circles, and the two segments tangential to two circles:

Circle c1, c2;
auto seg = getSegment( c1, c2 );  // as a segment
auto line = getLine( c1, c2 );    // as a line
// same result than: getSegment( c1, c2 ).getLine();
auto pair_segs = getTanSegs( c1, c2 ); // std::pair of Segment

This class holds a set of points and models an arbitrary set of joined segments, without orientation. It is available as two classes OPolyline_ (open) and CPolyline_ (closed).

The closed one automatically considers a connection betwen last and first point. It can be used to model a polygon.

OPolyline pl1; // empty
CPolyline pl2;
std::vector<Point2d> vpts;
// fill vpts
pl1.set( vpt );      // sets the points
pl2.set( vpt );

It can be initialised either with a container (std::vector, or std::array, or std::list) holding the points, or (only for the closed version) from a FRect:

std::vector<Point2d> vpts{ {0,0},{1,1},{3,1} };
OPolyline op(vpts);
CPolyline cp(vpts);
FRect rect( .... );
CPolyline cp2(rect);
// OPolyline op2(rect); // this does not build

Another constructor enables building a Polyline from a Segment, wich ends up with a Polyline of 2 points:

Segment seg; // default constructor
OPolyline po(seg);
CPolyline pc(seg);

Warning: you may not add a point identical to the previous one. Whatever the type, this code will throw:

std::vector<Point2d> vpts{ {0,0},{1,1},{3,1},{3,1} };
OPolyline op(vpts);
CPolyline cp(vpts);

An empty polyline is allowed, but the minimum number of points is 2, initializing with a vector holding 1 point will throw.

It has no orientation, meaning that the OPolyline build from this set of points:
(0,0)-(1,0)-(1,1)
will be identical as this one:
(1,1)-(1,0)-(0,0)

It is also possible to build a polyline by importing from a boost::geometry polygon (at present, only possible with the model::point point type). See an example here.

This requires the symbol HOMOG2D_USE_BOOSTGEOM to be defined.

Regular Convex Polygon

It is also possible to build directy a Regular Convex Polygon (RCP) by using a dedicated constructor. For example, this will build a RCP of 5 points, centered at (3,2), with the points at a distance 10:

CPolyline pol( 10, 5 );
pol.translate( 3, 2 );

For more on this, see the related set() function.

The open/close status can be read, but will return a constexpr value:

OPolyline p1;
CPolyline p2;
auto b1 = p1.isClosed(); // always false
auto b2 = p2.isClosed(); // always true

Both types provide access to basic attributes: number of points, number of segments, length and bounding box, all available as member or free functions:

auto n1 = pl.size();  // nb of points
auto n2 = size(pl);
auto s1 = pl.nbSegs(); // nb of segments
auto s2 = nbSegs(pl);

auto length1 = pl.length();   // or  length(pl);
auto rect1   = pl.getBB();    // or  getBB(pl);

You can extract either points or segments. The number of segments is related to the open/close condition. For example, if we have 4 points, that will generate 4 segments if closed, but only 3 if the polyline is open.

std::cout << "nbpts=" << pl.size() << " nb segments=" << pl.nbSegs() << '\n';
auto vec_pts  = pl.getPts();
auto vec_segs = pl.getSegs();
auto pt = pl.getPoint( i );   // will throw if point i non-existent
auto seg = pl.getSegment( i );   // will throw if segment i non-existent

The getBB() member (or free) function returns the corresponding Bounding Box. this is demonstrated in the following figures for two Polyline objects, one closed, the other open.

On these figures is also shown the extreme points, Top-most and Left-most are green, the two others are blue. (see code here).

The convex hull of a Polyline can be computed with the member function convexHull(), see here for an example.

You can get the top-most, left-most, bottom-most, or right-most point with these dedicated member functions:

Point2d_<FPT> getTmPoint() const;
Point2d_<FPT> getBmPoint() const;
Point2d_<FPT> getLmPoint() const;
Point2d_<FPT> getRmPoint() const;

Or use the getExtremePoint( CardDir ) member function and passing one of these:

CardDir::Bottom
CardDir::Top
CardDir::Left
CardDir::Right

For example:

Cpolyline pol;
// .. fill with points
auto top_pt   = pol.getTmPoint();
auto left_pt  = pol.getExtremePoint( CardDir::Left );

These are also available as free functions:

Cpolyline pol;
// .. fill with points
auto top_pt   = getTmPoint( pol );
auto left_pt  = getLmPoint( pol );
auto right_pt = getExtremePoint( CardDir::Right, pol );

(see misc. section for point set equivalent function).

Warning: These functions will throw if passed an empty polyline object.

You can get the closest distance between two points belonging to two polyline objects with getClosestPoints() (free function). This will return an object on which you can fetch the corresponding pair of points, as indexes or as points, and the distance value:

auto closest = getClosestPoints( poly1, poly2 );
auto ppts = closest.getPoints();  // get the points as a pair ("first" belongs to poly1, "second" to poly2)
auto d = closest.getMinDist()     // get the distance value
auto pidx = closest.getIndexes(); // get the indexes related to poly1, poly2

See an example here.

You can check if it fullfilths the requirements to be a simple polygon (must be closed and no intersections).
See definition here.

If it is, you can get its area and its centroid point:

CPolyline pl;
// ... set points
if( pl.isPolygon() ) {  // or : if( isPolygon(pl) )  (free function)
	std::cout << "area=" << pl.area();
	std::cout << "centroid point=" << pl.centroid();
}

warning: function name will change in next release for isSimple()

Please note that if not a polygon, or if applied on a open type, then the area() function will return 0 but the centroid() function will throw.

For closed types, you can determine its convexity:

CPolyline plo;
OPolyline plc;
// ... set points
std::cout << pls.isConvex() ? "is convex\n" : "is NOT convex\n"; // or free function: isConvex(plc)
assert( !plo.isConvex() ); // open is not a Simple Polygon, so it can't be convex

Polyline objects can be compared, however the behavior differs whether it is closed or not. Consider these two sets of points:

(1,1)--(3,4)--(1,3)
(3,4)--(1,3)--(1,1)

If they are not closed, then the == operator will return false. But if they are (both) closed, it will return true, as they obviously describe the same polygon.

This is handled through a normalization step, called automatically.

• if "closed" type, the normalization will reverse and rotate the points, so that the smallest point is first and the second one is smaller than the last one.
• if "open" type, only the reverse operation is performed.

However, comparison of identical objects can fail in some circumstances, because a Polyline object can hold the same point several times (but not contiguous). Consider these two closed Polyline objects:

A: (0,0)-(3,0)-(3,1)-(0,0)-(0,3)-(1,3)
and
B: (3,0)-(3,1)-(0,0)-(0,3)-(1,3)-(0,0)

They both describe the same object:

When compared, they will be considered as different because they both use twice the same point (0,0) and their normalisation will produce these sets of points:
A: (0,0)-(3,0)-(3,1)-(0,0)-(0,3)-(1,3) (unchanged)
B: (0,0)-(0,3)-(1,3)-(0,0)-(3,0)-(3,1)

For more details, see homog2d_Polyline.md.

All the primitives can be rotated using a homography (see following section), but in some situations you may only need "quarter-circle" rotations (mutiples of 90°). While it is of course possible to proceed these rotations with a homography, the downside is that you may end up with 0 values stored as 1.359 E-16, due to numerical nature of floating point computation. This can be undesirable, so an alternative is provided: You may rotate/mirror all the points of polyline objects with the rotate() member function. it takes as argument an enum value of type Rotate.

The available values are:

• CW: -90° (Clockwise)
• CCW: +90° (Counter Clockwise)
• Full: 180°
• VMirror: Mirror points relatively to vertical axis
• HMirror: Mirror points relatively to horizontal axis

Cpolyline poly;
// ... fill with points
poly.rotate( Rotate::CW ); // or free function: rotate( poly, Rotate::CW );

These operations are done relatively to the origin (0,0). If you need a rotation on a specific plane location, you may pass that location as second argument:

Cpolyline poly;
// ... fill with points
Point2d org( ..., ... );
poly.rotate( Rotate::CW, org ); // or free function: rotate( poly, Rotate::CW, org );

The member function setParallelogram() takes 3 points (may be of different floating-point types) and builds the corresponding parallelogram by computing the missing 4th point. Is only available for "closed" type.

(source)

The member function set( dist, nb ) will build a Regular Convex Polygon of nb points, that will be at a distance dist from center. The center will always be (0,0), and the first point will always be at (dist,0).

If some translation is needed, you can use the translate() member or free function, see the related constructor.

This function returns a std::pair holding two numerical values: the distance between two consecutive points as "first", and "second" the radius of the inscribed circle.

The minimum value for nb is 3 (will generate an equilateral triangle), the function will throw if less.

source

If the symbol HOMOG2D_USE_BOOSTGEOM is defined (see build options), you can import a Polyline from a boost Polygon type. See demo program that demonstrates that feature.

We follow here the traditional parametrization of ellipses: center point, semi-major (a) and semi-minor (b) distances, and angle between main axis and horizontal axis. Internally, it is stored as a conic in its matrix form (see build options for details).

Warning: support for ellipse is only partial at present, several features available with all the other primitives may not all be available for this type

It can be build using several constructors:

Ellipse ell;  // centered at (0,0), with null angle, major=2 minor=1
Ellipse ell2( x0,y0 ); // same as above, but centered at (`x0`,`y0`)
Point pt( ..., ... );
Ellipse ell3( pt ); // same as above, but centered at `pt`
Ellipse ell4( pt, major, minor, angle ); // all parameters given (angle has 0 as default value)
Circle cir;
Ellipse ell5( cir );  // can be initialized from a circle

Retrieving attributes (The perimeter function has the name "length" for consistency with the other primitives):

Ellipse ell;
auto center  = ell.center(); // or: center(ell)
auto angle   = ell.angle();  // or: angle(ell)
auto area    = ell.area();   // or: area(ell)
auto perim   = ell.length(); // or: length(ell)

auto majmin  = ell.getMajMin();  // returns a pair of floating point values

Two functions are provided to get the bounding box: as with the others primitives, the getBB() member function returns the "flat" bounding box, while the getOBB() returns the "oriented" bounding box as a closed polyline object.

These are also available as free functions:

Ellipse ell;
auto bb  = getBB(ell);
auto obb = getOBB(ell);

You can get the pair of axis lines:

Ellipse ell;
auto pair_lines  = ell.getAxisLines();
auto pair_lines2 = getAxisLines( ell ); // or use the free function

To check if the ellipse is a circle:

Ellipse ell;
bool b = ell.isCircle();

(An ellipse will be a circle if a=b, but as it is stored in the matrix form, we check here if A=C and B=0.

This will use a threshold, but you can provide the one you want, depending on your applications constraints:

Ellipse ell;
bool b = ell.isCircle(1E-15);

There is also a free function available:

bool b1 = isCircle( ell );
bool b2 = isCircle( ell, 1E-15 );

You can manipulate 2D transformations as 3x3 homogeneous matrices (aka "Homography"), using the class Homogr.

Homogr h; // unit transformation ("eye" matrix)
h.setTranslation(3,4);
Point2d pt1(1,2);
Point2d pt2 = h * pt1; // pt2 is now (4,6)
h.init(); // reset to unit transformation

This can also be used with all the other types (Segment, FRect, OPolyline, CPolyline, Circle, Ellipse):

Homogr h;
 ... assign some planar transformation
Segment s1( ..., ... );
auto s2 = h * s1;

Polyline pl;
pl = h * pl;

auto a = h * rect; // a is a CPolyline

It must be noted that due to the inherent projective nature of a homography, applying to a flat rectangle will not produce a rectangle but a CPolyline. Similarly, applying a homography to a Circle will generate an Ellipse object:

FRect r1;
auto r2 = Homogr() * r1;
Circle c1;
auto c2 = Homogr() * c1;
cout << "r2 type=" << getString( r2.type() ) << '\n'; // will print "CPolyline"
cout << "c2 type=" << getString( c2.type() ) << '\n'; // will print "Ellipse"

For lines, a known result is that if we have a line lA going through p1 and p2, and a homography H mapping p1 and p2 to p'1 and p'2, then the line lB joining these two points can be computed with lB = H^-T lA.
Since release 2.4, this library automatically handles this inversion, inside the class:

Homogr h;
 ... assign some planar transformation
Point2d p1a( ..., ... );
Point2d p2a( ..., ... );
Line2d lA = p1a * p2a;
auto p1b = h * p1a;
auto p2b = h * p2a;
lB = h * lA; // same as lB = p1b * p2b;

The three planar transformations (rotation, translation, scaling) are available directly through provided member functions. They are available in two forms: "setXxxx()" and "addXxxx()". The first one starts from the identity transformation and builds the requested one. The second form adds the requested transformation to the matrix.

• You can create a rotation or a scale transformation with one of these:

Homogr h;
h.setRotation( 3.14 ); // angle of PI radians
h.setScale( 2., 3. ); // discard previous rotation, and set horizontal scale factor to 2. and vertical to 3.

• You can build some complex transformation by multiplying these:

Homogr h; // unit transformation
h.setTranslation(3,4);
Homogr h2( 45. * M_PI / 180.); // 45° rotation matrix
auto h3a = h1*h2; // first, rotation, then translation
auto h3b = h2*h1; // first, translation, then rotation

• Or by calling dedicated member functions:

Homogr h;
h.addRotation( 3.14 );       // angle of PI radians (would be identical with "set")
h.addScale( 2., 3. );        // add scaling transformation
h.addTranslation( 0., 4. );  // add translation

• But you can also used "chained" syntax:

Homogr h; // unit transformation
h.addTranslation(3,4).addRotation( 45. * M_PI / 180.).addTranslation(-3,-4);

• You can access individual values of the matrix (read or write). This is needed if you want to set up some specific transformation (shearing, perspective, whatever):

h.set( 0, 0, 3.14 );  // sets value at first line, first col
auto v = h.get( 0, 0 ); // 3.14

To fill the matrix with arbitrary values, the best is to build it from a "vector of vectors", as in the example below:

std::vector<std::vector<float>> m = {
	{ 1,  0,  2 },
	{ 0,  1, -1 },
	{ 0,  0,  1 }
};
Homogr F = m;

You can also use std::array if needed.

• You can compute the inverse and/or the transpose of the matrix:

h.inverse();
h.transpose();
h.inverse().transpose(); // first, invert, second, transpose

(note: inversion is done by first computing its corresponding adjugate matrix.)

• Once you have set up your matrix, you can apply it to points (or lines), using the * operator:

Homogr F; // set up some transformation
Point2d p1;
Point2d p2 = H * p1;

• You don't even need to create a variable, you can build one "on the fly" for translations and rotations:

p1 = Homogr(50,100) * p1;   // translation
p2 = Homogr(M_PI/4) * p2;   // rotation

This is possible for all the primitives accepting a homography product.

• More complex stuff is possible too, without creating a variable:

p1 = Homogr().addTranslation(50,100).addScale(2) * p1;

• You can apply the homography to a set of points or lines:

std::vector<Point2d> v_pts;
... // fill with values
h.applyTo( v_pts );

This actually works with any other container on whom one can iterate, such as std::array or std::list.

• Or you may use the * operator to achieve the same result:

std::vector<Point2d> v_in;
... // fill with values
auto v_out = h * v_in;

Thanks to templates, this works also for a set of points (or lines) stored in a std::list or std::array.

Once you have the desired matrix, you can apply it to about anything you want. For example, here is a rotating polygon, with its bounding box and intersection points with a crossing line (see showcase3.cpp).

Four constructors are provided:

• one without arguments, that initializes the matrix to a unit transformation;
• one with one floating point argument, that produces a rotation matrix of the given angle value;
• one with two floating point arguments, that produces a translation matrix with the given values;
• the last one can be used to fill the matrix with a 2-dim container (std::vector<std::vector<numeric_type>> or std::array<std::array<numeric_type,3>,3>).

Homogr Hr( 1. ); // rotation matrix of 1 radian
Homogr Ht( 3., 4. ); // translation matrix of tx=3, ty=4
std::array<std::array<numeric_type,3>,3> ar;
// ... fill array
Homogr Ha( ar );

You can also compute the transformation from two sets of 4 (non-colinear) points:

std::vector<Point2d> v1(4); // "from" points
std::vector<Point2d> v2(4); // "to" points
... // fill v1 and v2
H.buildFrom4Points( v1, v2 );
auto H2 = buildFrom4Points( v1, v2 ); // or use the free function

For example, the following code:

	std::vector<Point2d> v1 { {20,20}, {250,20}, {230,170}, {60,190} };
	std::vector<Point2d> v2 { {60,60}, {280,50}, {220,150}, {90,130} };
	auto H = buildFrom4Points(v1, v2);
	std::cout << H;

will produce this matrix:

| 0.347509   0.140962     48.967  |
| -0.147718  0.510036     51.4901 |
| -0.0021031 0.00105012    1      |

However, this requires the solving of a linear system of 8 equations with 8 unknowns (i.e. computing the inverse of a 8x8 matrix). This task does not enter in the scope of this library, thus we rely on others ones to do this. The consequence is that this feature is ONLY AVAILABLE if one of the two options below are available on system at build time.

The two options available are:

• Opencv (https://opencv.org)
• Eigen (https://eigen.tuxfamily.org/)

The default is Opencv, thus it will fail to build if not installed on system (check out bindings for more on this). However, if none of these are installed on you system, the easiest to install is with no doubt Eigen, as it is a header-only library.

The member function buildFrom4Points() accepts as third argument an int, 0 means using Opencv, 1 means using Eigen.

This library has a homogeneous API for all intersections between the provided geometrical primitives. That is, whatever a and b (excepts points of course), there is a member function intersects() that both gives the answer to the question "do theses primitives intersect?" but also provides the intersections points.

If you are only interested in the first answer, you can write:

	if( a.intersects(b)() )  // or b.intersects(a)()
	 ... then do something

If you need the intersection points, then just store the returned value:

	auto res = a.intersects(b);  // or b.intersects(a)
	if( res() )           // does intersect !
	{
		std::cout << "number of intersections: " << res.size() << '\n';
		auto pts = res.get(); // get the points
	}

The number of intersection points will depend on the primitives, thus the access method (get()) will return different types. It will also throw if there is no intersection! And whatever the primitives, you can always get the number of intersection points with the size() member function.

The table below summarizes the number of intersection points to expect:

• For line-line and line-segment intersections, the get() member function will return the unique intersection point, or throw if none.
• For the other situations, the get() member function will return a std::vector holding the points (empty if no intersections).

For Polyline, the number of intersections is of course depending on the number of segments.

See the provided demo for a runnable example (relies on Opencv backend).

For the functions returning a pair of points, the returned pair will always hold as "first" the point with the lowest x value, and if equal, the point with the lowest y value.

For details on the algorithms involved, check this page.

When a segment has a point lying on another segment, such as in the figure below, this will be considered as an intersection point:

This has a consequence on rectangle intersections: when the rectangles are overlapping such as the figure below, we will have here 4 intersection points.

Similarly, in the situation as in the figure below, we will have 2 intersection points:

This library provides an answer to the question: "is this object inside this other object?", whatever their type. In many cases, the question doesnt really make any sense (a point cannot be inside a point, nor can a line be inside a segment), but to have a homogeneous interface, the code a.isInside(b) will always compile. In the nonsense situations described above, it will simply return false (as a constexpr value).

Note: these functions use a strict condition: if point is on an edge, it will not be considered as inside the other object.

The table below summarizes what type (lines) can be used to check if it is inside another object of same or different type (columns).

• F: (constexpr) false
• T/F: true or false
• NI: Not Implemented (yet), returns false

You can compute the rectangle corresponding to the intersection of two (flat) rectangles: one can use either the intersectArea() member function or (same name) free function, or the & operator. This will return an object that can be checked for with the () operator (returns a bool). It will return false if there is no intersection.

auto a1 = r1.intersectArea(r2);
auto a2 = r1 & r2;
auto a3 = intersectArea( r1, r2 ); // free function
if( a1() )
	std::cout << "common area is " << a1.get(); // prints the FRect object of the intersection

For the union of two rectangles, the usage is similar, but it will return a (closed) Polyline object. You may use either the unionArea() (member or free) function, or the | operator. And there is no get() function, as you will always get a valid Polyline object.

auto b1 = r1.unionArea( r2 );
auto b2 = r1 | r2;
auto b3 = unionArea( r1, r2 ); // free function
std::cout << "union is " << b1.get();

Additionaly, the getBB() free function returns the bounding box holding the two rectangles, as shown in gray in the two examples below.

Note that we may not have an intersection area even if there are some intersection points found, because these can be due to a shared segment, or a single intersection point.
For the union, if there is no intersection, the function will return an empty CPolyline object.

If one rectangle is inside the other one, then the union will return the largest rectangle (as a Polyline object), ant the intersection will return the smallest one.

For conveniency, a function IoU() is provided. It computes the ratio of the area of the intersection of two rectangles over the area of the union of these two rectangles. See this WP page where this is described. This page from OpenCV also provides all the details.

You can compute the convex hull of a set of points that are stored in a standard container (std::vector, std::list, or std::array) with the convexHull() free function. This function will return a CPolyline object. This function can also take a Polyline (CPolyline or OPolyline) object as input:

std::vector<Point2d> vec;
// ... fill with at least 3 points
auto ch1 = convexHull( vec );
CPolyline pl( vec );
auto ch2 = convexHull( pl ); // will be the same as ch1
auto ch3 = pl.convexHull(); // member function

CH of a set of points	CH of a Polyline

source code included

You can compute the Bounding Box of a set of objects that lie in a container, whatever that container type (std::vector, std::list or std::array). This function will return a FRect object:

std::vector<Point2d> vec;
// ... fill with at least 2 points
auto bb = getBB( vec );
draw( img, vec );
bb.draw( img );

This function will throw if the returned rectangle ends up in an invalid state. This means that for points or segments, the container's size needs to be at least 2. For polylines, circles and rectangles, the size needs to be at least 1.

However, as the returned rectangle may not have a null area, this function will throw if the container holds objects on which no bounding box can be defined. For example, if the container holds 3 identical points. Or even different points, but sharing a identical x or y coordinate (think: [0,0]-[0,5]) The same situation may occur with segments, for example a container holding these two segments: [0,0]-[0,5] and [0,10]-[0,20].

Examples (generated with this file):

For points, the Top-most and Left-most point are shown in green, and the Right-most and Bottom-most points are shown in blue (see next section about this).

Note: this function also works for containers holding "variant" type objects (CommonType), see RTP section.

Given a set of points in a container (std::vector, std::list or std::array), you can get the Top-most / Bottom-most / Left-most / Right-most point with a simple call to one of these:

std::vector<Point2d> vec { ... fill with points... };
auto pt_L = getLmPoint( vec );                  // Left-most
auto pt_R = getRmPoint( vec );                  // Right-most
auto pt_T = getTmPoint( vec );                  // Top-most
auto pt_B = getBmPoint( vec );                  // Bottom-most

Or use the generic function with a CardDir value (see here for that enum definition).

std::vector<Point2d> vec { ... fill with points... };
auto pt_R = getExtremePoint( Card::Right, vec );      // Right-most

see here for Polyline equivalent functions

For an example, see previous section.

You can check if three points lie on the same line with this:

bool b = areCollinear( pt1, pt2, pt3 );

Say you have container (std::vector or std::array) holding a bunch of points. Three functions allow you to find among these wich one is the closest or the farthest to a given point.

Point2d SomePoint( ...,...);
std::vector<Point2d> vpts;
// fill vector
auto idx1 = findNearestPoint( SomePoint, vpts );
cout << "nearest point is " << vpts[idx1] << '\n';
auto idx2 = findFarthestPoint( SomePoint, vpts );
cout << "farthest point is " << vpts[idx2] << '\n';

If you need to get both:

auto pidx = findNearestFarthestPoint( SomePoint, vpts );
cout << "nearest point is " << vpts[pidx.first]
     << ", farthest point is " << vpts[pidx.second] << '\n';

(or you could of course call the two previous function sequentially.)

see showcase

If you have a container (std::vector, std::list or std::array) holding either segments, circles or ellipses, you can get at once all the center points, grouped in a vector:

std::vector<Circle>  vec1;
std::vector<Segment> vec2;
std::vector<Ellipse> vec3;
 ... fill these
auto v1 = getCenters( vec1 );   // v1, v2, v3 hold a vector of Point2d
auto v2 = getCenters( vec2 );
auto v3 = getCenters( vec3 );

Similarly, if you have a container holding segments, you can get at once all the supporting lines:

std::list<Segment> vec;
 ... fill vec
auto v_lines = getLines( vec );

Besides the type conversions described here, a more general binding is provided with the ttmath library. It allows increasing range and precision of numerical values. See here for details.

Import from other types is pretty much straight forward. For points, a templated constructor is provided that can be used with any type having an 'x' and 'y' member. For example, say you have a point type:

struct MyPoint
{
	float x,y;
};

Then you can build a point (or a line going through (0,0) and that point) with:

MyPoint myPoint;
Point2d pt(myPoint);
Line2d li(myPoint);

But in case your type uses other identifiers than x and y, no problem: just define the symbol HOMOG2D_BIND_X and HOMOG2D_BIND_Y with the ones you use and the above code will be ok.

For homographies, you can import directly from std::vector<std::vector<T>> or std::array<std::array<T,3>,3>.

For the first case, it is mandatory that all the vectors sizes are equal to 3 (the 3 embedded ones and the global one).

For points, as long as the other type provides a 2-args numerical constructor, you can easily convert a h2d::Point2d into these, for example:

Point2d pt;
...
auto ptcv = pt.getPt<cv::Point2d >();                     // of free function: getPt<cv::Point2d >(pt);
auto ptbg = pt.getPt<boost::geometry::model::point_xy<double>>();

This is also possible for a std::vector:

std::vector<Point2d> vin;
// ... fill vin
auto vec1_out = getPts<cv::Point2d>(vin);                       // convert to a vector of Opencv points
auto vec2_out = getPts<boost::geometry::model::point_xy<float>>(vin); // convert to a vector of boost geometry points

Optional functions are provided to make interface with Opencv easier. These features are enabled by defining the symbol HOMOG2D_USE_OPENCV at build time, before "#include"'ing the file. You can then write this:

Point2d pt;
...
cv::Point2d ptcv1 = pt.getCvPtd(); // double coordinates
cv::Point2f ptcv2 = pt.getCvPtf(); // float coordinates
cv::Point2i ptcv3 = pt.getCvPti(); // integer coordinates

This is also available as free functions:

Point2d pt;
...
cv::Point2d ptcv1 = getCvPtd(pt);
cv::Point2f ptcv2 = getCvPtf(pt);
cv::Point2i ptcv3 = getCvPti(pt);
...
auto ptcv3 = getCvPt<cv::Point2d>(pt); // templated version

Reverse operation as simple as this:

cv::Point2d ptcv(4,5);
Point2d pt1(ptcv);      // using constructor
Point2d pt2 = ptcv;     // or assignment operator

(works the same for cv::Point2f and cv::Point2i)

Similarly, you can build a line using Opencv points:

cv::Point2d ptcv(4,5);
Line2d l1( ptcv );                     // line going trough (0,0) and (4,5)
Line2d l2( ptcv, cv::Point2d(8,9) );   // line going trough (4,5) and (8,9)

This also enables conversions between matrices types. You can build a homography using a provided cv::Mat:

cv::Mat m;   // needs to be 3x3, floating point type (either CV_32F or CV_64F)
... // fill m
Homog H = m;  // call of dedicated constructor
H = m;        // or call assignment operator

From release 2.10, a preliminar binding is provided with Boost Geometry. It can be used to import Boost point types, or boost polygons. This is made available by defining the symbol HOMOG2D_USE_BOOSTGEOM.

You may build a point using either of the two point types:

namespace bg = boost::geometry;
bg::model::point<double, 2, bg::cs::cartesian> pboost_1;
bg::model::d2::point_xy<double> pboost_2;
...
Point2d p1(pboost_1);
Point2d p2(pboost_2);
p1.set(pboost_1);     // this works too
p2.set(pboost_2);

The Cpolyline and OPolyline types have a constructor that takes a Boost polygon as argument. See a demo in this file.

Exporting of points to the Boost point types is also possible, if that latter type is Cartesian and has 2 dimensions (free or member function):

using boost_point = bg::model::point<double, 2, bg::cs::cartesian>;
Point2d pt( ..., ... );
boost_point bpta = pt.getPt<boost_point>();
boost_point bptb = h2d::getPt<boost_point>(pt);

This library provides a way to render data graphically, using two backends. However please note that this is not a "high-end" drawing tool, the rendering has no extended fine-tuning on how things are rendered, the goal is only to quickly see what is going on.

The user can select between two backends, both can be usable at the same time. They both are accessed through the templated datatype Image, lying in the sub-namespace img.

The two concrete types that can be used with Image are either img::SvgImage, to generate a SVG file, or Opencv cv::Mat type, that requires that the symbol HOMOG2D_USE_OPENCV is defined and that the library is installed on system.

The difference between these two backends is that with SVG, you may only generate a file; with OpenCv, you can build an interactive app, through the "HighGui" part of that library, whith mouse and keyboard callbacks. This is demonstrated in a provided demo program that you can try with:

$ make demo

This requires that Opencv is installed on your machine. In case you have some trouble building this program, please read this.

To have an idea, here are two renderings of the same objects done with the two backends (done with this program.)

SVG rendering	OpenCv rendering

Generic drawing member functions are provided for all the types. For example, creating a SVG file in current folder, holding a circle:

img::Image<img::SvgImage> im1( 300, 400 ); // 300 x 400 pixels
Circle c1( 100,100,80 );
c1.draw( im1 );
im1.write( "circles1.svg" );

Same, using Opencv to create a png file:

img::Image<cv::Mat> im2( 300, 400 );
Circle c2( 100,100,80 );
c2.draw( im2 );
im2.write( "circles2.png" );

A corresponding free function is available, can be used for any type:

Point2d pt(100,100);
Circle c( pt,80 );
draw( img, c );
draw( img, pt );

If you use Opencv, you might need the cv::Mat object for other tasks. It is available with the getReal() member function that returns a reference on that object (const or not):

img::Image<cv::Mat> img( 300, 400 );
cv::Mat& ocv = img.getReal()

You can draw text with the drawText() free or member function, with either Opencv or Svg backend:

img::Image<cv::Mat> im( 300, 400 );
Point2d loc( x, y );
drawText( im, "Some Text", loc );  // or: im.drawText( "Some Text", loc );

All these drawing functions (member and free function) support an additional optional argument of type img::DrawParams, also back-end library independent. that holds various parameters for drawing. It holds several member functions that allow to tweak the drawing parameters. All of these functions support the "chained-call" syntax.

So you can for example set the color and line width with:

li.draw( img, img::DrawParams().setThickness(2 /* pixels */).setColor(r,g,b) );

with r,g,b as bytes (uint8_t) in the range [0,255].

A local type holding these 3 values can also be used:

auto c = img::Color(255,0,222);
li.draw( img, img::DrawParams().setColor(c) );

The drawing parameters default values can be changed anytime with a call to setDefault(), and values will be retained, unless explicitely changed, as showed in the example below;

img::DrawParams dp;                                        // default line thickness is 1
dp.setColor( 0,  0, 250 ).setThickness(3);
dp.setDefault();                                        // default is now blue, with thickness=3
line.draw( img );                                  // use default settings (blue,...)
line.draw( img. img::DrawParams().setColor( 0,0,0) ); // warning, black, but line thickness=3 !

You can at any time return to the "factory" settings with a call to a static function:

img::DrawParams::resetDefault();

You can also save a style in a variable, to avoid lengthy lines:

auto color_red = img::DrawParams().setColor( 250, 0, 0 );
something.draw( img, color_red );

The available functions are given in the table below:

The following table shows the rendering of the different point styles (PtStyle), with the OpenCv and SVG backend, with width (setThickness()) set to 1 and 2.

width	png (OpenCv)	Svg
1
2

source

For Svg back-end only, the user can add some specific Svg attributes with setAttribString(). For example:

FRect r( 100,100,200,200);
r.draw( im, DrawParams().setAttrString("fill=\"rgb(100,200,150)\"") );

Make sure you add valid attributes, check here.

For Opencv back-end, this is ignored.

If you have a container (std::vector, std::array or std::list) filled with one of the primitives or a std::pair of primitives (can be different types), you can draw them at once with a call to the same free function draw():

std::vector<Segment> vseg;
// ... fill vseg with data
std::pair<Circle,FRect> pair;
// ... fill the pair
draw( img, vseg );      // use default parameters
draw( img, vseg, dp );  // pass some drawing parameters
draw( img, pair );      // draw the pair circle, rectangle
draw( img, pair, dp );  // you can even pass drawing parameters

For containers, a second generic function is provided that has as third argument a std::function. This is useful to enable having different drawing properties (think: color) for each element of the set:

void draw( img::Image<U>& img, const T& cont, std::function<img::DrawParams(int)>& func )

The passed function must return a valid img::DrawParams object. It may be build depending on the index of the object.

A typical example would be:

std::vector<Segment> vseg;
/// fill vseg with data
std::vector<Color> vcol( vseg.size() );
/// fill vcol with colors

auto fl = [&](int i)   // lambda
{
	return img::DrawParams().setColor( vcol[i] );
};
std::function<DrawParams(int)> func(fl);
draw( img, vseg, func );

Checkout here to see an example. A helper function img::genRandomColors() is provided, it will return a vector of img::Color objects filled with random RGB colors. For example:

auto vcol1 = img::genRandomColors(10);        // return 10 random colors with values in the range [20-250]
auto vcol2 = img::genRandomColors(10,100);    // return 10 random colors with values in the range [100-250]
auto vcol3 = img::genRandomColors(10,30,150); // return 10 random colors with values in the range [30-150]

The library is fully templated, the user has the ability to select for each type either float, double or long double as underlying numerical datatype, on a per-object basis.

The default datatype used for all the primitives (Point2d, Line2d, Homogr, Segment, FRect, Circle, Polyline, Ellipse) is double. The other types can be selected by an additional suffix letter added after the type:

F for float, D for double and L for long double.

For example: Point2dF, Line2dF or SegmentF are float types.

If you prefer the classical template notation, it is also available by adding an underscore after the type:

Point2d_<float> ptf;
FRect_<double> rectd;
Segment_<long double> sld;

However, this only applies to storage. All the computation (distances, angles, intersections, ...) use (and returns) the type defined by symbol HOMOG2D_INUMTYPE, that defaults to double.

If you need extra precision (and if your compiler supports it), you may configure the library to use long double by adding this before the "include":

#define HOMOG2D_INUMTYPE long double

or add that as a compile flag: $(CXX) $(CXXFLAGS) "-DHOMOG2D_INUMTYPE long double" ...
(don't forget the quotes!)

For any object, you may know its underlying floating-point type with the dtype() (member or free) function. It will return an enum value of type Dtype, either Dtype::Float, Dtype::Double or Dtype::LongDouble.

It can be printed out for humans with getString(), this will print "Float":

Circle c1;
assert( c1.dtype() == Dtype::Double );
CircleF c2;
assert( dtype(c2) == Dtype::Float );
std::cout << getString( dtype(c2) );

You may also check the size in bits of corresponding mantissa and exponent with the (member of free) function dsize() (assuming IEEE754 implementation). It will return a std::pair of integers, the first being the size of the mantissa, the second being the size of exponent.
(Also works for "big numbers", see below ).

Circle c1; // default is double
assert( c1.dsize().first == 53 );
assert( dsize(c1).second == 10 );

It is possible to convert to/from an object templated by a different type (at the cost of a potential precision loss):

Point2dD pt_double;
Line2dL  li_long;
Point2dF pt_float  = pt_double;
Line2dD  li_double = li_long;
SegmentD sd;
SegmentL sl = sd;

For the tests on null values and floating-point comparisons, some compromises had to be done. As you may know, the concept of "equal floating point values" is very tricky. In this library, this can hurt in several ways:

• creating a line from two points will fail if the points are equal,
• similarly, computing a point at the intersection of two lines will fail if the lines are parallel.

This library will ensure these conditions, and will throw an exception (of type std::runtime_error) if that kind of thing happens. The thresholds all have default values. They are implemented as static values, that user code can change any time.

More details and complete list on threshold page.

From release 2.10, there is a preliminar support for the ttmath library, that enables selecting the number of machine words for both mantissa and exponent. This can improve both precision of computation and maximum size of numbers, as it can extend the maximum size allowed by the standard type long double. This library is header-only, so its very simple to install.

To enable this, you need to define the symbol HOMOG2D_USE_TTMATH. This will also define a default value for HOMOG2D_INUMTYPE (internal numerical type)as ttmath::Big<2,2>. This definition means that both mantissa and exponent will be stored as 2 machine words. On a 64-bit platform, that will end up as 128 bits for both.

This can be overridden,

• either by another definition of HOMOG2D_INUMTYPE as default types. For example, to have 2 machine words for exponent and 3 for mantissa as default, you can add this on top of your file:

#define HOMOG2D_INUMTYPE ttmath::Big<2,3>

• or individually for each object. For example:

	Circle_<ttmath::Big<4,1>> circle;

The downside is that once the symbol HOMOG2D_USE_TTMATH is defined, you cannot use anymore the "standard types" (float, double, long double).

See this file for example.

Please note that you will probably need to adjust the relevant thresholds according to you choice of precision, see the threshold page.

For more on how this is handled in the code, see here.

A minimal SVG import code is present, it relies on the well-known tinyxml2 library, thus it needs to be present on machine to build an application using this feature.

On Debian-based distros, this can be easily done with $ sudo apt install libtinyxml2-dev

To enable its usage in your code, you need to do two things:

• define the symbol HOMOG2D_USE_SVG_IMPORT before including homog2d.hpp
• add the library to the build process. That can be done by adding this to the linking command-line:

$(pkg-config --libs tinyxml2)

(double the $ if in a makefile)

Importing is pretty simple: Instanciate a Tinyxml XMLDocument object, and use it to read the file. Then create a "visitor" object, and fetch a vector of the objects in the file:

tinyxml2::XMLDocument doc;
doc.LoadFile( "filename.svg" );

h2d::svg::Visitor visitor;
doc.Accept( &visitor );
auto data = visitor.get();

The latter function returns a vector of polymorphic objects CommonType. This is a wrapper around a std::variant, on which the library provides some helper functions. See RTP section on how to use this.

This polymorphic behavior is kept optional see here for more details. It is enabled only if symbol HOMOG2D_ENABLE_VRTP is defined (which is automatically done if HOMOG2D_USE_SVG_IMPORT is defined).

You can fetch the size of image in the SVG file (as double) with getImgSize(). However, this will throw if no size can be found, so you might consider using that in a "try/catch":

std::pair<double,double> imSize(500.,500.); // default size
try
{
	imSize = svg::getImgSize( doc );
	std::cout << "size: " << imSize.first << " x " << imSize.second << '\n';
}
catch( const std::exception& error )
{
	std::cout << "input file has no size, size set to 500x500\n -msg=" << error.what() << '\n';
}

When importing a SVG file, the following points must be considered:

• All the color, style,etc. Svg attributes present in file are lost, as this library does not store them.
• All groups (<g> tags) are ignored.
• Svg has no "line" object, what is called a line is actually a segment and it will be imported as such.
• Svg has no "point" object, thus it cannot be imported. However, if you try to import a file that was created with the Svg drawing subsystem, points will be plotted with a shape defined by its parameters.
• Svg has two ways to define a polyline (or polygon): either with the dedicated keywords (polyline or polygon), or by using the path element, that is much more general. This import subsystem handles all three of these. However, for the "path", the "curve" elements (SVG path commands C, S, Q, T) are not handled, the import code will just ignore thoses commands, if encountered while importing a SVG path object.
• When importing a SVG "path", it will be automatically converted to a CPolyline or a OPolyline, depending on the fact that it holds a z at the end of the SVG path "d" string.
• If you have trouble with some SVG file, a helper function printFileAttrib() is provided that will output all the SVG attributes of a file on stdout. See an example of its usage in file demo_svg_import.cpp.

SVG Reference: https://www.w3.org/TR/SVG2/shapes.html

If you have cloned the whole repo and have Tinyxml2 installed, you may build a demo program with:
$ make demo_import

This will build the file BUILD/demo_svg_import (source here) that will import any SVG file, print its content on screen (SVG general attributes and number of shapes), and generate another svg file demo_import.svg in current folder.

For example:
$ BUILD/demo_svg_import docs/img/comparison_1.svg

The previous line imports a file that has been generated by this library, so to have comething more realistic, you can run this:
$ BUILD/demo_svg_import misc/test_files/France_Normandy.svg

• The two types Point2d and Line2d are actually two typedefs of class base::LPBase, behavior differs due to some policy-based design. Similarly, the types CPolyline and OPolyline (Closed and Open polyline) are specializations of the root class base::PolylineBase.
• Points are stored as non-normalized values, except for the sign: the first value will always be positive. So the point [-1,1,1] will be automatically converted to [1,-1,-1]. Besides that, any computation will keep the resulting values.
• Lines are always stored as normalized values (a^2+b^2 = 1)
• Homographies are stored as normalized values, either as h33=1, or (if null) as h23=1, or (if null) as h13=1

For more details on the code, check this page.

A unit-test program is included, can be run locally and is also used by GitHub CI. It is uses the Catch2 library. The Github CI loads the 2.13.6 release. It is build and run with $ make test The CI launches the tests with both Ubuntu 20 (gcc9.4) and Ubuntu 22.

If you have Opencv installed on your machine, you can run the additional tests that make sure the Opencv binding stuff runs fine by passing make option USE_OPENCV=Y:

make test USE_OPENCV=Y

Similarly, if you have Tinyxml2 installed, you can run the additional SVG import tests by passing this flag:

make test USE_TINYXML2=Y

A second test target is included: $ make testall. It will build and run the test program 3 times, one for each numerical data type (float, double, and long double), through the symbol HOMOG2D_INUMTYPE.

The test target also attempts to build the files in the folder misc/no_build. These demonstrate some code that should NOT build, thus Make will fail if any of these does build. This is just to make sure that some invalid code does, indeed, not build.

Timing Using the Catch v2 library has a small drawback: build time is pretty long (but will succeed!). For example:

$ time make test -j2
real   0m41,986s
user   1m21,940s
sys    0m1,699s

Below are some options that can be passed, to activate them, just define the symbol. You can do that in the makefile by adding -DHOMOG2D_SYMBOL to the compiler call options, or just add a #define on top of your program before the #include "homog2d.hpp"

• HOMOG2D_USE_OPENCV: enable the Opencv binding, see Bindings.
• HOMOG2D_USE_EIGEN: enable the Eigen binding, useful if you need to compute a homography from points and Opencv not available (see here).
• HOMOG2D_USE_SVG_IMPORT: enables importing from svg files, requires Tinyxml2 library, see SVG import.
• HOMOG2D_USE_BOOSTGEOM: enables the binding with Boost::geometry (preliminar), see example here.
• HOMOG2D_USE_TTMATH (preliminar): this will enable the usage of the ttmath library, to increase numerical range and precision. See here for details.

• HOMOG2D_NOCHECKS: will disable runtime checking. If not defined, incorrect situations will throw a std::runtime_error. If defined, program will very likely crash in case an abnormal situation is encountered.

• HOMOG2D_NOWARNINGS: on some situations, some warnings may be printed out to stderr (see below). Defining this symbol will disables this.

• HOMOG2D_OPTIMIZE_SPEED: this option may be useful if you intend to to a lot of processing with ellipses, and you favor speed over memory. The default behavior for class Ellipse is to store only the homogeneous matrix representation (conic form),to minimize memory footprint. This drawback is that every time we need to access some parameter (say, center point), a lot of computations are required to get back to the "human-readable" values. With this option activated, each ellipse will store both representations, so access to values is faster. For more on this, see this page.

• HOMOG2D_ENABLE_PRTP: enables pointer-based runtime polymorphism. This will add a common base class rtp::Root to all the geometric primitives. At present, runtime polymorphism is currently moving to a variant-based approach, see RTP section.

• HOMOG2D_ENABLE_VRTP: enables variant-based runtime polymorphism. This will add a class rtp::CommonType holding all the geometric primitives as a std::variant. See section RTP for details.

• HOMOG2D_DEBUGMODE: this will be useful if some asserts triggers somewhere. While this shoudn't happen even with random data, numerical (floating-point) issues may still happen, read this for details.

Situations that will generate a warning

• When computing the angle between two lines/segments, and that this requires the computation of arccos() of a value slightly above 1. Then the value 1.0 will be used instead, but a warning will be generated.
• When importing a SVG file and an element in the file cannot be processed.

Runtime Polymorphism is the ability to store in a container (std::vector, std::list, ...) objects of different types and calling on those elements some free or member function. With this library, this is implemented using two different techniques, one with the classical pointer-based approach, and the other using a std::variant, enabled by upgrading to C++17.

At present, these two techniques can be used, they both have pros and cons, but the pointer-based approach might be shortly deprecated, So it is advised to use nowadays the "variant-based" technique, as it is more type-safe. And there is no feature available with the other approach that isn't available with the variant-based approach.

This is the "classical C++" technique: you store (smart)pointers of type Root in the container. All the geometric primitives will inherit from this (non-templated) class. That class (and its inheritance) will only exist if the symbol HOMOG2D_ENABLE_PRTP is defined:

std::vector<std::shared_ptr<rtp::Root>> vec;
vec.push_back( std::make_shared<Circle>(   Circle()  ) );
vec.push_back( std::make_shared<Segment>(  Segment() ) );
vec.push_back( std::make_shared<FRect>(    FRect()   ) );

You may then call one of the polymorphic member functions on each of them:

for( auto& e: vec )
{
	std::cout << getString(e->type())
		<< ": " << *e
		<< "\n  -area = "
		<< e->area()
		<< "\n  -length = "
	if( e->type() != Type::Line2d )
		std::cout << e->length() << '\n';
	else
		std::cout << "infinite\n";

Remarks:

• You may directly call the streaming operator (<<), the Root class takes care of redirecting to the correct class operator.
• Notice that if the object is detected as a line, the function length is not called. This is mandatory to avoid throwing an exception, as a line cannot have a finite length.

To do something more elaborate, you need to convert them using a dynamic cast:

if( e->type() == Type::CPolyline )
{
	auto pl1 = std::dynamic_pointer_cast<CPolyline>( e );
	std::cout << "Polyline has " << pl1->size() << " points\n";
}

At present, the only polymorphic member functions available:

• void draw( img::Image& ) (you may pass as second argument a img::DrawParams object)
• double length()
• double area()

Potential pitfall: there is no checking on the correct cast operation, it is up to the user code to make sure to cast the pointer to the correct type. Bad casting will very probably lead to a segfault.

Check test file homog2d_test_rtp_1.cpp for an example.

This feature is made available by defining the symbol HOMOG2D_ENABLE_VRTP. This will enable a templated common type CommonType_ that holds all the geometrical primitives, as a std::variant (requiring a move to C++17). It follows the naming conventions of primitives, so you can use CommonTypeF, CommonTypeD or CommonTypeL, with CommonType defaulting to HOMOG2D_INUMTYPE (double by default).

So you can now stack up different primitives in a container of that type:

std::vector<CommonType_<double>> vec;
vec.emplace_back( Circle() );
vec.emplace_back( FRect() );
vec.emplace_back( Point2d() );
...

To get the actual type of the object, you can call the free function type(), that will return an enum value of type Type having one of these values:
Point2d, Line2d, Segment, FRect, Circle, Ellipse, OPolyline, CPolyline. You can get a human-readable value ot the object type with getString(Type).

A set of functors to be used with std::visit() is available, lying in the fct sub-namespace (see here). But the easyest is probably to use the associated free functions, so you don't have the hassle of functors.

For example, with the above vector, you can print their type, length and area with:

for( auto& e: vec )
{
	std::cout << getString(type(e))
		<< "\n -area=" << area(e)
		<< "\n -length=" << length(e)
		<< "\n";
}

(warning, the length() function will throw here if a Line2d is in the vector).

To draw these on an img::Image, you can do this:

fct::DrawFunct vde( im ); // or fct::DrawFunct vde( im, dp ); if you need to pass some drawing parameters
for( auto& e: vec )
	std::visit( vde, e );

To apply the same homography on each element (and store them in-place), simple as this:

auto h = Homogr().addTranslation(3,3).addScale(15); // whatever...
for( auto& e: vec )
	e = transform( h, e );

But you may also use the associated functors and std::visit() if you prefer:

fct::TransformFunct transf( Homogr().addTranslation(3,3).addScale(15) );
for( auto& e: vec )
	e = std::visit( transf, e );

If you need to get the object as its base type, a dedicated functor is provided:

if( type(e) == Type::Circle )
	Circle c = fct::VariantUnwrapper{e};

Check test file homog2d_test_rtp_2.cpp for an example.

• With the "variant-based" technique, a constraint is that all elements of a vector of CommonType will share the same underlying floating-point type. This constraint does not stand with the "pointer-based" technique.

• With the "pointer-based" technique, adding another (user) virtual function is quite complicated. As opposed to the "variant-based" technique, where it just requires writing a function in user code, that call the std::visit() function.