irr::core::line2d< T > Class Template Reference

2D line between two points with intersection methods. More...

#include <line2d.h>

Public Member Functions
	line2d ()
	Default constructor for line going from (0,0) to (1,1). More...
	line2d (T xa, T ya, T xb, T yb)
	Constructor for line between the two points. More...
	line2d (const vector2d< T > &start, const vector2d< T > &end)
	Constructor for line between the two points given as vectors. More...
	line2d (const line2d< T > &other)
	Copy constructor. More...
line2d< T >	operator+ (const vector2d< T > &point) const
line2d< T > &	operator+= (const vector2d< T > &point)
line2d< T >	operator- (const vector2d< T > &point) const
line2d< T > &	operator-= (const vector2d< T > &point)
bool	operator== (const line2d< T > &other) const
bool	operator!= (const line2d< T > &other) const
void	setLine (const T &xa, const T &ya, const T &xb, const T &yb)
	Set this line to new line going through the two points. More...
void	setLine (const vector2d< T > &nstart, const vector2d< T > &nend)
	Set this line to new line going through the two points. More...
void	setLine (const line2d< T > &line)
	Set this line to new line given as parameter. More...
T	getLength () const
	Get length of line. More...
T	getLengthSQ () const
	Get squared length of the line. More...
vector2d< T >	getMiddle () const
	Get middle of the line. More...
vector2d< T >	getVector () const
	Get the vector of the line. More...
bool	intersectAsSegments (const line2d< T > &other) const
bool	incidentSegments (const line2d< T > &other) const
bool	nearlyParallel (const line2d< T > &line, const T factor=relativeErrorFactor< T >()) const
vector2d< T >	fastLinesIntersection (const line2d< T > &l) const
bool	lineIntersectSegment (const line2d< T > &segment, vector2d< T > &out) const
bool	intersectWith (const line2d< T > &l, vector2d< T > &out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const
	Tests if this line intersects with another line. More...
vector2d< T >	getUnitVector () const
	Get unit vector of the line. More...
f64	getAngleWith (const line2d< T > &l) const
	Get angle between this line and given line. More...
T	getPointOrientation (const vector2d< T > &point) const
	Tells us if the given point lies to the left, right, or on the line. More...
bool	isPointOnLine (const vector2d< T > &point) const
	Check if the given point is a member of the line. More...
bool	isPointBetweenStartAndEnd (const vector2d< T > &point) const
	Check if the given point is between start and end of the line. More...
vector2d< T >	getClosestPoint (const vector2d< T > &point, bool checkOnlySegments=true) const
	Get the closest point on this line to a point. More...
template<>
vector2df	getClosestPoint (const vector2df &point, bool checkOnlySegments) const

Public Attributes
vector2d< T >	start
	Start point of the line. More...
vector2d< T >	end
	End point of the line. More...

Detailed Description

template<class T>
class irr::core::line2d< T >

2D line between two points with intersection methods.

Definition at line 18 of file line2d.h.

Constructor & Destructor Documentation

line2d() [1/4]

template<class T>

irr::core::line2d< T >::line2d ( )

inline

Default constructor for line going from (0,0) to (1,1).

Definition at line 22 of file line2d.h.

: start(0,0), end(1,1) {}

line2d() [2/4]

template<class T>

irr::core::line2d< T >::line2d ( T  xa, T  ya, T  xb, T  yb  )

inline

Constructor for line between the two points.

Definition at line 24 of file line2d.h.

: start(xa, ya), end(xb, yb) {}

line2d() [3/4]

template<class T>

irr::core::line2d< T >::line2d ( const vector2d< T > &  start, const vector2d< T > &  end  )

inline

Constructor for line between the two points given as vectors.

Definition at line 26 of file line2d.h.

: start(start), end(end) {}

line2d() [4/4]

template<class T>

irr::core::line2d< T >::line2d ( const line2d< T > &  other )

inline

Copy constructor.

Definition at line 28 of file line2d.h.

: start(other.start), end(other.end) {}

Member Function Documentation

fastLinesIntersection()

template<class T>

vector2d<T> irr::core::line2d< T >::fastLinesIntersection ( const line2d< T > &  l ) const

inline

returns a intersection point of 2 lines (if lines are not parallel). Behaviour undefined if lines are parallel or coincident. It's on optimized intersectWith with checkOnlySegments=false and ignoreCoincidentLines=true

Definition at line 118 of file line2d.h.

                {
                        const f32 commonDenominator = (f32)((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 f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
                                        (l.end.Y - l.start.Y)*(start.X - l.start.X));

                                const f32 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;
                }

getAngleWith()

template<class T>

f64 irr::core::line2d< T >::getAngleWith ( const line2d< T > &  l ) const

inline

Get angle between this line and given line.

Parameters

l	Other line for test.

Returns

Angle in degrees.

Definition at line 268 of file line2d.h.

                {
                        vector2d<T> vect = getVector();
                        vector2d<T> vect2 = l.getVector();
                        return vect.getAngleWith(vect2);
                }

getClosestPoint() [1/2]

template<class T>

vector2d<T> irr::core::line2d< T >::getClosestPoint ( const vector2d< T > &  point, bool  checkOnlySegments = true  ) const

inline

Get the closest point on this line to a point.

Parameters

checkOnlySegments

Default (true) is to return a point on the line-segment (between begin and end) of the line. When set to false the function will check for the first the closest point on the the line even when outside the segment.

Definition at line 302 of file line2d.h.

                {
                        vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y));
                        vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y));
                        f64 d = v.getLength();
                        if ( d == 0 ) // can't tell much when the line is just a single point
                                return start;
                        v /= d;
                        f64 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));
                }

