#987

Build # #987

Build Type

push

travis-ci

Committed by GitHub

Commit Message

build(deps): bump decode-uri-component in /waves/javascript_demo

Run Details

910 of 910 relevant lines covered (100.0%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/hyperbolic_tessellation/tessellation.py

"""The core implementation of a hyperbolic tessellation of the
Poincare disk by uniform, regular polygons.
"""

from collections import deque
from collections import namedtuple
from geometry import Point
from geometry import orientation
from hyperbolic import PoincareDiskLine
from hyperbolic import PoincareDiskModel
from hyperbolic import compute_fundamental_triangle
import svgwrite


class TessellationConfiguration(
        namedtuple('TessellationConfiguration',
                   ['num_polygon_sides', 'num_polygons_per_vertex'])):
    def __init__(self, num_polygon_sides, num_polygons_per_vertex):
        if not self.is_hyperbolic():
            raise ValueError("Configuration {%s, %s} is not hyperbolic." %
                             (self.num_polygon_sides, self.num_polygons_per_vertex))

    def is_hyperbolic(self):
        return (self.num_polygon_sides - 2) * (self.num_polygons_per_vertex - 2) > 4


class PolygonSet(set):
    """A helper class wrapping a set of polygons, that implements special
    checks for membership and insertion.

    We canonicalize a polygon by rounding its vertex entries, and storing
    them in a frozenset. All insertion and containment checks are done
    against the canonicalized input.
    """

    PRECISION = 5

    def _canonicalize(self, points):
        return frozenset(
            Point(round(p.x, self.PRECISION), round(p.y, self.PRECISION))
            for p in points
        )

    def add_polygon(self, points):
        """Add a polygon to the set."""
        self.add(self._canonicalize(points))

    def contains_polygon(self, points):
        """Test if a polygon is in the set."""
        return self._canonicalize(points) in self


class RenderedCoords:
    """A helper class to keep track of a transformation from the unit circle to
    a rendered image.
    """

    def __init__(self, canvas_width):
        self.canvas_width = canvas_width
        self.canvas_center = Point(canvas_width / 2, canvas_width / 2)
        self.scaling_factor = self.canvas_width / 2

    def in_rendered_coords(self, p):
        if isinstance(p, Point):
            scaled_and_reflected = Point(p.x, -p.y) * self.scaling_factor
            return self.canvas_center + scaled_and_reflected
        else:
            return p * self.scaling_factor


class HyperbolicTessellation(object):
    """A class representing a tessellation in the Poincare disk model.

    The model consists of the interior of a unit disk in the plane. Lines are
    arcs of circles perpendicular to the boundary of the disk, or diameters
    of the unit circle.
    """

    def __init__(self, configuration, max_polygon_count=500):
        self.configuration = configuration
        self.disk_model = PoincareDiskModel(Point(0, 0), radius=1)

        # compute the vertices of the center polygon via reflection
        self.center_polygon = self.compute_center_polygon()
        self.tessellated_polygons = self.tessellate(
            max_polygon_count=max_polygon_count)

    def compute_center_polygon(self):
        center, top_vertex, x_axis_vertex = compute_fundamental_triangle(
            self.configuration)
        p = self.configuration.num_polygon_sides

        """The center polygon's first vertex is the top vertex (the one that
        makes an angle of pi / q), because the x_axis_vertex is the center of
        an edge.
        """
        polygon = [top_vertex]

        p1, p2 = top_vertex, x_axis_vertex
        for i in range(p - 1):
            p2 = self.disk_model.line_through(center, p1).reflect(p2)
            p1 = self.disk_model.line_through(center, p2).reflect(p1)
            polygon.append(p1)

        return polygon

    def tessellate(self, max_polygon_count=500):
        """Return the set of polygons that make up a tessellation of the center
        polygon. Keep reflecting polygons until the Euclidean bounding box of all
        polygons is less than the given threshold.
        """
        queue = deque()
        queue.append(self.center_polygon)
        tessellated_polygons = []
        processed = PolygonSet()

        while queue:
            polygon = queue.popleft()
            if processed.contains_polygon(polygon):
                continue

            edges = [(polygon[i], polygon[(i + 1) % len(polygon)])
                     for i in range(len(polygon))]
            for u, v in edges:
                line = self.disk_model.line_through(u, v)
                reflected_polygon = [line.reflect(p) for p in polygon]
                queue.append(reflected_polygon)

            tessellated_polygons.append(polygon)
            processed.add_polygon(polygon)
            if len(processed) > max_polygon_count:
                processed.add_polygon(polygon)
                break

        return tessellated_polygons

    def render(self, filename, canvas_width):
        """Output an svg file drawing the tessellation."""
        self.transformer = RenderedCoords(canvas_width)
        self.dwg = svgwrite.Drawing(filename=filename, debug=False)

        self.dwg.fill(color='white', opacity=0)
        boundary_circle = self.dwg.circle(
            center=self.transformer.in_rendered_coords(self.disk_model.center),
            r=self.transformer.in_rendered_coords(self.disk_model.radius),
            id='boundary_circle',
            stroke='black',
            stroke_width=1)
        boundary_circle.fill(color='white', opacity=0)
        self.dwg.add(boundary_circle)

        polygon_group = self.dwg.add(self.dwg.g(
            id='polygons', stroke='blue', stroke_width=1))
        for polygon in self.tessellated_polygons:
            self.render_polygon(polygon, polygon_group)

        self.dwg.save()

    def render_polygon(self, polygon, group):
        arcs_group = group.add(self.dwg.g())

        edges = [(polygon[i], polygon[(i + 1) % len(polygon)])
                 for i in range(len(polygon))]

        for (p, q) in edges:
            line = self.disk_model.line_through(p, q)
            if isinstance(line, PoincareDiskLine):
                self.render_arc(arcs_group, line, p, q)
            else:
                line = self.dwg.line(
                    self.transformer.in_rendered_coords(p),
                    self.transformer.in_rendered_coords(q))
                arcs_group.add(line)

    def render_arc(self, group, line, from_point, to_point):
        use_positive_angle_dir = orientation(
            from_point, to_point, self.disk_model.center) == 'counterclockwise'

        p1 = self.transformer.in_rendered_coords(from_point)
        p2 = self.transformer.in_rendered_coords(to_point)
        r = self.transformer.in_rendered_coords(line.radius)
        path = self.dwg.path('m')

        path.push(p1)
        path.push_arc(
            target=p2,
            rotation=0,
            r=r,
            large_arc=False,
            angle_dir='+' if use_positive_angle_dir else '-',
            absolute=True)

        group.add(path)

1	"""The core implementation of a hyperbolic tessellation of the
2	Poincare disk by uniform, regular polygons.
3	"""
4
5	from collections import deque	1✔
6	from collections import namedtuple	1✔
7	from geometry import Point	1✔
8	from geometry import orientation	1✔
9	from hyperbolic import PoincareDiskLine	1✔
10	from hyperbolic import PoincareDiskModel	1✔
11	from hyperbolic import compute_fundamental_triangle	1✔
12	import svgwrite	1✔
13
14
15	class TessellationConfiguration(	1✔
16	namedtuple('TessellationConfiguration',
17	['num_polygon_sides', 'num_polygons_per_vertex'])):
18	def __init__(self, num_polygon_sides, num_polygons_per_vertex):	1✔
19	if not self.is_hyperbolic():	1✔
20	raise ValueError("Configuration {%s, %s} is not hyperbolic." %	1✔
21	(self.num_polygon_sides, self.num_polygons_per_vertex))
22
23	def is_hyperbolic(self):	1✔
24	return (self.num_polygon_sides - 2) * (self.num_polygons_per_vertex - 2) > 4	1✔
25
26
27	class PolygonSet(set):	1✔
28	"""A helper class wrapping a set of polygons, that implements special
29	checks for membership and insertion.
30
31	We canonicalize a polygon by rounding its vertex entries, and storing
32	them in a frozenset. All insertion and containment checks are done
33	against the canonicalized input.
34	"""
35
36	PRECISION = 5	1✔
37
38	def _canonicalize(self, points):	1✔
39	return frozenset(	1✔
40	Point(round(p.x, self.PRECISION), round(p.y, self.PRECISION))
41	for p in points
42	)
43
44	def add_polygon(self, points):	1✔
45	"""Add a polygon to the set."""
46	self.add(self._canonicalize(points))	1✔
47
48	def contains_polygon(self, points):	1✔
49	"""Test if a polygon is in the set."""
50	return self._canonicalize(points) in self	1✔
51
52
53	class RenderedCoords:	1✔
54	"""A helper class to keep track of a transformation from the unit circle to
55	a rendered image.
56	"""
57
58	def __init__(self, canvas_width):	1✔
59	self.canvas_width = canvas_width	1✔
60	self.canvas_center = Point(canvas_width / 2, canvas_width / 2)	1✔
61	self.scaling_factor = self.canvas_width / 2	1✔
62
63	def in_rendered_coords(self, p):	1✔
64	if isinstance(p, Point):	1✔
65	scaled_and_reflected = Point(p.x, -p.y) * self.scaling_factor	1✔
66	return self.canvas_center + scaled_and_reflected	1✔
67	else:
68	return p * self.scaling_factor	1✔
69
70
71	class HyperbolicTessellation(object):	1✔
72	"""A class representing a tessellation in the Poincare disk model.
73
74	The model consists of the interior of a unit disk in the plane. Lines are
75	arcs of circles perpendicular to the boundary of the disk, or diameters
76	of the unit circle.
77	"""
78
79	def __init__(self, configuration, max_polygon_count=500):	1✔
80	self.configuration = configuration	1✔
81	self.disk_model = PoincareDiskModel(Point(0, 0), radius=1)	1✔
82
83	# compute the vertices of the center polygon via reflection
84	self.center_polygon = self.compute_center_polygon()	1✔
85	self.tessellated_polygons = self.tessellate(	1✔
86	max_polygon_count=max_polygon_count)
87
88	def compute_center_polygon(self):	1✔
89	center, top_vertex, x_axis_vertex = compute_fundamental_triangle(	1✔
90	self.configuration)
91	p = self.configuration.num_polygon_sides	1✔
92
93	"""The center polygon's first vertex is the top vertex (the one that
94	makes an angle of pi / q), because the x_axis_vertex is the center of
95	an edge.
96	"""
97	polygon = [top_vertex]	1✔
98
99	p1, p2 = top_vertex, x_axis_vertex	1✔
100	for i in range(p - 1):	1✔
101	p2 = self.disk_model.line_through(center, p1).reflect(p2)	1✔
102	p1 = self.disk_model.line_through(center, p2).reflect(p1)	1✔
103	polygon.append(p1)	1✔
104
105	return polygon	1✔
106
107	def tessellate(self, max_polygon_count=500):	1✔
108	"""Return the set of polygons that make up a tessellation of the center
109	polygon. Keep reflecting polygons until the Euclidean bounding box of all
110	polygons is less than the given threshold.
111	"""
112	queue = deque()	1✔
113	queue.append(self.center_polygon)	1✔
114	tessellated_polygons = []	1✔
115	processed = PolygonSet()	1✔
116
117	while queue:	1✔
118	polygon = queue.popleft()	1✔
119	if processed.contains_polygon(polygon):	1✔
120	continue	1✔
121
122	edges = [(polygon[i], polygon[(i + 1) % len(polygon)])	1✔
123	for i in range(len(polygon))]
124	for u, v in edges:	1✔
125	line = self.disk_model.line_through(u, v)	1✔
126	reflected_polygon = [line.reflect(p) for p in polygon]	1✔
127	queue.append(reflected_polygon)	1✔
128
129	tessellated_polygons.append(polygon)	1✔
130	processed.add_polygon(polygon)	1✔
131	if len(processed) > max_polygon_count:	1✔
132	processed.add_polygon(polygon)	1✔
133	break	1✔
134
135	return tessellated_polygons	1✔
136
137	def render(self, filename, canvas_width):	1✔
138	"""Output an svg file drawing the tessellation."""
139	self.transformer = RenderedCoords(canvas_width)	1✔
140	self.dwg = svgwrite.Drawing(filename=filename, debug=False)	1✔
141
142	self.dwg.fill(color='white', opacity=0)	1✔
143	boundary_circle = self.dwg.circle(	1✔
144	center=self.transformer.in_rendered_coords(self.disk_model.center),
145	r=self.transformer.in_rendered_coords(self.disk_model.radius),
146	id='boundary_circle',
147	stroke='black',
148	stroke_width=1)
149	boundary_circle.fill(color='white', opacity=0)	1✔
150	self.dwg.add(boundary_circle)	1✔
151
152	polygon_group = self.dwg.add(self.dwg.g(	1✔
153	id='polygons', stroke='blue', stroke_width=1))
154	for polygon in self.tessellated_polygons:	1✔
155	self.render_polygon(polygon, polygon_group)	1✔
156
157	self.dwg.save()	1✔
158
159	def render_polygon(self, polygon, group):	1✔
160	arcs_group = group.add(self.dwg.g())	1✔
161
162	edges = [(polygon[i], polygon[(i + 1) % len(polygon)])	1✔
163	for i in range(len(polygon))]
164
165	for (p, q) in edges:	1✔
166	line = self.disk_model.line_through(p, q)	1✔
167	if isinstance(line, PoincareDiskLine):	1✔
168	self.render_arc(arcs_group, line, p, q)	1✔
169	else:
170	line = self.dwg.line(	1✔
171	self.transformer.in_rendered_coords(p),
172	self.transformer.in_rendered_coords(q))
173	arcs_group.add(line)	1✔
174
175	def render_arc(self, group, line, from_point, to_point):	1✔
176	use_positive_angle_dir = orientation(	1✔
177	from_point, to_point, self.disk_model.center) == 'counterclockwise'
178
179	p1 = self.transformer.in_rendered_coords(from_point)	1✔
180	p2 = self.transformer.in_rendered_coords(to_point)	1✔
181	r = self.transformer.in_rendered_coords(line.radius)	1✔
182	path = self.dwg.path('m')	1✔
183
184	path.push(p1)	1✔
185	path.push_arc(	1✔
186	target=p2,
187	rotation=0,
188	r=r,
189	large_arc=False,
190	angle_dir='+' if use_positive_angle_dir else '-',
191	absolute=True)
192
193	group.add(path)	1✔

pim-book / programmers-introduction-to-mathematics / #987

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous