Channels ▼
RSS

Design

The PolyArea Project: Part 1


Poly Area Architecture and Organization

The architecture focuses on separating the UI code from the algorithmic code to accomodate testing and also potential replacement of the low-level graphic library (PyGame). In addition, there is a little module called config.py that lets users configure the look-and-feel.

There are three modules in the algorithmic core:

  • The polygon module is responsible for the main algorithm. It has a custom Polygon class that provides some important methods used by the calc_polygon_area() function and its support functions: find_Second_top_point() and remove_top_triangle(). It uses functions from the triangle and helpers modules.
  • The triangle module contains two functions: herons_formula() and calc_triangle_area(). It also has two test functions: test_herons_formula() and test_calc_triangle_area(). This is a good example of bottom up programming. It is a very small bit of functionality (calculating the area of a triangle) encapsulated in its own module with its own tests. It is very easy to implement, test and if necessary modify it (e.g. implement the calculation using a different formula).
  • The helpers module is a support module that contains many simple and general-purpose functions that are not tied specifically to the polygon triangulation algorithm. This module can potentially be reused in other computational geometry programs. It follows the same pattern as the triangle module and has a test function for each function. Some functions are: find_line_coeeficients(), calc_distance(), and intersect().

Then there is one big UI module and a config module.

  • The ui module is responsible for all the visual aspects of poly area and the interaction with the user. It lets you draw a polygon and make sure you draw a valid polygon. Once the polygon is closed it is divided into triangles and its area is calculated and you can visualize the algorithm operation step by step by pressing the spacebar. There is a fair amount of functionality involved and the code to verify that the polygon is valid is actually more complicated then the core algorithm. The ui module uses the mainloop and pygame_objects modules.
  • The config module resembles a Windows .ini file. It just contains some variables such as grid resolution, line thickness, and colors. The ui module reads this file and uses the values when rendering the UI.

There are two PyGame-related infrastructure modules:

  • The mainloop module encapsulates the typical event loop of a GUI program and provides a PyGame-based implementation. In addition to some PyGame incantations it manages a list of object it renders to the screen in each iteration. These objects must support a simple interface and objects can be added/removed dynamically from the list during the program's run.
  • The pygame_objects module contains several objects that support the mainloop interface.

Finally there is a BaseObject base class.

Testing

Testing is not as rigorous as I would implement in a professional project (100% coverage), but it is pretty good. I didn't implement negative tests (tests that provide bad input on purpose to make sure the code fails as expected with the proper exception and helpful error message) because writing these tests take a lot of time (usually there are many more bad inputs than good inputs) and I control the using code, so I can make sure no bad inputs are provided.

The triangle.py and helpers.py have self tests. Normally, they should be imported and used by other modules, but if you run them directly then they execute a test() function. This is done via the module's __name__ attribute.


if __name__=='__main__':
 test()

The __name__ attribute is set by the interpreter when the module is being run directly as in:


python triangle.py

There are internal tests for the following modules:

  • The tests for the triangle module are very simple. The test_herons_formula() functions makes sure that the when passing 3, 4 and 5 as the triangle sides the herons_formula() function correctly returns the area as 6:

    
    def test_herons_formula():
      a = 3
      b = 4
      c = 5
      assert herons_formula(a, b, c) == 6
    
    

  • The test for the compute_triangle_area() module is almost the same except that it passes the vertices of an equivalent triangle:

    
    def test_calc_triangle_area():
      p1 = (0, 0)
      p2 = (0, 3)
      p3 = (4, 0)
      assert calc_triangle_area(p1, p2, p3) == 6
    
    

  • The helpers module contains simple tests for all its functions. For example, here is the test_find_line_coefficients() function:

    
    def test_find_line_coefficients():
      line = ((1,0), (1,3))
      assert find_line_coefficients(*line) == None
        
      line = ((0,0), (5,5))
      assert find_line_coefficients(*line) == (1, 0)
    
      line = ((4,5), (5,5))
      assert find_line_coefficients(*line) == (0, 5)
    
    

There is a standalone test (in its own module) for the polygon module: polygon_test. The reason this test is separate is that the polygon module has relatively a lot of code and cluttering it with test code would make it harder to navigate and less readable. The polygon_test module has multiple test functions for different aspects of the polygon module and a central test() function that runs all the specific test functions:


def test():
  test_is_triangle()
  test_split()
  test_find_second_top_point()
  test_remove_top_triangle()
  test_calc_polygon_area()
  
if __name__=='__main__':
  test()
  print 'Done.'

To test the polygon module properly different types of polygons are used as test subjects. The same group of polygons is used for multiple tests. The test polygons are defined globally at the beginning of the module as a set of vertices:


triangle = ((0,0), (0,3), (4,0))
rectangle = ((0,0), (0,3), (4,3), (4,0))
parallelogram = ((0,0), (3,1), (4,5), (1,4))
concave = ((0,0), (3,6), (6,0), (3,3))
concave2 = ((0,0), (4,6), (4,1), (5,3), (5,0))
...
concave12 = (0,1), (1,0), (1,1), (2,0), (2, 2)

When the test polygons became more complicated I added a little sketch comment to some of them. That helped a lot visualizing what happens during the algorithm execution. For example, here is the concave11 test polygon:

"""
     o
   /   \
 /      \
o   o    o
 \  | \  |
  \ |  \ |
   o     o
   
"""
concave11 = ((0,1), (1, 2), (2, 1), (2, 0), (1, 1), (1, 0))

Inside each test function Polygon objects are instantiated using the test polygon vertices. Here is the test_is_triangle() function:


def test_is_triangle():
  """ """
  p = Polygon(triangle)
  assert p.is_triangle()
  
  p = Polygon(rectangle)
  assert not p.is_triangle()
  
  p = Polygon(parallelogram)
  assert not p.is_triangle()

  p = Polygon(concave)
  assert not p.is_triangle()

  p = Polygon(concave2)
  assert not p.is_triangle()


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video