Channels ▼
RSS

Open Source

The PolyArea Project: Part 2


The PolyArea UI

The user interface of PolyArea is very simple: You can draw a polygon, you can clear a polygon, and once a polygon is complete you can visualize and find its area incrementally.

Drawing a Polygon. This operation is performed with the mouse. You start by clicking anywhere on the empty grid. Now, when you move your mouse a line is drawn from the first clicked point to the current mouse position. If you click again the current line becomes permanent (part of the polygon) and from its end a new temporary line is drawn to the current mouse position. This continues until you close the polygon by clicking again on the first point. There are a few more details. The PolyArea program will constrain you to grid points only to avoid too crowded polygons that don't look nice. This also helps when you want to close the polygon. The last feature is that PolyArea will not let you create invalid polygons where lines cross (or touch) other polygon lines. You can still get yourself in trouble and find yourself in a situation where you have nowhere to go (e.g. if you create an unclosed polygon that covers all the grid points). It is pretty easy to avoid it and if worse come to worst you can always clear the current polygon and start all over.

Clearing a Polygon. You can clear the current (potentially unclosed) polygon any time. Just press n (for "new") on the keyboard and the grid will be cleared.

Incrementally Finding the Area. When you close a polygon PolyArea will immediately triangulate it. Now, you can observe your handiwork by repeatedly pressing the Spacebar. PolyArea will paint a triangle every time you press the Spacebar and update the text display with the accumulated area of the triangles. Once the polygon is fully painted, further key presses on the Spacebar will do nothing. You can now clear the polygon by pressing n and start a new polygon.

Many aspects of the look-and-feel such window size, line widths, and colors can be customized by editing the config.py file. Fill free to play with it. It's a Python file, but it's very similar to a simple .ini file with a list of key,value pairs:


<code>
# Main Window
main_window_bg_color = (255,) * 3
main_window_size = (830, 620)
main_window_title = 'Poly GUI'

# Grid
grid_delta_x = 30
grid_delta_y = 30
grid_padding = 10
grid_bg_color = (255, 255, 200),
grid_border_color = (10,100,10),
grid_line_color = (150, 150, 255)

# Triangle
triangle_border_color = (255, 0, 255)
triangle_bg_color = triangle_border_color

# Area text
text_color = (255, 0, 0)
text_size = 36
text_pos = (main_window_size[0] - 200, main_window_size[1] - 50)
</code>

The ui.py file is the entry point to the program. When you launch it the main() function is called. The main function creates a PolyMainLoop object with the appropriate window size, title and background color, creates and adds a Grid object and finally creates and adds a Text object to display the area of the polygon (initially just "???"). Once all the preparations are done it calls the main loop's run() so it can start handling events and interact with the user. Most of the constants come from the above mentioned config.py file.


<code>
def main(render_func=nop):
  mainloop = PolyMainLoop(main_window_size,
                          main_window_title,
                          main_window_bg_color)
  # Create grid object
  delta_x = 30
  delta_y = 30
  padding = 10
  grid = Grid(rect=pygame.rect.Rect(grid_padding,
                                    grid_padding,
                                    main_window_size[0] - 2 * grid_padding,
                                    main_window_size[1] - 2 * padding),
              delta_x=grid_delta_x,
              delta_y=grid_delta_y,
              background_color=grid_bg_color,
              border_color=grid_border_color,
              line_color=grid_line_color )
  # Add grid to the main loop's list of objects
  mainloop.objects.append(grid)
  mainloop.objects.append(Text('Area: ???',
                               size=text_size,
                               color=text_color,
                               pos=text_pos))
    
  # Run the main loop
  mainloop.run()
  
if __name__=='__main__':
  main()

</code>

The PolyAreaMainLoop

This class drives the dynamic interaction of PolyArea with the user. It handles mouse and keyboard events, updates the objects list and invokes the algorithmic core when a polygon is closed. The __init__() method initializes the generic MainLoop base class and defines a bunch of state variables needed to keep track of the current polygon. Remember that the main() function adds the fixed Grid and Text object to the object list after PolyMainLoop is created.


<code>
class PolyMainLoop(MainLoop):
  def __init__(self, screen_size, caption, background_color=(255, 255, 255)):
    MainLoop.__init__(self, screen_size, caption, background_color)
    self.prevPos = None
    self.startpos = None
    self.oldLine = None
    self.polygon_complete = False
    self.area = 0
    self.firstPoint = None
    self.triangles = []
</code>

PolyMainLoop gets the run() implementation from its base class and just overrides the handle_events() method. It gets a list of PyGame events and starts processing them. If the QUIT event is received it just exits the program. There is no need to shutdown cleanly or persist anything. Mouse events are handled by dedicated methods (_onMouseDown() and _onMouseMove()). Keyboard events are checked: If Spacebar is pressed the _paint_next_triangle() method is called and if n is pressed the object list is cleared except for the grid and text objects and the internal state is reset (the _reset() method).


