Algorithm
Development Kit 1.0

algs.model.twod
Class TwoDLineSegment

java.lang.Object
  extended by algs.model.twod.TwoDLineSegment
All Implemented Interfaces:
ILineSegment, IMultiLineSegment

public class TwoDLineSegment
extends java.lang.Object
implements ILineSegment, IMultiLineSegment

Standard two-dimensional implementation of ILineSegment. By etiquette, all line segments are directionless, so we impose our own order on things. Specifically, the start of the line has its y value >= the y-value of the end.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 TwoDPoint end
          Store Line segment end.
 boolean isPoint
          Is just a point?
 double m
          Slope.
 int sign
          Sign of Slope.
 TwoDPoint start
          Store Line segment start.
 
Fields inherited from interface algs.model.ILineSegment
COINCIDENT, INTERSECTING, NON_INTERSECTING, PARALLEL
 
Constructor Summary
TwoDLineSegment(double x1, double y1, double x2, double y2)
          Helper method for constructing a Line segment from four points.
TwoDLineSegment(IPoint s, IPoint e)
           
 
Method Summary
 int dimensionality()
          Return the dimensionality of this line segment.
 boolean equals(java.lang.Object o)
          Provides the standard equals method.
 IPoint getEnd()
          Return the coordinate value of the End of the line segment as a two-dimensional IPoint.
 IMultiPoint getEndPoint()
          Return the coordinate value of the End of the line segment as an IMultiPoint.
 IPoint getStart()
          Return the coordinate value of the Start of the line segment as a two-dimensional IPoint.
 IMultiPoint getStartPoint()
          Return the coordinate value of the Start of the line segment as an IMultiPoint.
 IPoint intersection(ILineSegment other)
          Computer the intersection point with the given line segment.
 boolean intersection(IPoint p)
          Determine if line segments intersects this point.
 int intersectionType(ILineSegment other)
          Compute the intersection type with the given line segment.
 boolean isHorizontal()
          Determine if horizontal.
 boolean isPoint()
          Determine if this line segment is simply a point (same start & end).
 boolean isVertical()
          Determine if vertical.
 boolean pointOnLeft(IPoint p)
          Given the line segment in its reverse-directed orientation (from lower to upper point), determine if point p is to the left of the line, as you head from lower to upper If it is exactly on the line, then we return false.
 boolean pointOnRight(IPoint p)
          Given the line segment in its reverse-directed orientation (from lower to upper point), determine if point p is to the right of the line, as you head from lower to upper.
 int sign()
          Return sign of slope.
 double slope()
          Compute slope of line segment, or return Double.NaN for vertical lines.
 java.lang.String toString()
          Reasonable toString() implementation.
 double yIntercept()
          Compute yIntercept of line segment if extended to be a line.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

start

public final TwoDPoint start
Store Line segment start.


end

public final TwoDPoint end
Store Line segment end.


isPoint

public final boolean isPoint
Is just a point?


m

public final double m
Slope.


sign

public final int sign
Sign of Slope. Needed to deal with the 3 situations when determining pointOnRight. Assume positive

Constructor Detail

TwoDLineSegment

public TwoDLineSegment(double x1,
                       double y1,
                       double x2,
                       double y2)
Helper method for constructing a Line segment from four points.

Parameters:
x1 - x-value of p1
y1 - y-value of p1
x2 - x-value of p2
y2 - y-value of p2

TwoDLineSegment

public TwoDLineSegment(IPoint s,
                       IPoint e)
Parameters:
s - Start of this line segment in two-dimensional space
e - End of this line segment in two-dimensional space TODO: Should we prevent attempts to store with Infinity?
Method Detail

getStartPoint

public IMultiPoint getStartPoint()
Description copied from interface: IMultiLineSegment
Return the coordinate value of the Start of the line segment as an IMultiPoint.

Specified by:
getStartPoint in interface IMultiLineSegment
See Also:
IMultiLineSegment.getStartPoint()

getEndPoint

public IMultiPoint getEndPoint()
Description copied from interface: IMultiLineSegment
Return the coordinate value of the End of the line segment as an IMultiPoint.