getClosestPoint() [2/2]

template<>

vector2df irr::core::line2d< irr::f32 >::getClosestPoint ( const vector2df &  point, bool  checkOnlySegments  ) const

inline

Definition at line 330 of file line2d.h.

        {
                const vector2df c = point - start;
                vector2df v = end - start;
                const f32 d = (f32)v.getLength();
                if ( d == 0 ) // can't tell much when the line is just a single point
                        return start;
                v /= d;
                const f32 t = v.dotProduct(c);

                if ( checkOnlySegments )
                {
                        if (t < 0) return start;
                        if (t > d) return end;
                }

                v *= t;
                return start + v;
        }

getLength()

template<class T>

T irr::core::line2d< T >::getLength ( ) const

inline

Get length of line.

Returns

Length of the line.

Definition at line 53 of file line2d.h.

{ return start.getDistanceFrom(end); }

getLengthSQ()

template<class T>

T irr::core::line2d< T >::getLengthSQ ( ) const

inline

Get squared length of the line.

Returns

Squared length of line.

Definition at line 57 of file line2d.h.

{ return start.getDistanceFromSQ(end); }

getMiddle()

template<class T>

vector2d<T> irr::core::line2d< T >::getMiddle ( ) const

inline

Get middle of the line.

Returns

center of the line.

Definition at line 61 of file line2d.h.

                {
                        return (start + end)/(T)2;
                }

getPointOrientation()

template<class T>

T irr::core::line2d< T >::getPointOrientation ( const vector2d< T > &  point ) const

inline

Tells us if the given point lies to the left, right, or on the line.

Returns

0 if the point is on the line <0 if to the left, or >0 if to the right.

Definition at line 278 of file line2d.h.

                {
                        return ( (end.X - start.X) * (point.Y - start.Y) -
                                        (point.X - start.X) * (end.Y - start.Y) );
                }

getUnitVector()

template<class T>

vector2d<T> irr::core::line2d< T >::getUnitVector ( ) const

inline

Get unit vector of the line.

Returns

Unit vector of this line.

Definition at line 259 of file line2d.h.

                {
                        T len = (T)(1.0 / getLength());
                        return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
                }

getVector()

template<class T>

vector2d<T> irr::core::line2d< T >::getVector ( ) const

inline

Get the vector of the line.

Returns

The vector of the line.

Definition at line 68 of file line2d.h.

{ return vector2d<T>( end.X - start.X, end.Y - start.Y); }

incidentSegments()

template<class T>

bool irr::core::line2d< T >::incidentSegments ( const line2d< T > &  other ) const

inline

Check if 2 segments are incident (intersects in exactly 1 point).

Definition at line 98 of file line2d.h.

                {
                        return 
                                start.checkOrientation( end, other.start) != start.checkOrientation( end, other.end)
                        &&  other.start.checkOrientation( other.end, start) != other.start.checkOrientation( other.end, end);
                }

intersectAsSegments()

template<class T>

bool irr::core::line2d< T >::intersectAsSegments ( const line2d< T > &  other ) const

inline

Check if this segment intersects another segment, or if segments are coincindent (colinear).

Definition at line 72 of file line2d.h.

                {
                        // Taken from:
                        // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

                        // Find the four orientations needed for general and
                        // special cases
                        s32 o1 = start.checkOrientation( end, other.start);
                        s32 o2 = start.checkOrientation( end, other.end);
                        s32 o3 = other.start.checkOrientation( other.end, start);
                        s32 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 && other.start.isBetweenPoints( start, end)) return true;
                        if (o2 == 0 && other.end.isBetweenPoints( start, end)) return true;
                        if (o3 == 0 && start.isBetweenPoints( other.start, other.end)) return true;
                        if (o4 == 0 && end.isBetweenPoints( other.start, other.end)) return true;

                        return false; // Doesn't fall in any of the above cases
                }

intersectWith()

template<class T>

bool irr::core::line2d< T >::intersectWith ( const line2d< T > &  l, vector2d< T > &  out, bool  checkOnlySegments = true, bool  ignoreCoincidentLines = false  ) const

inline

Tests if this line intersects with another line.

Parameters

