3
\$\begingroup\$

I wrote a small program to compute intersection of 2D infinite lines using Boost Geometry

A line is defined by two points in Line class. The getVector method enables to extract a direction vector.

The perp function enables to compute the perp product of two vectors. A zero value means vectors are parallel.

The intersect function checks if two lines intersect using the perp product of direction vectors. If true, it provides the intersection point by reference using parametric equation of lines.

Feel free to tell me if you know a more relevant library than Boost Geometry. Any idea to simplify and improve this code ?

Includes + namespace + typedef

#include <cmath>
#include <iostream>
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

namespace bg = boost::geometry;

typedef bg::model::d2::point_xy<double> Point;
typedef bg::model::d2::point_xy<double> Vector;

Line class

class Line
{
  public:
    Line(const Point& point1,const Point& point2): p1(point1), p2(point2) {}
    ~Line() {}

    Vector getVector() const 
    {
      Vector v(p2);
      bg::subtract_point(v,p1);
      return v;
    }

    Point p1;
    Point p2;
};

perp function

double perp(const Vector& v1, const Vector& v2)
{
  return bg::get<0>(v1)*bg::get<1>(v2)-bg::get<1>(v1)*bg::get<0>(v2);
}

intersect function

bool intersect(const Line& l1, const Line& l2, Point& inter)
{
  Vector v1 = l1.getVector();
  Vector v2 = l2.getVector();

  if(std::abs(perp(v1,v2))>0.)
  {
    Line l(l1.p1,l2.p1);
    Vector v = l.getVector();
    double t = perp(v,v2)/perp(v1,v2);
    inter = v1;
    bg::multiply_value(inter,t);
    bg::add_point(inter,l.p1);
    return true;
  }
  else return false;
}

Main with an example

int main(int argc, char** argv)
{
  Point p1(0.,0.);
  Point p2(1.,0.);
  Point p3(0.,1.);
  Point p4(0.,2.);
  Line l1(p1,p2);
  Line l2(p3,p4);

  Point inter;
  if( intersect(l1,l2,inter) )
  {
    std::cout<<"Coordinates of intersection: "<<inter.x()<<" "<<inter.y()<<std::endl;
  }
}
\$\endgroup\$
  • \$\begingroup\$ It may be worth it to give CGAL (Computational Geometry Algorithm Library) a shot. \$\endgroup\$ – NameRakes Apr 23 '16 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.