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

2.5 The Polygon ADT

As indicated earlier, there are many different types of containers. Most containers are designed for general purpose use, such as a list or dictionary. But a container can also be designed for a specific limited use. For example, suppose we need a container to store and manage a collection of vertices that define a geometric polygon. A polygon container would store and manage a collection of vertices in a specific order, which define the polygon. The operations needed to use and manage the collection can be limited to those needed to find, add, or remove vertices. In this section, we define and implement a complex abstract data type to represent a polygon.

ADT Definition

The Polygon ADT

A polygon is a closed geometric shape consisting of three or more line segments (edges) that are connected end to end. The endpoints of the line segments are known as vertices, which are defined by points in the two-dimensional Cartesian coordinate system. The vertices of the polygon can be accessed by position (0 ... n-1).

  • Polygon(x0, y0, x1, y1, x2, y2)

    Creates a new polygon instance defined by the three vertices (x0, y0), (x1, y1), and (x2, y2).

  • length()

    Returns the number of vertices that define the polygon.

  • findVertex(x, y)

    Searches the collection of vertices and returns the index or position of the given vertex, (x, y). If the polygon does not consist of a vertex with the given coordinates, -1 is returned.

  • getVertex(index)

    Returns the coordinates of the vertex at the given index position as a 2-tuple (x, y). The index must be within the valid range of vertices.

  • appendVertex(x, y)

    Adds a new vertex with coordinates (x, y) to the polygon immediately following the vertex in the last position (len(p) - 1). The vertex can not be equal to an existing vertex.

  • insertVertex(index, x, y)

    Inserts a new vertex with coordinates (x, y) at the index position. All existing vertices at and following the index position are shifted down one place. The vertex can not be equal to an existing vertex. The index must be within the valid range from 0 to the number of vertices in the polygon. If the index is equal to the number of vertices, then the new vertex is appended to the end of the list.

  • deleteVertex(index)

    Removes the vertex at the given index position of a polygon that consist of more than 3 vertices. All existing vertices at and following the index position are shifted up one place. The index must be within the valid range of vertices.

  • perimeter()

    Returns the total length of the perimeter of the polygon which is the sum of the lengths of the line segments connecting adjacent vertices.

The following simple program illustrates the basic use of the Polygon ADT. A three sided polygon is initially constructed with two additional vertices added, one is inserted and the other appended. The number of vertices is obtained and a search is performed for a given vertex.

from polygon import Polygon

poly = Polygon(0, 12, 13, 20, 27, 10)
poly.insertVertex(3, 20, 0)
poly.appendVertex(5, 0)

print("The polygon contains", len(poly), "vertices.")

if poly.findVertex(5, 20) >= 0 :
  print("The polygon has vertex (%d, %d)", (5, 20))
else :
  print("The polygon does not contain vertex (%d, %d)", (5, 20))
Page last modified on August 03, 2023, at 07:33 AM