Channels ▼


The PolyArea Project: Part 2


In this type of program there are many gotchas that you should be aware of and pay attention to.

Coordinate Systems. It is critical when dealing with multiple coordinate systems to make sure you are always using the correct coordinate systems. In, the case of PolyArea the window coordinate system is used for rendering, but the grid coordinate system, which is shifted by the grid padding width and height is used for computation.

The current configuration values set the grid padding to 10. That means that a point such as (40, 40) in the window coordinate system is just (30, 30) in the grid coordinate system. If you mix these coordinate systems and neglect to translate some points you get nasty bugs that are very hard to detect. The approach to address it is to explicitly identify the location in your code (e.g. the mouse event handlers) where you get input in one coordinate system and make sure you convert each point.

Fractured Pixels. The mouse events and snap to grid processing generate integral numbers. Various computations for intersections generate floating point numbers. Mixing them up can sometimes hurt you in unexpected ways. For example, the Python division operation works differently for integers and floating-point numbers.

Integer division. The integer division in Python 2.x is floor division (in Python 3 that has changed).

>>> 3 / 5

If you expected 0.6 you are in for a surprise.

You can find the remainder using the % (modulo) operator:

>>> 3 % 5

Floating-point numbers. Computers represent fractions normally as floating-point numbers. In Python, there is the float data type. Due to the this representation scheme (2's complement) some fractions can be represented only approximately. This can lead to unexpected results:

>>> 3 / 5.0

Yes, you will not get 0.6 even with floating-point numbers. When mixing integers and floats, point the integers are promoted to floats.

Rounding. Rounding is also a potentially confusing aspect. Python has the round() function that rounds to the nearest integer and also the math.floor() and math.ceil(). In PolyArea I needed a special rounding operation to round an integer to the closest multiple of another integer. This was needed to find the closest grid point. I came up with this function that uses both Python's regular division operation / and the floor division // (which always does floor didivision even if some of the operands are floats):

def round_int(n, r):
  """Rounds an integer n to the closest multiple of an integer r"""
  return int(n + r / 2) // r * r

Dimensional reversal. Another issue to be aware of is the axis. In mathematics it is common for the Y dimension to grow up (smaller numbers are bellow larger number). It is even customary to say low and high numbers, were "high" numbers are larger. In computer graphics on the other hand the X dimension runs from left to right, but the Y dimension runs from top to bottom (a takeaway from the display hardware scanning order).

Does it matter? Well, that depends on your expectations. In the last article when I discussed the algorithm and I mentioned finding top points and removing top triangles I was using the standard math dimensions. But, when PolyArea actually renders the polygons on the screen everything is flipped on its head. That means that visually PolyArea scans from the bottom up and finds bottom points and removes bottom triangles first; see Figure 7.

[Click image to view at full size]
Figure 7


PolyArea was a fun project. I enjoyed working with Saar and I was surprised by how challenging it turned out to be. The program itself and the process were pretty educational and the end result is cool and entertaining.

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.