From cb021ade17bfad70dd2c957ebfa1bf0edb857300 Mon Sep 17 00:00:00 2001 From: "W. Trevor King" Date: Sun, 28 Mar 2010 01:03:53 -0400 Subject: [PATCH] Added actual center-of-mass calculation for territories. 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 | 211 ++++++++++++++++++++++++---- share/templates/earth/continent.col | 1 + share/templates/earth/gbr.reg | 10 +- share/templates/earth/jap.reg | 8 +- share/templates/earth/line.col | 1 + share/templates/earth/ngu.reg | 16 +-- 6 files changed, 199 insertions(+), 48 deletions(-) diff --git a/pyrisk/graphics.py b/pyrisk/graphics.py index 32cc46e..7085eb3 100644 --- a/pyrisk/graphics.py +++ b/pyrisk/graphics.py @@ -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([ '' % ' '.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([ - '' % (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 diff --git a/share/templates/earth/continent.col b/share/templates/earth/continent.col index 7b935ab..d344028 100644 --- a/share/templates/earth/continent.col +++ b/share/templates/earth/continent.col @@ -4,3 +4,4 @@ Asia green South America red Africa orange Australia purple +_opacity 0.5 diff --git a/share/templates/earth/gbr.reg b/share/templates/earth/gbr.reg index 0d715b2..a731189 100644 --- a/share/templates/earth/gbr.reg +++ b/share/templates/earth/gbr.reg @@ -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 diff --git a/share/templates/earth/jap.reg b/share/templates/earth/jap.reg index 0a546d9..c2e666e 100644 --- a/share/templates/earth/jap.reg +++ b/share/templates/earth/jap.reg @@ -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 diff --git a/share/templates/earth/line.col b/share/templates/earth/line.col index 0db4841..057b61a 100644 --- a/share/templates/earth/line.col +++ b/share/templates/earth/line.col @@ -1,3 +1,4 @@ border grey route black virtual route - +army white diff --git a/share/templates/earth/ngu.reg b/share/templates/earth/ngu.reg index 09af2df..cbdc461 100644 --- a/share/templates/earth/ngu.reg +++ b/share/templates/earth/ngu.reg @@ -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 -- 2.26.2