Data Structures and Algorithms using Python
Copyright © 2023 by Rance Necaise
Table Of Contents
Data Structures and Algorithms using Python
Copyright © 2023
by Rance Necaise

1.8 Implementing the Line Segment ADT

To use the ADT, we must provide a concrete implementation. Before we can do that, however, we need to determine what would be the best way to represent the new data type. Since a line segment is defined by the x- and y-coordinates of two endpoints, we can represent a line segment by storing those four values. Further, a line segment can be defined for either the discrete (integer coordinates) or continuous space (real coordinates). For simplicity, we will assume the use of floating-point values for the coordinates.

Constructor and Accessors

To implement the LineSegment class, we begin with the constructor. The constructor takes four arguments, two for each pair of coordinates and stores the values in four separate instance variables.

class LineSegment :
  def __init__(self, x0, y0, x1, y1) :
    self._xCoordA = x0
    self._yCoordA = y0
    self._xCoordB = x1
    self._yCoordB = y1

With the use of four instance variables for the coordinates, the implementation of the two endpoint accessor methods are rather simple:

def endPointA(self) :
  return (self._xCoordA, self._yCoordA)  # returns a 2-tuple

def endPointB(self) :
  return (self._xCoordB, self._yCoordB)  # returns a 2-tuple

Line Characteristics

The Line Segment ADT defines several operations that provide information related to the characteristics of the line segment. First, the isVertical method is used to determine if the line segment represents a vertical line. By definition, a line segment is vertical if it is parallel to the y-axis. That is, the x-coordinates of both endpoints are identical. Here is the implementation of the isVertical method:

def isVertical(self) :
  return self._xCoordA == self._xCoordB

To compute the length of a line segment, we use the Euclidean distanceformula

and implement the length method as follows:

def length(self) :
  xDiff = self._xCoordA - self._xCoordB
  yDiff = self._yCoordA - self._yCoordB
  dist = sqrt(xDiff ** 2 + yDiff ** 2)
  return dist

The Euclidean distance requires the use of the sqrt function from the math module, which we assume was imported at the top of the \module{line} module. Implementation of the isHorizontal, isParallel, and midPoint methods are left as an exercise.

The Shift Operation

The shift operation defined by the Line Segment ADT does not modify the given line segment itself. Instead it creates and returns a new line segment that results from shifting the original line segment. It would be used like this:

lineA = LineSegment(0, 0, 10, 20)
lineB = lineA.shift(5, 2)

If we were to print the value of the lineA line segment before and after the shift,

lineA = LineSegment(0, 0, 10, 20)
print(lineA)
lineB = lineA.shift(5, 2)
print(lineA)

it would produce identical results

line: (0, 0)#(10, 20)
line: (0, 0)#(10, 20)

To implement the shift method, we must first compute the coordinates for the new line segment. This is done by adding the appropriate increment value to the coordinates of the line segment referenced by self. A new line segment is then created and returned using the new coordinates. Here is the implementation of that method:

def shift(self, xInc, yInc) :
  newX0 = self._xCoordA + xInc
  newY0 = self._yCoordA + yInc
  newX1 = self._xCoordB + xInc
  newY1 = self._yCoordB + yInc
  return LineSegment(newX0, newY0, newX1, newY1)

Line Slope

The slope of a straight line segment is computed as m = rise / run, that is the difference in the y-coordinates (y0 - y1) divided by the difference in the x-coordinates (x0 - y1). Given this formula, the implementation of the slope method follows:

def slope(self) :
  rise = self._yCoordA - self._yCoordB
  run = self._xCoordA - self._xCoordB
  return rise / run

A partial implementation of the Line Segment ADT is provided below. This definition of the slope method correctly implements the slope formula. There is a problem, however. The slope can not be computed for a vertical line, which would result in a division by zero run-time error. What should we do or what should be returned when the slope method is applied to a vertical line? We answer this question and provide a correct solution in the next section.

Program Listing
Program: line1.py
  1. # Implementation of the Line Segment ADT in which the coordinates for
  2. # end points are stored in individual instance variables.
  3. from math import sqrt
  4.  
  5. class LineSegment :
  6.    # Creates a new LineSegment instance from the given end point coords.
  7.   def __init__(self, x0, y0, x1, y1) :
  8.     self._xCoordA = x0
  9.     self._yCoordA = y0
  10.     self._xCoordB = x1
  11.     self._yCoordB = y1
  12.  
  13.    # Returns the first end point of the line as a 2-tuple (x, y).
  14.   def endPointA(self) :
  15.     return (self._xCoordA, self._yCoordA)
  16.  
  17.    # Returns the second end point of the line as a 2-tuple (x, y).
  18.   def endPointB(self) :
  19.     return (self._xCoordB, self._yCoordB)
  20.  
  21.    # Returns a Boolean value indicating if this is a vertical line segment.
  22.   def isVertical(self) :
  23.     return self._xCoordA == self._xCoordB
  24.    
  25.    # Returns the Euclidean distance between the two endpoints.    
  26.   def length(self) :
  27.     xDiff = self._xCoordA - self._xCoordB
  28.     yDiff = self._yCoordA - self._yCoordB
  29.     dist = sqrt(xDiff ** 2 + yDiff ** 2)
  30.     return dist
  31.    
  32.    # Returns a new LineSegment instance that is the result of shifting
  33.    # this line segment in both the x- and y-direction.
  34.   def shift(self, xInc, yInc) :
  35.     newX0 = self._xCoordA + xInc
  36.     newY0 = self._yCoordA + yInc
  37.     newX1 = self._xCoordB + xInc
  38.     newY1 = self._yCoordB + yInc
  39.     return LineSegment(newX0, newY0, newX1, newY1)
  40.    
  41.    # Returns the slope of the line segment given as the rise over the run.
  42.   def slope(self) :
  43.     rise = self._yCoordA - self._yCoordB
  44.     run = self._xCoordA - self._xCoordB
  45.     return rise / run    
  46.    
  47.    # --- The remaining methods go here ---
Page last modified on July 30, 2023, at 08:19 PM