michael@0: /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef GFX_LINESEGMENT_H
michael@0: #define GFX_LINESEGMENT_H
michael@0: 
michael@0: #include "gfxTypes.h"
michael@0: #include "gfxPoint.h"
michael@0: 
michael@0: struct gfxLineSegment {
michael@0:   gfxLineSegment(const gfxPoint &aStart, const gfxPoint &aEnd) 
michael@0:     : mStart(aStart)
michael@0:     , mEnd(aEnd)
michael@0:   {}
michael@0: 
michael@0:   bool PointsOnSameSide(const gfxPoint& aOne, const gfxPoint& aTwo)
michael@0:   {
michael@0:     // Solve the equation y - mStart.y - ((mEnd.y - mStart.y)/(mEnd.x - mStart.x))(x - mStart.x) for both points 
michael@0:   
michael@0:     gfxFloat deltaY = (mEnd.y - mStart.y);
michael@0:     gfxFloat deltaX = (mEnd.x - mStart.x);
michael@0:   
michael@0:     gfxFloat one = deltaX * (aOne.y - mStart.y) - deltaY * (aOne.x - mStart.x);
michael@0:     gfxFloat two = deltaX * (aTwo.y - mStart.y) - deltaY * (aTwo.x - mStart.x);
michael@0: 
michael@0:     // If both results have the same sign, then we're on the correct side of the line.
michael@0:     // 0 (on the line) is always considered in.
michael@0: 
michael@0:     if ((one >= 0 && two >= 0) || (one <= 0 && two <= 0))
michael@0:       return true;
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Determines if two line segments intersect, and returns the intersection
michael@0:    * point in aIntersection if they do.
michael@0:    *
michael@0:    * Coincident lines are considered not intersecting as they don't have an
michael@0:    * intersection point.
michael@0:    */
michael@0:   bool Intersects(const gfxLineSegment& aOther, gfxPoint& aIntersection)
michael@0:   {
michael@0:     gfxFloat denominator = (aOther.mEnd.y - aOther.mStart.y) * (mEnd.x - mStart.x ) - 
michael@0:                            (aOther.mEnd.x - aOther.mStart.x ) * (mEnd.y - mStart.y);
michael@0: 
michael@0:     // Parallel or coincident. We treat coincident as not intersecting since
michael@0:     // these lines are guaranteed to have corners that intersect instead.
michael@0:     if (!denominator) {
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     gfxFloat anumerator = (aOther.mEnd.x - aOther.mStart.x) * (mStart.y - aOther.mStart.y) -
michael@0:                          (aOther.mEnd.y - aOther.mStart.y) * (mStart.x - aOther.mStart.x);
michael@0:   
michael@0:     gfxFloat bnumerator = (mEnd.x - mStart.x) * (mStart.y - aOther.mStart.y) -
michael@0:                          (mEnd.y - mStart.y) * (mStart.x - aOther.mStart.x);
michael@0: 
michael@0:     gfxFloat ua = anumerator / denominator;
michael@0:     gfxFloat ub = bnumerator / denominator;
michael@0: 
michael@0:     if (ua <= 0.0 || ua >= 1.0 ||
michael@0:         ub <= 0.0 || ub >= 1.0) {
michael@0:       //Intersection is outside of the segment
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     aIntersection = mStart + (mEnd - mStart) * ua;  
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0:   gfxPoint mStart;
michael@0:   gfxPoint mEnd;
michael@0: };
michael@0: 
michael@0: #endif /* GFX_LINESEGMENT_H */