<code>
  def handle_events(self, events):
    for event in events: 
      if event.type == pygame.QUIT: 
        sys.exit() 
      elif event.type == pygame.MOUSEBUTTONDOWN:
        self._onMouseDown(event)
      elif event.type == pygame.MOUSEMOTION:
        self._onMouseMove(event)
      elif event.type == pygame.KEYDOWN:
        if event.key == pygame.K_SPACE:
          self._paint_next_triangle()
        elif event.key == pygame.K_n:
          # Keep just the grid and the area text
          self.objects = self.objects[:2]
          self._reset()
</code>

Let's follow the normal interaction of the user with program. Nothing important happens until the first click, so the first interesting event is handled by _onMouseDown(). This function accepts a PyGame event object that contains the current position of the mouse.

Handling mouse clicks starts by trying to bail out early. If the polygon is already complete then there is no need to respond to mouse clicks:


<code>
  def _onMouseDown(self, event):
    """ """
    if self.polygon_complete:
      return
</code>

If the user clicks multiple times on the same spot only the first click should be handled.</p>

<code>
    # Ignore repeated clicks on the same spot
    if self.prevPos == event.pos:
      return

    self.prevPos = event.pos
</code>

Now it tried to translate the exact mouse position to a nearby grid point by calling the fixPoint() method. This method is the most complicated code of the UI and it may or may not find a grid point that satisfies all the constraints in the vicinity of event.pos. If it finds a suitable grid point, it returns it (Figure 5); otherwise it returns "None". If no grid point is found, the mouse click is ignored.

[Click image to view at full size]
Figure 5


<code>    
    sp = self.fixPoint(event.pos)
    if not sp:
      return
</code>

The last check is repeated clicks on the fixed first point. This is a special case and can happen if after the clicking for the first time the user moves the mouse just a little bit.


<code>
    # Ignore repeated clicks on the first point
    if self.oldLine is not None:
      if sp == self.oldLine.startpos == self.oldLine.endpos:
        return
</code>

At this stage, we are clear and can actually process the mouse click. self.startpos gets the fixed click point and becomes the start point of a new polygon line. Also, if this is the first click we store it as self.firstPoint.


<code>
    self.startpos = sp
    
    if self.firstPoint is None:
      self.firstPoint = sp
</code>

If there was an old temporary line, then this line now becomes a permanent polygon line. A Line object is created (going from oldLine.startpos to current point) and added to the object list.


<code>
    if self.oldLine is not None:
      line = Line(color=(0, 255, 0),
                  startpos=self.oldLine.startpos,
                  endpos=self.startpos,
                  width=3)
      self.objects.append(line)
</code>

If the current point is the first point, then it means the polygon has just been closed. The oldLine is removed (no more temporary lines) and the algorithmic core is invoked.


<code>
      if self.startpos == self.firstPoint:
        self.objects.remove(self.oldLine)
        self.oldLine = None
        self.polygon_complete = True
        self._do_algorithm()
</code>

Let's see what happens when the mouse moves.

Handling mouse motion. When the mouse moves the program can be in several states. If the current polygon is complete or if there is no polygon at all, then mouse motion can be ignored.


<code>
  def _onMouseMove(self, event):
    """ """
    if self.polygon_complete:
      return
    if self.startpos is None:
      return
</code>

If there was an old temporary line it needs to be removed.


<code>    
    # Remove old line
    if self.oldLine is not None and self.oldLine in self.objects:
      self.objects.remove(self.oldLine)
</code>

If the fixed mouse position is invalid, then no temporary line will be drawn and the users will have to move their mouse to a valid position.


<code>
    end_pos = self.fixPoint(event.pos)    
    if end_pos is None:
      return
</code>

At this stage everything is fine and a new Line object is created from the last fixed click position (self.startpos) to the current fixed mouse position. This Line object is appended to the objects list so it will be rendered on the screen. Finally, a reference to this line is stored in self.oldLine so it can be removed later.


<code>
    # Add current line to mainloop's objects
    line = Line(color=(255, 0, 0),
                startpos=self.startpos,
                endpos=end_pos,
                width=3)
    self.objects.append(line)
    
    # Remember the current line so it can be removed when the mouse moves
    self.oldLine = line
</code>
    

How to fix a point. When users move the mouse around or clicks it, PolyArea doesn't use the exact mouse position. Instead it looks for the nearest grid point that doesn't intersect or touch any existing polygon line. The fixPoint() method uses various helper methods and functions that I will not cover in detail.

The first thing it does is create a special function called s2g by doing partial application of the generic snapToGrid() function with the actual grid and the distance between columns and rows (dx and dy). This is a neat functional where you use the functools.partial() function to turn a function with some arguments to a function where some of the arguments are fixed.


