Added actual center-of-mass calculation for territories.
authorW. Trevor King <wking@drexel.edu>
Sun, 28 Mar 2010 05:03:53 +0000 (01:03 -0400)
committerW. Trevor King <wking@drexel.edu>
Sun, 28 Mar 2010 05:05:02 +0000 (01:05 -0400)
Also:
* Added CCW check in Region._generate_outline.
* Added attribute control (e.g. opacity) for continent color templates.
* Added army outline color control to templates.
* Removed unnecessary label_offset attribute from Region.

pyrisk/graphics.py
share/templates/earth/continent.col
share/templates/earth/gbr.reg
share/templates/earth/jap.reg
share/templates/earth/line.col
share/templates/earth/ngu.reg

index 32cc46e..7085eb3 100644 (file)
@@ -99,16 +99,19 @@ class TemplateLibrary (object):
             pointlist.append((x,y,label))
         return pointlist
     def _read_colors(self, filename):
-        colors = {}
+        colors = {'_attributes': {}}
         for line in open(filename, 'r'):
             line = line.strip()
             if len(line) == 0:
                 continue
             fields = line.split('\t')
-            name,color = [x.strip() for x in fields]
-            if color == '-':
-                color = None
-            colors[name] = color
+            name,value = [x.strip() for x in fields]
+            if value == '-':
+                value = None
+            if name.startswith('_'): # attribute setting
+                colors['_attributes'][name[1:]] = value
+            else: # continent color
+                colors[name] = value
         return colors
     def _generate_regions(self, region_pointlists, route_pointlists):
         regions = []
@@ -200,7 +203,7 @@ TEMPLATE_LIBRARY = TemplateLibrary()
 
 
 class Vector (tuple):
-    """Simple vector addition and subtraction.
+    """Simple cartesian vector operations.
 
     >>> v = Vector
     >>> a = v((0, 0))
@@ -214,6 +217,10 @@ class Vector (tuple):
     (-1, -2)
     >>> -c
     (-2, -3)
+    >>> b*0.5
+    (0.5, 0.5)
+    >>> c*(1, -1)
+    (2, -3)
     >>> a < b
     True
     >>> c > b
@@ -232,6 +239,16 @@ class Vector (tuple):
         new = self.__class__(map(operator.neg, self))
         self._set_name(new)
         return new
+    def mag(self):
+        """Return the magnitude.
+        """
+        return math.sqrt(sum([x**2 for x in self]))
+    def angle(self):
+        """Return the direction (must be in 2D).
+        """
+        if len(self) != 2:
+            raise ValueError('length != 2, %s' % (self))
+        return math.atan2(self[1], self[0])
     def __add__(self, other):
         if len(self) != len(other):
             raise ValueError('length missmatch %s, %s' % (self, other))
@@ -245,10 +262,48 @@ class Vector (tuple):
         self._set_name(new, other)
         return new
     def __mul__(self, other):
+        """Return the elementwise product (with vectors) or scalar
+        product (with numbers).
+        """
+        if hasattr(other, '__iter__'): # dot product
+            if len(self) != len(other):
+                raise ValueError('length missmatch %s, %s' % (self, other))
+            new = self.__class__([s*o for s,o in zip(self, other)])
+            #map(operator.mul, self, other))
+        else: # scalar product
+            new = self.__class__([x*other for x in self])
+        self._set_name(new, other)
+        return new
+    def triple_angle(self, previous, next):
+        """Return the angle between (previous->self) and (self->next)
+        in radians.
+        """
+        angle = (next-self).angle() - (self-previous).angle()
+        while angle > math.pi:
+            angle -= 2*math.pi
+        while angle < -math.pi:
+            angle += 2*math.pi
+        return angle
+    def cross(self, other):
+        """Return the cross product.
+        
+        In 2D, just return the z component of the result.
+        """
         if len(self) != len(other):
             raise ValueError('length missmatch %s, %s' % (self, other))
-        new = self.__class__(map(operator.mul, self, other))
-        self._set_name(new, other)
+        if len(self) not in [2,3]:
+            raise ValueError('cross product not defined in %dD, %s, %s'
+                             % (len(self), self, other))
+        if len(self) == 2:
+            s = self.__class__((self[0], self[1], 0))
+            o = self.__class__((other[0], other[1], 0))
+        else:
+            s = self; o = other
+        new = self.__class__((s[1]*o[2]-s[2]*o[1],
+                              -s[0]*o[2]-s[2]*o[0],
+                              s[0]*o[1]-s[1]*o[0]))
+        if len(self) == 2:
+            return new[2]
         return new
 
 def nameless(vector):