l	Other line to test intersection with.
checkOnlySegments	Default is to check intersection between the begin and endpoints. When set to false the function will check for the first intersection point when extending the lines.
out	If there is an intersection, the location of the intersection will be stored in this vector.
ignoreCoincidentLines	When true coincident lines (lines above each other) are never considered as intersecting. When false the center of the overlapping part is returned.

Returns

True if there is an intersection, false if not.

Definition at line 160 of file line2d.h.

                {
                        // Uses the method given at:
                        // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
                        const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
                                                                                        (l.end.X - l.start.X)*(end.Y - start.Y));

                        const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
                                                                                        (l.end.Y - l.start.Y)*(start.X -l.start.X));

                        const f32 numeratorB = (f32)((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 f32 uA = numeratorA / commonDenominator;
                        if (checkOnlySegments)
                        {
                                if(uA < 0.f || uA > 1.f)
                                        return false; // Outside the line segment

                                const f32 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;
                }

isPointBetweenStartAndEnd()

template<class T>

bool irr::core::line2d< T >::isPointBetweenStartAndEnd ( const vector2d< T > &  point ) const

inline

Check if the given point is between start and end of the line.

Assumes that the point is already somewhere on the line.

Definition at line 294 of file line2d.h.

                {
                        return point.isBetweenPoints(start, end); 
                }

isPointOnLine()

template<class T>

bool irr::core::line2d< T >::isPointOnLine ( const vector2d< T > &  point ) const

inline

Check if the given point is a member of the line.

Returns

True if point is between start and end, else false.

Definition at line 286 of file line2d.h.

                {
                        T d = getPointOrientation(point);
                        return (d == 0 && point.isBetweenPoints(start, end));
                }

lineIntersectSegment()

template<class T>

bool irr::core::line2d< T >::lineIntersectSegment ( const line2d< T > &  segment, vector2d< T > &  out  ) const

inline

Check if this line intersect a segment. The eventual intersection point is returned in "out".

Definition at line 141 of file line2d.h.

                {
                        if (nearlyParallel( segment))
                                return false;

                        out = fastLinesIntersection( segment);

                        return out.isBetweenPoints( segment.start, segment.end);
                }

nearlyParallel()

template<class T>

bool irr::core::line2d< T >::nearlyParallel ( const line2d< T > &  line, const T  factor = relativeErrorFactor<T>()  ) const

inline

Check if 2 lines/segments are parallel or nearly parallel.

Definition at line 106 of file line2d.h.

                {
                        const vector2d<T> a = getVector();
                        const vector2d<T> b = line.getVector();

                        return a.nearlyParallel( b, factor);
                }

operator!=()

template<class T>

bool irr::core::line2d< T >::operator!= ( const line2d< T > &  other ) const

inline

Definition at line 40 of file line2d.h.

                { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}

operator+()

template<class T>

line2d<T> irr::core::line2d< T >::operator+ ( const vector2d< T > &  point ) const

inline

Definition at line 32 of file line2d.h.

{ return line2d<T>(start + point, end + point); }

operator+=()

template<class T>

line2d<T>& irr::core::line2d< T >::operator+= ( const vector2d< T > &  point )

inline

Definition at line 33 of file line2d.h.

{ start += point; end += point; return *this; }

operator-()

template<class T>

line2d<T> irr::core::line2d< T >::operator- ( const vector2d< T > &  point ) const

inline

Definition at line 35 of file line2d.h.

{ return line2d<T>(start - point, end - point); }

operator-=()

template<class T>

line2d<T>& irr::core::line2d< T >::operator-= ( const vector2d< T > &  point )

inline

Definition at line 36 of file line2d.h.

{ start -= point; end -= point; return *this; }

operator==()

template<class T>

bool irr::core::line2d< T >::operator== ( const line2d< T > &  other ) const

inline

Definition at line 38 of file line2d.h.

                { return (start==other.start && end==other.end) || (end==other.start && start==other.end);}

setLine() [1/3]

template<class T>

void irr::core::line2d< T >::setLine ( const T &  xa, const T &  ya, const T &  xb, const T &  yb  )

inline

Set this line to new line going through the two points.

Definition at line 45 of file line2d.h.

{start.set(xa, ya); end.set(xb, yb);}

setLine() [2/3]

template<class T>

void irr::core::line2d< T >::setLine ( const vector2d< T > &  nstart, const vector2d< T > &  nend  )

inline

Set this line to new line going through the two points.

Definition at line 47 of file line2d.h.

{start.set(nstart); end.set(nend);}

setLine() [3/3]

template<class T>

void irr::core::line2d< T >::setLine ( const line2d< T > &  line )

inline

Set this line to new line given as parameter.

Definition at line 49 of file line2d.h.

{start.set(line.start); end.set(line.end);}

Member Data Documentation

end

template<class T>

vector2d<T> irr::core::line2d< T >::end

End point of the line.

Definition at line 325 of file line2d.h.

start

template<class T>

vector2d<T> irr::core::line2d< T >::start

Start point of the line.

Definition at line 323 of file line2d.h.

---

The documentation for this class was generated from the following file:

• include/irrlicht/line2d.h