<code>
  def fixPoint(self, point):
    grid = self.objects[0]
    dx = grid.delta_x
    dy = grid.delta_y

    s2g = partial(snapToGrid, dx=dx, dy=dy, grid=grid)
</code>

For drawing purposes the coordinate system is based on the window itself (0,0 is top left corner of the window), but for computation purposes it is better to work based on the grid coordinate system (0,0 is the top left corner of the grid) so both the target point and the start point of the current line (if there is one) are converted to the grid coordinates using the window2grid() function.


</code>
    # Normalize the point to the grid
    w2g = window2grid
    sp = w2g(self.startpos, grid) if self.startpos else None
    p = w2g(point, grid)
</code>

If there is no current line then simply snap the point to the grid, convert it back from grid to the window coordinate system and return it. That's the easy case.


<code>
    # It's the first point
    if not sp or not self.firstPoint:
      return grid2window(s2g(p), grid)
</code>

At this point the polygon lines are computed. There is no need to fix them because they are already on grid points, but they need to be converted to the grid coordinate system.


<code>
    # Find all the polygon lines  
    poly_lines = [x for x in self.objects if isinstance(x, Line)]
    # Remove the oldLine
    if self.oldLine in poly_lines:
      poly_lines.remove(self.oldLine)
    # Convert polylines to grid co-ordinates  
    poly_lines = [(w2g(line.startpos, grid), w2g(line.endpos, grid))
                  for line in poly_lines]
</code>

If the current point and its snapped to grid point don't intersect or overlap any polygon line (that's what _checkEndPoint() checks) then return the current point.


<code>
    if self._checkEndPoint(sp, p, poly_lines, s2g):
      return grid2window(s2g(p), grid)
</code>

If we got here it's possible the line from self.startpos to the current point intersects with other polygon lines.


<code>    
    intersections = self._findIntersections(sp, p, poly_lines, s2g)
</code>

Now, if there were any intersections the code restricts the target point to the nearest intersection. The nearest intersection is found by calculating the distance to each intersection point.


<code>
    # If there are any real intersections
    if intersections:
      # There were intersections. Find the nearest one and restrict the point
      # to the nearest grid point that doesn't intersect.
      nearest = None
      distance = sys.maxint
      
      # Find the nearest intersection by iterating over
      # all the intersection points and keeping the intersection point
      # whose distance from the start position is the shortest.
      for intersection in intersections:
        d = helpers.calc_distance(intersection, sp)
        if d < distance:
          distance = d
          nearest = intersection
                
      xp = s2g(nearest)
</code>      

The next step is to find all the neighboring points.


<code>
      #Find all potential 8 neighbors
      neighbours = [
        (xp[0] - dx, xp[1] - dy),
        (xp[0], xp[1] - dy),
        (xp[0] + dx, xp[1] - dy),
        (xp[0] - dx, xp[1]),
        (xp[0] + dx, xp[1]),
        (xp[0] - dx, xp[1] + dy),
        (xp[0], xp[1] + dy),
        (xp[0] + dx, xp[1] + dy),
        ]
</code>

If the corrected intersection point was on the edge or corner of the grid, then some neighbors are outside the grid and must be filtered out.


<code>
      # Eliminate neighbors outside the grid (if xp is on edge or corner)
      all_neighbours = neighbours[:]
      neighbours = [n for n in neighbours if
                    (0 <= n[0] < grid.rect[2] - grid.rect[0]) and
                    (0 <= n[1] < grid.rect[3] - grid.rect[1])]
      
      assert neighbours != []
</code>

Now, that the candidate list (xp and all its valid neighbors) has been assembled the closest valid point is selected. The distance to each candidate that passes and if its closer than the current best candidate AND if it passes the _checkEndPoint() method then it becomes the selected point (see Figure 6).

[Click image to view at full size]
Figure 6


<code>
      # Calculate the distance of each neighbour from the start point
      # and pick the closest one
      p = None
      selected_seg = None
      distance = sys.maxint
      
      for i, n in enumerate([xp] + neighbours):
        #d = helpers.calc_distance(n, sp)
        d = helpers.calc_distance(n, point)
        if d < distance:
          if self._checkEndPoint(sp, n, poly_lines, s2g):
            distance = d
            p = n
</code>
       

It is entirely possible that no valid neighbor will be found. In this case just return None and the current line will stay the same even though the mouse moved or the mouse click will be ignored.


<code>
      if not p:
        return None
</code>   

But, if a valid point is found convert it back to the window coordinates system and return it.


<code>
    p = s2g(p)
    # Offset the result point back to the main window coordinate system
    p = grid2window(p, grid)
    
    return p
</code>


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