@@ -287,20 +342,27 @@ class Route (ID_CmpMixin):
 class Region (NameMixin, ID_CmpMixin, list):
     """Contains a list of boundaries and a label.
 
-    Regions can be Territories, sections of ocean, etc.
+    Regions can be Territories or pieces of Territories (e.g separate
+    islands, such as in Indonesia).
+
+    Boundaries must be entered counter clockwise (otherwise you
+    will get an error).
 
     >>> r = Region('Earth',
-    ...            [Boundary([(0,0), (0,1)]),
-    ...             Boundary([(0,0), (1,0)]),
-    ...             Boundary([(0,0), (0,1)]),
-    ...             Boundary([(0,0), (1,0)])],
-    ...            [True, True, False, False],
-    ...            (0.5, 0.5))
+    ...            [Boundary([(0,0), (10,0)]),
+    ...             Boundary([(0,0), (0,10)]),
+    ...             Boundary([(0,0), (10,0)]),
+    ...             Boundary([(0,0), (0,10)])],
+    ...            [True, True, False, False])
     >>> r.outline
-    [(0, 0), (0, 1), (1, 1), (1, 0), (0, 0)]
+    [(0, 0), (10, 0), (10, 10), (0, 10), (0, 0)]
+    >>> r.area()
+    100.0
+    >>> r.center_of_mass()
+    (5, 5)
     """
     def __init__(self, name, boundaries, head_to_tail, routes=None,
-                 route_head_to_tail=None, label_offset=(0,0)):
+                 route_head_to_tail=None):
         NameMixin.__init__(self, name)
         list.__init__(self, boundaries)
         ID_CmpMixin.__init__(self)
@@ -314,7 +376,6 @@ class Region (NameMixin, ID_CmpMixin, list):
             self.routes = []
             self.route_head_to_tail = []
         self.route_starts = [] # set by .locate_routes
-        self.label_offset = Vector(label_offset)
         self.generate_outline() # sets .outline, .starts
         self.x_min = min([b.x_min+s[0] for b,s in zip(self, self.starts)])
         self.x_max = max([b.x_max+s[0] for b,s in zip(self, self.starts)])
@@ -341,8 +402,13 @@ class Region (NameMixin, ID_CmpMixin, list):
             self.starts.append(pos)
             for p in new:
                 points.append(pos+p)
-        assert points[-1] == points[0], '%s: %s' % (self, points)
+        assert points[-1] == points[0], '%s: %s (not closed)' % (self, points)
         self.outline = points
+        total_angle = 0
+        for prev,p,next in self._unique_triples():
+            total_angle += p.triple_angle(prev, next)
+        assert abs(total_angle-2*math.pi) < 0.1, \
+            "%s: %s (not CCW: %.2f)" % (self, points, total_angle)
     def locate_routes(self):
         self.route_starts = []
         for route,htt in zip(self.routes, self.route_head_to_tail):
@@ -354,9 +420,81 @@ class Region (NameMixin, ID_CmpMixin, list):
                 if hasattr(point, 'name') and point.name == anchor.name:
                     self.route_starts.append(point-nameless(anchor))
                     break
+    def area(self):
+        """Return the region's enclosed area as a float.
+        """
+        return sum([self._triangle_area(a,b,c) for a,b,c in self._triangles()])
+    def center_of_mass(self):
+        """Return a vector locating the region's center of mass.
+
+        Truncated to the lower-left pixel.
+        """
+        cas = []
+        for a,b,c in self._triangles():
+            cas.append((self._triangle_center_of_mass(a,b,c),
+                        self._triangle_area(a,b,c)))
+        m = sum([a for c,a in cas])
+        average = Vector((int(sum([c[0]*a for c,a in cas])/m),
+                          int(sum([c[1]*a for c,a in cas])/m)))
+        return average
+    def _unique_triples(self):
+        """Iterate through consecutive triples (prev, p, next)
+        for every unique point in self.outline.
+        """
+        unique = self.outline[:-1]
+        assert len(unique) >= 3, \
+            '%s: %s (< 3 unique points)' % (self, self.outline)
+        for i,p in enumerate(unique):
+            prev = unique[i-1]
+            next = unique[(i+1)%len(unique)]
+            yield (prev, p, next)
+    def _triangles(self):
+        """Iterate through CCW triangles composing the region.
+
+        >>> r = Region('Earth',
+        ...            [Boundary([(0,0),(1,-1),(0,3),(-1,0),(0,0)])],
+        ...            [True])
+        >>> for triangle in r._triangles():
+        ...     print triangle
+        ((0, 0), (1, -1), (0, 3))
+        ((-1, 0), (0, 0), (0, 3))
+        """
+        points = self.outline[:-1]
+        while len(points) >= 3:
+            for i,p in enumerate(points):
+                prev = points[i-1]
+                next = points[(i+1)%len(points)]
+                if p.triple_angle(prev, next) > 0:
+                    break # found first CCW triangle
+            points.remove(p) # drop the outer point
+            yield (prev, p, next)
+    def _triangle_area(self, a, b, c):
+        """
+        >>> r = Region('Earth',
+        ...            [Boundary([(0,0), (1,0), (1,1), (0,0)])],
+        ...            [True])
+        >>> triangle = r.outline[:3]
+        >>> triangle
+        [(0, 0), (1, 0), (1, 1)]
+        >>> r._triangle_area(*triangle)
+        0.5
+        """
+        return abs(0.5 * (b-a).cross(c-a))
+    def _triangle_center_of_mass(self, a, b, c):
+        """
+        >>> r = Region('Earth',
+        ...            [Boundary([(0,0), (1,0.3), (0.5,1.2), (0,0)])],
+        ...            [True])
+        >>> triangle = r.outline[:3]
+        >>> ['(%.2f, %.2f)' % x for x in triangle]
+        ['(0.00, 0.00)', '(1.00, 0.30)', '(0.50, 1.20)']
+        >>> r._triangle_center_of_mass(*triangle)
+        (0.5, 0.5)
+        """
+        return (a+b+c)*(1/3.)
 
 class WorldRenderer (object):