Specified by:
getEndPoint in interface IMultiLineSegment
See Also:
IMultiLineSegment.getEndPoint()

getStart

public IPoint getStart()
Description copied from interface: ILineSegment
Return the coordinate value of the Start of the line segment as a two-dimensional IPoint. The start point will have a higher y-value than the end line, except for horizontal lines.

Specified by:
getStart in interface ILineSegment
See Also:
ILineSegment.getStart()

getEnd

public IPoint getEnd()
Description copied from interface: ILineSegment
Return the coordinate value of the End of the line segment as a two-dimensional IPoint. The end point will have a lower y-value than the end line, except for horizontal lines.

Specified by:
getEnd in interface ILineSegment
See Also:
ILineSegment.getEnd()

equals

public boolean equals(java.lang.Object o)
Provides the standard equals method. A line segment (p1, p2) is not the same as line segment (p2, p1).

Overrides:
equals in class java.lang.Object

toString

public java.lang.String toString()
Reasonable toString() implementation.

Overrides:
toString in class java.lang.Object

dimensionality

public int dimensionality()
Description copied from interface: IMultiLineSegment
Return the dimensionality of this line segment.

Specified by:
dimensionality in interface IMultiLineSegment
See Also:
IMultiLineSegment.dimensionality()

slope

public double slope()
Compute slope of line segment, or return Double.NaN for vertical lines.

Specified by:
slope in interface ILineSegment

sign

public int sign()
Return sign of slope.

Specified by:
sign in interface ILineSegment

isHorizontal

public boolean isHorizontal()
Determine if horizontal.

Specified by:
isHorizontal in interface ILineSegment

isVertical

public boolean isVertical()
Determine if vertical.

Specified by:
isVertical in interface ILineSegment

yIntercept

public double yIntercept()
Compute yIntercept of line segment if extended to be a line.

Specified by:
yIntercept in interface ILineSegment

intersectionType

public int intersectionType(ILineSegment other)
Compute the intersection type with the given line segment. Method not actually used by any algorithms (yet). Returns one of:

Parameters:
other - other line segment with which to compare.

intersection

public IPoint intersection(ILineSegment other)
Computer the intersection point with the given line segment. If no such intersection, return null. If null is returned, you may have to invoke intersectionType to discover the reason.

Specified by:
intersection in interface ILineSegment

intersection

public boolean intersection(IPoint p)
Determine if line segments intersects this point.

Intersection is true if point equals either of the end points. Removed since it detects intersections along the infinite line which is the extension of this line segment. Only for vertical lines does this method restrict the intersection to between (start, end).

Specified by:
intersection in interface ILineSegment
Parameters:
p - point to be inspected.

isPoint

public boolean isPoint()
Description copied from interface: ILineSegment
Determine if this line segment is simply a point (same start & end).

Specified by:
isPoint in interface ILineSegment
See Also:
ILineSegment.isPoint()

pointOnRight

public boolean pointOnRight(IPoint p)
Given the line segment in its reverse-directed orientation (from lower to upper point), determine if point p is to the right of the line, as you head from lower to upper. If it is exactly on the line, then we return false. Note that we use the following inverted equation for lines to make the determination. The equation can easily be confirmed, but care must be taken based upon the sign of the slope (since we are dividing by m).
              
                 (y2 - y1)
    0 = y - y1 - --------- (x - x1)
                 (x2 - x1)
 
Since this operation is SO COMMON, we use a standard trick to remove the IF statements. Specifically, if m is positive, then we check if res < 0 but if m is negative, then we check if -res < 0. Thus we also need to store the SIGN of the slope with each segment.

Specified by:
pointOnRight in interface ILineSegment
Parameters:
p - Point in question

pointOnLeft

public boolean pointOnLeft(IPoint p)
Given the line segment in its reverse-directed orientation (from lower to upper point), determine if point p is to the left of the line, as you head from lower to upper If it is exactly on the line, then we return false. See pointOnRight(IPoint) for the mathematical explanation for these equations, as well as importance of sign.

Specified by:
pointOnLeft in interface ILineSegment
Parameters:
p -

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.