skramm / homog2d Goto Github PK

C++ 2D geometry library, handles points, lines, polylines, planar transformations (and other primitives), using homogeneous coordinates. Provided with complete manual and samples.

License: Other

Makefile 2.39% C++ 95.90% Shell 0.65% CSS 0.02% Gnuplot 0.56% TeX 0.49%

2d-geometric homogeneous-coordinates homography library 2d-transformations computational-geometry cpp geometry cpp17 cpp17-library

homog2d's Introduction

homog2d

Current test status:

A single-file header-only C++ library dedicated to handling 2D lines, points and homographies (2D planar transformations) in Cartesian geometry, using internally homogeneous coordinates. Also handles other geometric primitives, see full manual.

(see other demos here)

Language: C++14 or C++17
Home: https://github.com/skramm/homog2d
Usage: just fetch the file homog2d.hpp, put it somewhere, and "#include" it in your source file. No build!
Status: beta
Author: Sebastien Kramm, [email protected]
Licence: MPLv2

Short preview:

#include "homog2d.hpp"
using namespace h2d;
int main()
{
	Line2d l1( Point2d(10,10) );               // a line passing through (0,0) and (10,10)
	Line2d l2( Point2d(0,10), Point2d(10,0) ); // a line passing through (0,10) and (10,0)
	auto pt = l1 * l2;                         // intersection point (5,5)
	Homogr H(2,3);                             // a translation matrix
	std::cout << H * pt;                       // prints [7,8]
}

News

2024-04-21: switch to c++17, enable runtime polymorphism using std::variant, see here
2024-03-23: added SVG "path" element import
2023-12-26: fresh 2.11 release, see https://github.com/skramm/homog2d/releases
2023-11-17: added doc index
2023-07-11: added online Doxygen-generated reference, through the great https://codedocs.xyz/ see here
2023-02-19: 2.10 release, see https://github.com/skramm/homog2d/releases
2023-02-12: added support for "big numbers" through the ttmath library, see here) (preliminar!)

(see history for more)

Details

Install: to install on your machine, copy file homog2d.hpp somewhere where your compiler can reach it, or $ sudo make install after cloning repo. This will copy that file in /usr/local/include.
Audience: any C++ dev requiring some basic computational geometry, without the burden of large scale framework.
Usage: see full manual, or Doxygen-generated pages online.
Reference: once downloaded, enter $ make doc (requires Doxygen), or read online.
A test file is provided, needs Catch2. When installed, run $ make test (or $ make testall for testing with all 3 numerical types).
Contributing: at present, the best you can do is testing and bug/issue reporting. Don't hesitate, this is still beta but stable release expected soon.
Rationale:
- Usage simplicity, max flexibility
- No dependency (*)
- Modern C++, using policy-based design, tag dispatching, sfinae, ...
- Direct bindings with other libraries (OpenCv, Boost Geometry) (optional)
Geometric features:
- basic primitives: points, lines, segments, circles, rectangles, polygons, ellipse,
- planar transformation of any of these (rotation, translation, ...),
- computing of intersection points between these,
- enclosing determination
- ...
Related libraries:
- CGAL, the reference computational geometry library.
- Boost Geometry, a highly generic library with some overlapping features (but quite harder to use)
- Opencv, the reference CV library, much more algorithms, but no direct support for homogeneous geometry.
- Wykobi, has much more computational geometry features but no direct support for homogeneous geometry.

Warning: The images shown in the manual are there just there as an illustration of what the library does, but there is no rendering code included. The library provides drawing functions, that can be used to generate Svg files. An alternative is to use a supported third-party library (Opencv), but the latter is not needed to use this library.

(*): Except for some additional features, see manual.

homog2d's People

Contributors

Stargazers

Watchers

Forkers

linecode dseeni july-creater toge trisgelar rrjia alan0526 edelmanjm

homog2d's Issues

Compatibility with c++17

Today I officially start working in earnest with your great contribution, again thank you very much for this @skramm! 😘

But I've hit the first hurdle. Due to my other dependencies I need to work with C++17. However your library seems to have incompatibilities in this regard.

I am working with Visual Studio 2019 (Windows 10 x64).

When I try to build your "short preview" with the C++17 configuration I get the following errors.