-    def __init__(self, template_lib=None, line_width=2, buf=10, dpcm=60):
+    def __init__(self, template_lib=None, line_width=2, buf=10, dpcm=50):
         self.template_lib = template_lib
         if self.template_lib == None:
             self.template_lib = TEMPLATE_LIBRARY
@@ -391,15 +529,20 @@ class WorldRenderer (object):
             else:
                 terr_regions[t.name] = [r]
             c_col = template.continent_colors[t.continent.name]
+            if len(template.continent_colors['_attributes']) == 0:
+                c_col_attr = ''
+            else:
+                attrs = template.continent_colors['_attributes'].items()
+                c_col_attr = ''.join([' %s="%s"' % (k,v) for k,v in attrs])
             if template.line_colors['border'] == None:
                 b_col_attr = ''
             else:
-                b_col_attr = 'stroke="%s" stroke-width="%d"' \
+                b_col_attr = ' stroke="%s" stroke-width="%d"' \
                     % (template.line_colors['border'], self.line_width)
             lines.extend([
                     '<polygon title="%s / %s / %s"'
                     % (t, t.player, t.armies),                    
-                    '         fill="%s" %s' % (c_col, b_col_attr),
+                    '         fill="%s"%s%s' % (c_col, c_col_attr, b_col_attr),
                     '         points="%s" />'
                     % ' '.join(['%d,%d' % ((region_pos[id(r)]+p)
                                            *(1,-1) # svg y value increases down
@@ -432,9 +575,15 @@ class WorldRenderer (object):
             color = template.player_colors[players.index(t.player)]
             if color == None:
                 continue
+            if template.line_colors['army'] == None:
+                b_col_attr = ''
+            else:
+                b_col_attr = ' stroke="%s" stroke-width="%d"' \
+                    % (template.line_colors['army'], self.line_width)
+                radius += self.line_width/2.
             lines.extend([
-                    '<circle title="%s / %s / %s" fill="%s"'
-                    % (t, t.player, t.armies, color),
+                    '<circle title="%s / %s / %s"' % (t, t.player, t.armies),
+                    '         fill="%s"%s' % (color, b_col_attr),
                     '         cx="%d" cy="%d" r="%.1f" />'
                     % (center[0], center[1]*-1+height, radius),
                     ])
@@ -506,15 +655,15 @@ class WorldRenderer (object):
         return t
     def _territory_center(self, region_pos, regions):
         """Return the center of mass of a territory composed of regions.
-
-        Note: currently not CM, just averages outline points.
         """
-        points = []
+        cas = []
         for r in regions:
-            for p in r.outline:
-                points.append(p + region_pos[id(r)])
-        average = Vector((int(sum([p[0] for p in points])/len(points)),
-                          int(sum([p[1] for p in points])/len(points))))
+            center = r.center_of_mass() + region_pos[id(r)]
+            area = r.area()
+            cas.append((center, area))
+        m = sum([a for c,a in cas])
+        average = Vector((int(sum([c[0]*a for c,a in cas])/m),
+                          int(sum([c[1]*a for c,a in cas])/m)))
         return average
     def _auto_template(self, world):
         raise NotImplementedError
index 7b935ab..d344028 100644 (file)
@@ -4,3 +4,4 @@ Asia    green
 South America  red
 Africa orange
 Australia      purple
+_opacity       0.5
index 0d715b2..a731189 100644 (file)
@@ -1,8 +1,8 @@
 479    247     n scotland
-483    254     dep-grb-multi
-499    293     dover
-482    304     dep-gbr-to-weu
-470    306     lands-end?
-480    287     ne wales
 466    255     skye
+480    287     ne wales
+470    306     lands-end?
+482    304     dep-gbr-to-weu
+499    293     dover
+483    254     dep-grb-multi
 479    247     n scotland
index 0a546d9..c2e666e 100644 (file)
@@ -1,7 +1,7 @@
 845    292     jap-to-multi
-844    255
-861    260
-862    305
-833    336
 826    327
+833    336
+862    305
+861    260
+844    255
 845    292     jap-to-multi
index 0db4841..057b61a 100644 (file)
@@ -1,3 +1,4 @@
 border grey
 route  black
 virtual route  -
+army   white
index 09af2df..cbdc461 100644 (file)
@@ -1,11 +1,11 @@
 823    462     dep-ngu-multi
-817    451
-822    444
-862    458
-872    483
-867    486
-841    480
-835    476
-835    468
 831    464
+835    468
+835    476
+841    480
+867    486
+872    483
+862    458
+822    444
+817    451
 823    462     dep-ngu-multi