line2d.h

Go to the documentation of this file.

// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h
 
#ifndef __IRR_LINE_2D_H_INCLUDED__
#define __IRR_LINE_2D_H_INCLUDED__
 
#include "vector2d.h"
 
namespace saga
{
namespace core
{
 
template <class T>
class line2d
{
  public:
    line2d() : start(0,0), end(1,1) {}
    line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {}
    line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {}
    line2d(const line2d<T>& other) : start(other.start), end(other.end) {}
 
    // operators
 
    line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); }
    line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; }
 
    line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); }
    line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; }
 
    bool operator==(const line2d<T>& other) const
    { return (start==other.start && end==other.end) || (end==other.start && start==other.end);}
    bool operator!=(const line2d<T>& other) const
    { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}
 
    // functions
    void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);}
    void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);}
    void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);}
 
 
    T getLength() const { return start.getDistanceFrom(end); }
 
 
    T getLengthSQ() const { return start.getDistanceFromSQ(end); }
 
 
    vector2d<T> getMiddle() const
    {
      return (start + end)/(T)2;
    }
 
 
    vector2d<T> getVector() const { return vector2d<T>(end.X - start.X, end.Y - start.Y); }
 
    bool intersectAsSegments(const line2d<T>& other) const
    {
      // Taken from:
      // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
 
      // Find the four orientations needed for general and
      // special cases
      std::int32_t o1 = start.checkOrientation(end, other.start);
      std::int32_t o2 = start.checkOrientation(end, other.end);
      std::int32_t o3 = other.start.checkOrientation(other.end, start);
      std::int32_t o4 = other.start.checkOrientation(other.end, end);
 
      // General case
      if (o1 != o2 && o3 != o4)
        return true;
 
      // Special Cases to check if segments are coolinear
      if (o1 == 0 && isBetweenPoints(other.start, start, end)) return true;
      if (o2 == 0 && isBetweenPoints(other.end, start, end)) return true;
      if (o3 == 0 && isBetweenPoints(start, other.start, other.end)) return true;
      if (o4 == 0 && isBetweenPoints(end, other.start, other.end)) return true;
 
      return false; // Doesn't fall in any of the above cases
    }
 
    bool incidentSegments(const line2d<T>& other) const
    {
      return
        start.checkOrientation(end, other.start) != start.checkOrientation(end, other.end)
      &&  other.start.checkOrientation(other.end, start) != other.start.checkOrientation(other.end, end);
    }
 
    bool nearlyParallel(const line2d<T>& line, const T factor = relativeErrorFactor<T>()) const
    {
      const vector2d<T> a = getVector();
      const vector2d<T> b = line.getVector();
 
      return a.nearlyParallel(b, factor);
    }
 
    vector2d<T> fastLinesIntersection(const line2d<T>& l) const
    {
      const float commonDenominator = (float)((l.end.Y - l.start.Y)*(end.X - start.X) -
        (l.end.X - l.start.X)*(end.Y - start.Y));
 
      if (commonDenominator != 0.f)
      {
        const float numeratorA = (float)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
          (l.end.Y - l.start.Y)*(start.X - l.start.X));
 
        const float uA = numeratorA / commonDenominator;
 
        // Calculate the intersection point.
        return vector2d<T> (
          (T)(start.X + uA * (end.X - start.X)),
          (T)(start.Y + uA * (end.Y - start.Y))
         );
      }
      else
        return l.start;
    }
 
    bool lineIntersectSegment(const line2d<T>& segment, vector2d<T> & out) const
    {
      if (nearlyParallel(segment))
        return false;
 
      out = fastLinesIntersection(segment);
 
      return isBetweenPoints(out, segment.start, segment.end);
    }
 
 
    bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const
    {
      // Uses the method given at:
      // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
      const float commonDenominator = (float)((l.end.Y - l.start.Y)*(end.X - start.X) -
                      (l.end.X - l.start.X)*(end.Y - start.Y));
 
      const float numeratorA = (float)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
                      (l.end.Y - l.start.Y)*(start.X -l.start.X));
 
      const float numeratorB = (float)((end.X - start.X)*(start.Y - l.start.Y) -
                      (end.Y - start.Y)*(start.X -l.start.X));
 
      if(equals(commonDenominator, 0.f))
      {
        // The lines are either coincident or parallel
        // if both numerators are 0, the lines are coincident
        if(!ignoreCoincidentLines && equals(numeratorA, 0.f) && equals(numeratorB, 0.f))
        {
          // Try and find a common endpoint
          if(l.start == start || l.end == start)
            out = start;
          else if(l.end == end || l.start == end)
            out = end;
          // now check if the two segments are disjunct
          else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)
            return false;
          else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)
            return false;
          else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)
            return false;
          else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)
            return false;
          // else the lines are overlapping to some extent
          else
          {
            // find the points which are not contributing to the
            // common part
            vector2d<T> maxp;
            vector2d<T> minp;
            if ((start.X>l.start.X && start.X>l.end.X && start.X>end.X) || (start.Y>l.start.Y && start.Y>l.end.Y && start.Y>end.Y))
              maxp=start;
            else if ((end.X>l.start.X && end.X>l.end.X && end.X>start.X) || (end.Y>l.start.Y && end.Y>l.end.Y && end.Y>start.Y))
              maxp=end;
            else if ((l.start.X>start.X && l.start.X>l.end.X && l.start.X>end.X) || (l.start.Y>start.Y && l.start.Y>l.end.Y && l.start.Y>end.Y))
              maxp=l.start;
            else
              maxp=l.end;
            if (maxp != start && ((start.X<l.start.X && start.X<l.end.X && start.X<end.X) || (start.Y<l.start.Y && start.Y<l.end.Y && start.Y<end.Y)))
              minp=start;
            else if (maxp != end && ((end.X<l.start.X && end.X<l.end.X && end.X<start.X) || (end.Y<l.start.Y && end.Y<l.end.Y && end.Y<start.Y)))
              minp=end;
            else if (maxp != l.start && ((l.start.X<start.X && l.start.X<l.end.X && l.start.X<end.X) || (l.start.Y<start.Y && l.start.Y<l.end.Y && l.start.Y<end.Y)))
              minp=l.start;
            else
              minp=l.end;
 
            // one line is contained in the other. Pick the center
            // of the remaining points, which overlap for sure
            out = core::vector2d<T>();
            if (start != maxp && start != minp)
              out += start;
            if (end != maxp && end != minp)
              out += end;
            if (l.start != maxp && l.start != minp)
              out += l.start;
            if (l.end != maxp && l.end != minp)
              out += l.end;
            out.X = (T)(out.X/2);
            out.Y = (T)(out.Y/2);
          }
 
          return true; // coincident
        }
 
        return false; // parallel
      }
 
      // Get the point of intersection on this line, checking that
      // it is within the line segment.
      const float uA = numeratorA / commonDenominator;
      if (checkOnlySegments)
      {
        if(uA < 0.f || uA > 1.f)
          return false; // Outside the line segment
 
        const float uB = numeratorB / commonDenominator;
        if(uB < 0.f || uB > 1.f)
          return false; // Outside the line segment
      }
 
      // Calculate the intersection point.
      out.X = (T)(start.X + uA * (end.X - start.X));
      out.Y = (T)(start.Y + uA * (end.Y - start.Y));
      return true;
    }
 
 
    vector2d<T> getUnitVector() const
    {
      T len = (T)(1.0 / getLength());
      return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
    }
 
 
    double getAngleWith(const line2d<T>& l) const
    {
      vector2d<T> vect = getVector();
      vector2d<T> vect2 = l.getVector();
      return vect.getAngleWith(vect2);
    }
 
 
    T getPointOrientation(const vector2d<T>& point) const
    {
      return ((end.X - start.X) * (point.Y - start.Y) -
          (point.X - start.X) * (end.Y - start.Y));
    }
 
 
    bool isPointOnLine(const vector2d<T>& point) const
    {
      T d = getPointOrientation(point);
      return (d == 0 && isBetweenPoints(point, start, end));
    }
 
 
    bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
    {
      return isBetweenPoints(point, start, end);
    }
 
 
    vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const
    {
      vector2d<double> c((double)(point.X-start.X), (double)(point.Y- start.Y));
      vector2d<double> v((double)(end.X-start.X), (double)(end.Y-start.Y));
      double d = v.getLength();
      if (d == 0) // can't tell much when the line is just a single point
        return start;
      v /= d;
      double t = v.dotProduct(c);
 
      if (checkOnlySegments)
      {
        if (t < 0) return vector2d<T>((T)start.X, (T)start.Y);
        if (t > d) return vector2d<T>((T)end.X, (T)end.Y);
      }
 
      v *= t;
      return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y));
    }
 
    vector2d<T> start;
    vector2d<T> end;
};
 
  // partial specialization to optimize <float> lines (avoiding casts)
  template <>
  inline vector2df line2d<float>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const
  {
    vector2df c = point - start;
    vector2df v = end - start;
    float d = (float)v.getLength();
    if (d == 0) // can't tell much when the line is just a single point
      return start;
    v /= d;
    float t = v.dotProduct(c);
 
    if (checkOnlySegments)
    {
      if (t < 0) return start;
      if (t > d) return end;
    }
 
    v *= t;
    return start + v;
  }
 
 
  typedef line2d<float> line2df;
  typedef line2d<std::int32_t> line2di;
 
} // namespace core
} // namespace saga
 
#endif