>main.cpp
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(407,1): warning C4267: 'argument': conversion from 'size_t' to 'int', possible loss of data
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(417,1): warning C4267: 'argument': conversion from 'size_t' to 'int', possible loss of data
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): error C2244: 'h2d::Circle_<FPT1>::intersects': unable to match function definition to an existing declaration
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4573): message : see declaration of 'h2d::Circle_<FPT1>::intersects'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : definition
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_2,FPT> h2d::Circle_<FPT1>::intersects(const h2d::Circle_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : existing declarations
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::IntersectM<FPT> h2d::Circle_<FPT1>::intersects(const h2d::base::PolylineBase<PLT2,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::IntersectM<FPT> h2d::Circle_<FPT1>::intersects(const h2d::FRect_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_2,FPT> h2d::Circle_<FPT1>::intersects(const h2d::Circle_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::IntersectM<FPT> h2d::Circle_<FPT1>::intersects(const h2d::Segment_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(4574,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_2,FPT> h2d::Circle_<FPT1>::intersects(const h2d::base::LPBase<h2d::type::IsLine,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): error C2244: 'h2d::Segment_<FPT>::intersects': unable to match function definition to an existing declaration
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6435): message : see declaration of 'h2d::Segment_<FPT>::intersects'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : definition
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::Segment_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : existing declarations
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::base::PolylineBase<PLT2,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::FRect_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::Circle_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::base::LPBase<h2d::type::IsLine,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6436,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::Segment_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): error C2244: 'h2d::Segment_<FPT>::intersects': unable to match function definition to an existing declaration
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6474): message : see declaration of 'h2d::Segment_<FPT>::intersects'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : definition
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::base::LPBase<h2d::type::IsLine,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : existing declarations
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::base::PolylineBase<PLT2,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::FRect_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::IntersectM<FPT> h2d::Segment_<FPT>::intersects(const h2d::Circle_<FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::base::LPBase<h2d::type::IsLine,FPT2> &) const'
1>P:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\inc\homog2d\homog2d.hpp(6475,1): message : 'h2d::detail::Intersect<h2d::detail::Inters_1,FPT> h2d::Segment_<FPT>::intersects(const h2d::Segment_<FPT2> &) const'
1>Done building project "geometria_msvc2019.vcxproj" -- FAILED.

With the C++14 configuration however the same code seems to go smoothly, but it is not convenient for me due to my other dependencies. Is it possible to solve it? 😧

Thanks!!

DJuego

CPolygon enclosing not correctly detected

Hello,

First of, let me tell you that you have done really an impressive work.

I've just started using your library to check two things: 1. intersection between different polygons and between polygons and circles, and 2. enclosing of circles/polygons in polygons.

It worked flawlessly for almost everything, but I'm now facing a problem that I can't understand if it's a bug or if it's intended to be as this.

By reading the documentation, this part in particular, I was under the impression that it is possible to determine whether a polygon is enclosed within another.

But by running this code:

int main (){
  h2d::CPolyline rect(std::vector<h2d::Point2d>{
      h2d::Point2d(-2, 2),
      h2d::Point2d(-2,-2),
      h2d::Point2d( 2,-2),
      h2d::Point2d( 2, 2),
  });
  std::cout << "rect closed: " << rect.isClosed() << std::endl;

  h2d::CPolyline map(std::vector<h2d::Point2d>{
      h2d::Point2d(-5, 5),
      h2d::Point2d(-5,-5),
      h2d::Point2d( 5,-5),
      h2d::Point2d( 5, 5)
  });
  std::cout << "map closed: " << map.isClosed() << std::endl;

  std::cout << "map: " << map << std::endl;
  std::cout << "rect: " << rect << std::endl;

  std::cout << "rect intersects map: " << rect.intersects(map).size() << std::endl;
  std::cout << "rect is inside map: " << rect.isInside(map) << std::endl;
  for (auto p : rect.getPts()){
    std::cout << "point " << p << " is inside map: " << p.isInside(map) << std::endl;
  }

  return 0;
}

The output I get is the following:

rect closed: 1
map closed: 1
map: CPolyline: [-5,5]-[-5,-5]-[5,-5]-[5,5]-
rect: CPolyline: [-2,2]-[-2,-2]-[2,-2]-[2,2]-
rect intersects map: 0
rect is inside map: 0
point [-2,2] is inside map: 1
point [-2,-2] is inside map: 1
point [2,-2] is inside map: 1
point [2,2] is inside map: 1

Now the strange thing is that by using (CLion) debugger on the rect.isInside(map) instruction, it brings me to

/// This function is a fallback for all sub-classes that do not provide such a method.
/**
It is necessary in a run-time polymorphism context, as we would have build failures if a given type disallows providing such a method
(for example, when trying to check if some object is inside an open polyline).
*/
template<typename T>
constexpr bool isInside( const Common<T>& ) const
{
  return false;
}

Which would be find if I weren't using CPolygon but OPolygon.

I'm not sure if it's a problem of how I set my data or if there is a missing instruction in the library for the CPolygon.

compilation error on msvc 19.28

There is another compilation error on msvc 19.28.

https://raw.githubusercontent.com/skramm/homog2d/master/homog2d.hpp(2954): error C2063: 'h2d::operator *': not a function

Please refer godbolt: https://godbolt.org/z/61brssf9x

It works fine with gcc, clang and apple-clang.
Is there any way to fix this?

Feature to consider: Disable console messages (std::cerr) at will.

I understand that homog2d is not originally intended to address the requirements of speed-critical applications (such as real-time camera streams). However, some easy optimization in that sense could be considered. For instance, It would be nice if there was some way to disable the messages that are emitted right now by std::cerr.

For example; at the moment, although the result I get is perfect for my purposes, the console just spits out the execution of this line thousands of times.

std::cerr << "homog2d: angle computation overflow detected, value "
			<< std::scientific << std::setprecision(20)
			<< fres << ", truncated to 1.0\n";

"1.0000000000000000000224 or so (I can't quite remember), is truncated to 1.0." Ah. Well, that's great. :-)

I don't doubt that it is interesting to know that this event is occurring, but I can't do anything about it at this time.

I also honestly don't think this is a performance bottleneck for my application. Probably not. :-D But another added benefit is that noise in console would be reduced.

I suggest more control over this kind of messages (perhaps conditional compilation).

DJuego

Question about planned features

Thanks for this contribution! It seems to fit almost like a glove for an educational robotics related project I am involved in. It looks like a truly elegant contribution. I can deservedly say that it has been a lucky find. :-)

That said; there are some planned features that would come in very handy to what I have planned ('add non-convex polyline splitting into polygons', 'add polygon union and intersection'). Do you have any rough idea when they will see the light of day in the master?

Thank you again, and congrats!!

DJuego

MSVC2019: Build fails - Problems with code linkage.

Hi again! A new problem. :-D

Minimal sample:

//geometria.hpp
#pragma once
#include "homog2d/homog2d.hpp"
class geometria
{
};

//geometria.cpp
#include "geometria.hpp"

//main.cpp

#include "geometria.hpp"
void main()
{
}

And here is the result 😬 :

Build started...
1>------ Build started: Project: geometria_msvc2019, Configuration: Debug x64 ------
1>main.obj : error LNK2005: "public: __cdecl h2d::img::Image<struct h2d::img::SvgImage>::Image<struct h2d::img::SvgImage>(unsigned __int64,unsigned __int64)" (??0?$Image@USvgImage@img@h2d@@@img@h2d@@QEAA@_K0@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "public: void __cdecl h2d::img::Image<struct h2d::img::SvgImage>::clear(unsigned char,unsigned char,unsigned char)" (?clear@?$Image@USvgImage@img@h2d@@@img@h2d@@QEAAXEEE@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "public: void __cdecl h2d::img::Image<struct h2d::img::SvgImage>::drawText(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,class h2d::base::LPBase<struct h2d::type::IsPoint,float>,class h2d::img::DrawParams)" (?drawText@?$Image@USvgImage@img@h2d@@@img@h2d@@QEAAXV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V?$LPBase@UIsPoint@type@h2d@@M@base@3@VDrawParams@23@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "unsigned __int64 & __cdecl h2d::errorCount(void)" (?errorCount@h2d@@YAAEA_KXZ) already defined in geometria.obj
1>main.obj : error LNK2005: "char const * __cdecl h2d::getString(enum h2d::Type)" (?getString@h2d@@YAPEBDW4Type@1@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "enum h2d::Dtype __cdecl h2d::priv::impl_dtype(struct h2d::detail::DataFpType<float> const &)" (?impl_dtype@priv@h2d@@YA?AW4Dtype@2@AEBU?$DataFpType@M@detail@2@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "enum h2d::Dtype __cdecl h2d::priv::impl_dtype(struct h2d::detail::DataFpType<double> const &)" (?impl_dtype@priv@h2d@@YA?AW4Dtype@2@AEBU?$DataFpType@N@detail@2@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "enum h2d::Dtype __cdecl h2d::priv::impl_dtype(struct h2d::detail::DataFpType<long double> const &)" (?impl_dtype@priv@h2d@@YA?AW4Dtype@2@AEBU?$DataFpType@O@detail@2@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "void __cdecl h2d::priv::runion::moveToNextCell(unsigned char &,unsigned char &,enum h2d::priv::runion::Direction const &)" (?moveToNextCell@runion@priv@h2d@@YAXAEAE0AEBW4Direction@123@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "class std::vector<struct std::pair<unsigned char,unsigned char>,class std::allocator<struct std::pair<unsigned char,unsigned char> > > __cdecl h2d::priv::runion::parseTable(class std::array<class std::array<struct h2d::priv::runion::Cell,4>,4> &)" (?parseTable@runion@priv@h2d@@YA?AV?$vector@U?$pair@EE@std@@V?$allocator@U?$pair@EE@std@@@2@@std@@AEAV?$array@V?$array@UCell@runion@priv@h2d@@$03@std@@$03@5@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "void __cdecl h2d::thr::printThresholds(class std::basic_ostream<char,struct std::char_traits<char> > &)" (?printThresholds@thr@h2d@@YAXAEAV?$basic_ostream@DU?$char_traits@D@std@@@std@@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "public: void __cdecl h2d::img::Image<struct h2d::img::SvgImage>::svgInit(void)" (?svgInit@?$Image@USvgImage@img@h2d@@@img@h2d@@QEAAXXZ) already defined in geometria.obj
1>main.obj : error LNK2005: "enum h2d::priv::runion::Direction __cdecl h2d::priv::runion::turn(enum h2d::priv::runion::Direction,enum h2d::priv::runion::Turn)" (?turn@runion@priv@h2d@@YA?AW4Direction@123@W44123@W4Turn@123@@Z) already defined in geometria.obj
1>main.obj : error LNK2005: "public: void __cdecl h2d::img::Image<struct h2d::img::SvgImage>::write(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >)const " (?write@?$Image@USvgImage@img@h2d@@@img@h2d@@QEBAXV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z) already defined in geometria.obj
1>p:\Mis-Proyectos\Profesional\Ciberlandia\Geometria\prj\geometria_msvc2019\x64\Debug\geometria_msvc2019.exe : fatal error LNK1169: one or more multiply defined symbols found
1>Done building project "geometria_msvc2019.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

DJuego

PS:
However, this code works.

//main.cpp
#include "homog2d/homog2d.hpp"
void main()
{
}

[feature request] estimation of a homography from two ellipses

(this is just a reminder of a TODO)

From a suggestion done by Royi Avital:
-add estimation of a homography from two ellipses

Some refs:

Compilation issues in MSVS 17.8.3

Test code does not compile with MSVS 17.8.3

/std:c++14 option
homog2d.hpp(6257,87): error C2275: 'h2d::type::IsClosed': expected an expression instead of a type
homog2d.hpp(6257,72): error C2923: 'h2d::detail::PlHelper': 'h2d::type::IsClosed' is not a valid template type argument for parameter 'T'
homog2d.hpp(6257,24): error C2475: 'h2d::base::PolylineBase<T1,T2>::impl_set_RCP': redefinition; 'constexpr' specifier mismatch

/std:c++17 and /std:c++20 options
homog2d.hpp(6257,87): error C2275: 'h2d::type::IsClosed': expected an expression instead of a type
homog2d.hpp(6257,72): error C2923: 'h2d::detail::PlHelper': 'h2d::type::IsClosed' is not a valid template type argument for parameter 'T'
homog2d.hpp(6257,96): error C2955: 'h2d::detail::PlHelper': use of class template requires template argument list
homog2d.hpp(6257,58): error C2955: 'h2d::detail::PlHelper': use of class template requires template argument list
homog2d.hpp(6257,24): error C2475: 'h2d::base::PolylineBase<T1,T2>::impl_set_RCP': redefinition; 'constexpr' specifier mismatch

#include "homog2d.hpp"
using namespace h2d;
int main()
{
Line2d l1(Point2d(10, 10)); // a line passing through (0,0) and (10,10)
Line2d l2(Point2d(0, 10), Point2d(10, 0)); // a line passing through (0,10) and (10,0)
auto pt = l1 * l2; // intersection point (5,5)
Homogr H(2, 3); // a translation matrix
std::cout << H * pt; // prints [7,8]
}

skramm / homog2d Goto Github PK

homog2d's Introduction

homog2d

News

Details

homog2d's People

Contributors

Stargazers

Watchers

Forkers

homog2d's Issues

Recommend Projects

Recommend Topics

Recommend Org