geometry.py

Wed, 31 Jan 2018 14:36:36 +0200

author
Santeri Piippo
date
Wed, 31 Jan 2018 14:36:36 +0200
changeset 33
d91dfc6056a3
parent 31
02e7e1d73ebb
child 38
66c9591b733d
permissions
-rw-r--r--

add LICENSE

7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
1 def degree_rep(angle):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
2 from math import degrees
22
9bb00170780b refactor
Santeri Piippo
parents: 15
diff changeset
3 return '%.2f°' % degrees(angle)
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
4
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
5 def position_vector(vertex):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
6 assert isinstance(vertex, Vertex)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
7 return Vector(*vertex.coordinates)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
8
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
9 def angle_magnitude_key(angle):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
10 '''
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
11 Returns how great an angle is.
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
12 '''
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
13 from math import pi as π
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
14 normalized_angle = abs(angle) % (2 * π)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
15 if normalized_angle > π:
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
16 normalized_angle = (2 * π) - normalized_angle
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
17 return normalized_angle
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
18
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
19 class Vertex:
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
20 def __init__(self, x, y, z):
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
21 if not all(is_real(coordinate) for coordinate in (x, y, z)):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
22 raise ValueError(str.format('Bad vertex coordinates: {!r}',
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
23 (x, y, z),
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
24 ))
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
25 self.x, self.y, self.z = x, y, z
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
26 def __repr__(self):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
27 return str.format('Vertex({!r}, {!r}, {!r})', self.x, self.y, self.z)
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
28 def distance_to(self, other):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
29 # can't use hypot because of 3 arguments
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
30 from math import sqrt
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
31 return sqrt(
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
32 (self.x - other.x) ** 2 +
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
33 (self.y - other.y) ** 2 +
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
34 (self.z - other.z) ** 2
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
35 )
3
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
36 @property
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
37 def coordinates(self):
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
38 return self.x, self.y, self.z
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
39 def __add__(self, other):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
40 assert not (type(self) == type(other) == Vertex)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
41 if type(self) == Vector and type(other) == Vector:
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
42 result_type = Vector
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
43 else:
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
44 result_type = Vertex
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
45 return result_type(self.x + other.x, self.y + other.y, self.z + other.z)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
46 def __radd__(self, other):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
47 return self + other
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
48 def __neg__(self):
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
49 return type(self)(-self.x, -self.y, -self.z)
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
50 def __sub__(self, other):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
51 result = self + (-position_vector(other))
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
52 if isinstance(other, Vertex):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
53 return Vector(*result.coordinates)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
54 else:
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
55 return result
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
56 def __mul__(self, scalar):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
57 assert is_real(scalar)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
58 return type(self)(self.x * scalar, self.y * scalar, self.z * scalar)
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
59 def __rmul__(self, other):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
60 return self * other
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
61 def __truediv__(self, scalar):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
62 assert is_real(scalar)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
63 return type(self)(self.x / scalar, self.y / scalar, self.z / scalar)
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
64 def __floordiv__(self, scalar):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
65 assert is_real(scalar)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
66 return type(self)(self.x // scalar, self.y // scalar, self.z // scalar)
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
67 def __matmul__(self, transformation_matrix):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
68 return transform(self, transformation_matrix)
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
69 def __eq__(self, other):
24
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
70 return self.is_close(other, threshold = 1e-10)
13
12d4ddc4bfd8 Got the skew test working
Santeri Piippo
parents: 12
diff changeset
71 def __ne__(self, other):
12d4ddc4bfd8 Got the skew test working
Santeri Piippo
parents: 12
diff changeset
72 return not self.__eq__(other)
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
73 def __lt__(self, other):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
74 return self.coordinates < other.coordinates
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
75 def __hash__(self):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
76 return hash(self.coordinates)
24
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
77 def is_close(self, other, *, threshold):
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
78 return all(
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
79 abs(a - b) < threshold
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
80 for a, b in zip(self.coordinates, other.coordinates)
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
81 )
5
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
82
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
83 class VertexOp:
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
84 def __init__(self, callable):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
85 self.callable = callable
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
86 def __rmul__(self, coordinate):
e340e35d6e4c Added vertex operators
Santeri Piippo
parents: 3
diff changeset
87 return self.callable(coordinate)
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
88
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
89 class LineSegment:
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
90 def __init__(self, v1, v2):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
91 self.v1, self.v2 = v1, v2
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
92 def __repr__(self):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
93 return str.format('LineSegment({!r}, {!r})', self.v1, self.v2)
3
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
94 @property
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
95 def length(self):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
96 return self.v1.distance_to(self.v2)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
97 @property
3
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
98 def vertices(self):
1dc58f44d556 Can now write dat files, added direct color handling
Santeri Piippo
parents: 1
diff changeset
99 return self.v1, self.v2
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
100 def __len__(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
101 return 2
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
102 def __getitem__(self, index):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
103 return self.vertices[index]
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
104
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
105 class IndexRing:
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
106 def __init__(self, container):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
107 self.container = container
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
108 def __getitem__(self, index):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
109 return self.container[index % len(self.container)]
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
110
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
111 class Vector(Vertex):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
112 def __init__(self, x, y, z):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
113 super().__init__(x, y, z)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
114 def __repr__(self):
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
115 return str.format('Vector({!r}, {!r}, {!r})', self.x, self.y, self.z)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
116 def length(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
117 from math import sqrt
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
118 return sqrt(self.x ** 2 + self.y ** 2 + self.z ** 2)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
119 def normalized(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
120 length = self.length()
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
121 if length > 0:
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
122 return Vector(self.x / length, self.y / length, self.z / length)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
123 else:
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
124 return Vector(0, 0, 0)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
125
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
126 def dot_product(v1, v2):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
127 ''' Returns the dot product v1 · v2. '''
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
128 return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
129
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
130 def cross_product(v1, v2):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
131 ''' Returns the cross product v1 × v2. '''
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
132 return Vector(
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
133 x = v1.y * v2.z - v1.z * v2.y,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
134 y = v1.z * v2.x - v1.x * v2.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
135 z = v1.x * v2.y - v1.y * v2.x,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
136 )
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
137
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
138 def unit_normal(a, b, c):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
139 x = Matrix3x3([
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
140 1, a.y, a.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
141 1, b.y, b.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
142 1, c.y, c.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
143 ]).determinant()
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
144 y = Matrix3x3([
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
145 a.x, 1, a.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
146 b.x, 1, b.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
147 c.x, 1, c.z,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
148 ]).determinant()
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
149 z = Matrix3x3([
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
150 a.x, a.y, 1,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
151 b.x, b.y, 1,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
152 c.x, c.y, 1,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
153 ]).determinant()
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
154 return Vector(x, y, z).normalized()
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
155
13
12d4ddc4bfd8 Got the skew test working
Santeri Piippo
parents: 12
diff changeset
156 class NoIntersection(Exception):
12d4ddc4bfd8 Got the skew test working
Santeri Piippo
parents: 12
diff changeset
157 pass
12d4ddc4bfd8 Got the skew test working
Santeri Piippo
parents: 12
diff changeset
158
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
159 def pairs(iterable, *, count = 2):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
160 '''
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
161 Iterates the given iterable and returns tuples containing `count`
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
162 sequential values in the iterable.
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
163
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
164 Formally, for a vector A with indices 0…n and pair count k, this
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
165 function yields:
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
166 (A₀, A₁, …, Aₖ),
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
167 (A₁, A₂, …, Aₖ₊₁),
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
168 …,
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
169 (Aₙ₋₂, Aₙ₋₁, …, Aₖ₋₂),
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
170 (Aₙ₋₁, A₀, …, Aₖ₋₁).
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
171 '''
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
172 iterable_count = len(iterable)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
173 for index in range(iterable_count):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
174 yield tuple(
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
175 iterable[(index + offset) % iterable_count]
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
176 for offset in range(count)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
177 )
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
178
1
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
179 class Polygon:
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
180 def __init__(self, vertices):
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
181 self.vertices = vertices
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
182 def __repr__(self):
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
183 return str.format('Polygon({!r})', self.vertices)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
184 def area(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
185 total = Vector(0, 0, 0)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
186 for v1, v2 in pairs(self.vertices):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
187 total += cross_product(v1, v2)
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
188 return dot_product(total, unit_normal(self.vertices[0], self.vertices[1], self.vertices[2]))
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
189 def centroid(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
190 ...
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
191 raise NotImplementedError
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
192 def __getitem__(self, index):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
193 return self.vertices[index % len(self.vertices)]
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
194 def __len__(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
195 return len(self.vertices)
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
196 @property
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
197 def perimeter_lines(self):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
198 for v1, v2 in pairs(self.vertices):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
199 yield LineSegment(v1, v2)
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
200 @property
12
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
201 def angles(self):
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
202 from math import acos
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
203 for v1, v2, v3 in pairs(self.vertices, count = 3):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
204 vec1 = (position_vector(v3) - position_vector(v2)).normalized()
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
205 vec2 = (position_vector(v1) - position_vector(v2)).normalized()
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
206 cosine = dot_product(vec1, vec2) / vec1.length() / vec2.length()
12
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
207 yield acos(cosine)
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
208 @property
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
209 def smallest_angle(self):
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
210 return min(
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
211 angle_magnitude_key(angle)
eb74680a5e43 commit work done on test suites...
Santeri Piippo
parents: 9
diff changeset
212 for angle in self.angles)
7
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
213 @property
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
214 def hairline_ratio(self):
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
215 lengths = [line.length for line in self.perimeter_lines]
0ab0d61ccee8 Smallest angles
Santeri Piippo
parents: 6
diff changeset
216 return max(lengths) / min(lengths)
1
5411a25cfca7 Parsing function complete
Santeri Piippo
parents: 0
diff changeset
217
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
218 def is_real(number):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
219 return isinstance(number, int) or isinstance(number, float)
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
220
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
221 def matrix_indices():
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
222 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
223 Yields index pairs for matrix iteration
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
224 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
225 from itertools import product
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
226 yield from product(range(3), range(3))
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
227
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
228 class Matrix3x3:
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
229 '''
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
230 A 3×3 matrix forming the top-left portion of a full 4×4 transformation
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
231 matrix.
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
232 '''
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
233 class Row:
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
234 def __init__(self, matrix_ref, i1, i2, i3):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
235 self.matrix_ref = matrix_ref
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
236 self.matrix_indices = i1, i2, i3
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
237 def __getitem__(self, row_index):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
238 return self.matrix_ref[self.matrix_indices[row_index]]
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
239 def __setitem__(self, row_index, value):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
240 self.matrix_ref[self.matrix_indices[row_index]] = value
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
241 def __init__(self, values = None):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
242 if values is not None:
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
243 assert(all(is_real(x) for x in values))
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
244 assert len(values) == 9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
245 self.values = values
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
246 else:
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
247 self.values = [1, 0, 0, 0, 1, 0, 0, 0, 1]
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
248 def __repr__(self):
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
249 if self != Matrix3x3():
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
250 return str.format('Matrix3x3({!r})', self.values)
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
251 else:
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
252 return 'Matrix3x3()'
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
253 def __getitem__(self, index):
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
254 if isinstance(index, tuple):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
255 assert all(k in [0, 1, 2] for k in index)
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
256 return self.values[index[0] * 3 + index[1]]
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
257 else:
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
258 return Matrix3x3.Row(self, index * 3, index * 3 + 1, index * 3 + 2)
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
259 def determinant(self):
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
260 return sum([
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
261 +(self[0, 0] * self[1, 1] * self[2, 2]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
262 +(self[0, 1] * self[1, 2] * self[2, 0]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
263 +(self[0, 2] * self[1, 0] * self[2, 1]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
264 -(self[0, 2] * self[1, 1] * self[2, 0]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
265 -(self[0, 1] * self[1, 0] * self[2, 2]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
266 -(self[0, 0] * self[1, 2] * self[2, 1]),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
267 ])
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
268 def scaling_vector(self):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
269 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
270 Extracts scaling factors from this transformation matrix.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
271 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
272 from math import sqrt
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
273 return Vector(
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
274 x = sqrt(self[0, 0] ** 2 + self[1, 0] ** 2 + self[2, 0] ** 2),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
275 y = sqrt(self[0, 1] ** 2 + self[1, 1] ** 2 + self[2, 1] ** 2),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
276 z = sqrt(self[0, 2] ** 2 + self[1, 2] ** 2 + self[2, 2] ** 2),
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
277 )
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
278 def rotation_component(self):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
279 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
280 Extracts rotation from this matrix.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
281 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
282 return self.split()[0]
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
283 def split(self):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
284 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
285 Extracts the rotation matrix and scaling vector.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
286 '''
24
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
287 vec = self.scaling_vector()
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
288 return Matrix3x3([
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
289 self[i, j] / vec.coordinates[j]
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
290 for i, j in matrix_indices()
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
291 ]), vec
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
292 def contains_scaling(self):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
293 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
294 Returns whether this matrix contains scaling factors.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
295 '''
24
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
296 vec = self.scaling_vector()
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
297 return abs((vec.x * vec.y * vec.z) - 1) >= 1e-10
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
298 def contains_rotation(self):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
299 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
300 Returns whether this matrix contains rotation factors.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
301 '''
24
f8080ffceaa9 added test for forbidden primitive scaling
Santeri Piippo
parents: 22
diff changeset
302 return self.rotation_component() != Matrix3x3()
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
303 def __eq__(self, other):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
304 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
305 Returns whether two matrices are equivalent.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
306 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
307 return all(
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
308 abs(self[(i, j)] - other[(i, j)]) < 1e-10
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
309 for i, j in matrix_indices()
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
310 )
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
311 def __matmul__(self, other):
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
312 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
313 Computes the matrix multiplication self × other.
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
314 '''
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
315 return Matrix3x3([
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
316 sum(self[i, k] * other[k, j] for k in range(3))
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
317 for i, j in matrix_indices()
6
6da1e81c5652 Added code to compute areas of triangles and quadrilaterals
Santeri Piippo
parents: 5
diff changeset
318 ])
14
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
319 def __add__(self, other):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
320 return Matrix3x3([
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
321 a + b
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
322 for a, b in zip(self.values, other.values)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
323 ])
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
324 def __mul__(self, scalar):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
325 return Matrix3x3([
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
326 x * scalar
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
327 for x in self.values
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
328 ])
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
329
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
330 def complete_matrix(matrix, anchor):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
331 '''
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
332 Combines a 3×3 matrix and an anchor vertex into a full 4×4
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
333 transformation matrix.
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
334 '''
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
335 return [
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
336 matrix[0, 0], matrix[0, 1], matrix[0, 2], anchor.x,
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
337 matrix[1, 0], matrix[1, 1], matrix[1, 2], anchor.y,
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
338 matrix[2, 0], matrix[2, 1], matrix[2, 2], anchor.z,
0
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
339 0, 0, 0, 1,
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
340 ]
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
341
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
342 def transform(vertex, transformation_matrix):
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
343 '''
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
344 Transforms a vertex by a 4×4 transformation matrix.
55b4c97d44c5 Initial commit with half-done parsing function
Santeri Piippo
parents:
diff changeset
345 '''
9
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
346 return Vertex(
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
347 x = transformation_matrix[0] * vertex.x \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
348 + transformation_matrix[1] * vertex.y \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
349 + transformation_matrix[2] * vertex.z \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
350 + transformation_matrix[3],
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
351 y = transformation_matrix[4] * vertex.x \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
352 + transformation_matrix[5] * vertex.y \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
353 + transformation_matrix[6] * vertex.z \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
354 + transformation_matrix[7],
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
355 z = transformation_matrix[8] * vertex.x \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
356 + transformation_matrix[9] * vertex.y \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
357 + transformation_matrix[10] * vertex.z \
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
358 + transformation_matrix[11],
fea8e9ae6f29 Added matrix code, moved library paths to ldcheck.cfg.
Santeri Piippo
parents: 7
diff changeset
359 )
14
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
360
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
361 def transform_to_xy(polygon):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
362 '''
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
363 Transforms the provided polygon into the XY plane. The polygon is
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
364 assumed to be planar.
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
365
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
366 Implementation is based on this StackOverflow answer:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
367 https://math.stackexchange.com/a/476311
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
368 '''
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
369 v1, v2, v3 = polygon.vertices[:3]
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
370 a, b = v3 - v2, v1 - v2
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
371 normal = cross_product(a, b).normalized()
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
372 v_matrix = Matrix3x3([
15
45b3aeb25003 Condensed transform_to_xy
Santeri Piippo
parents: 14
diff changeset
373 0, 0, -normal.x,
45b3aeb25003 Condensed transform_to_xy
Santeri Piippo
parents: 14
diff changeset
374 0, 0, -normal.y,
45b3aeb25003 Condensed transform_to_xy
Santeri Piippo
parents: 14
diff changeset
375 normal.x, normal.y, 0,
14
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
376 ])
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
377 try:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
378 rotation_matrix = Matrix3x3()
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
379 rotation_matrix += v_matrix
15
45b3aeb25003 Condensed transform_to_xy
Santeri Piippo
parents: 14
diff changeset
380 rotation_matrix += (v_matrix @ v_matrix) * (1 / (1 + normal.z))
14
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
381 except ZeroDivisionError:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
382 rotation_matrix = Matrix3x3()
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
383 full_matrix = complete_matrix(rotation_matrix, Vertex(0, 0, 0))
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
384 return Polygon([
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
385 transform(vertex = vertex, transformation_matrix = full_matrix)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
386 for vertex in polygon.vertices
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
387 ])
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
388
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
389 def vector_angle(vec_1, vec_2, normalized = False):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
390 from math import acos, pi as π
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
391 cosine = dot_product(vec_1, vec_2)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
392 try:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
393 cosine /= vec_1.length() * vec_2.length()
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
394 except ZeroDivisionError:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
395 return 0
31
02e7e1d73ebb Fix math domain errors in vector_angle
Santeri Piippo
parents: 30
diff changeset
396 # Fix the cosine, it can go outside bounds due to rounding errors,
02e7e1d73ebb Fix math domain errors in vector_angle
Santeri Piippo
parents: 30
diff changeset
397 # e.g. 1.0000000000000002, which then causes a math domain error.
02e7e1d73ebb Fix math domain errors in vector_angle
Santeri Piippo
parents: 30
diff changeset
398 cosine = min(max(-1, cosine), 1)
14
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
399 angle = acos(cosine)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
400 if normalized and angle > π / 2:
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
401 angle = π - angle
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
402 return angle
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
403
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
404 def split_quadrilateral(polygon):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
405 assert(len(polygon.vertices) == 4)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
406 vertices = IndexRing(polygon.vertices)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
407 for i in (0, 1):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
408 a, b = vertices[0 + i], vertices[1 + i]
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
409 c, d = vertices[2 + i], vertices[3 + i]
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
410 yield Polygon([a, b, c]), Polygon([b, c, d])
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
411
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
412 def triangle_plane_normal(polygon):
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
413 assert(len(polygon.vertices) == 3)
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
414 a, b, c = polygon.vertices[:3]
d383f319f35b transform_to_xy implemented and concave test online
Santeri Piippo
parents: 13
diff changeset
415 return cross_product(b - a, b - c)
28
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
416
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
417 def line_intersection_xy(line_1, line_2):
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
418 '''
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
419 Computes 2D line intersection. Can return a point outside the given
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
420 segments. Z is ignored.
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
421 '''
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
422 a, b = line_1.vertices
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
423 c, d = line_2.vertices
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
424 denominator = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
425 x = (c.x - d.x) * (a.x * b.y - a.y * b.x)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
426 x -= (a.x - b.x) * (c.x * d.y - c.y * d.x)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
427 y = (c.y - d.y) * (a.x * b.y - a.y * b.x)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
428 y -= (a.y - b.y) * (c.x * d.y - c.y * d.x)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
429 try:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
430 x /= denominator
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
431 y /= denominator
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
432 except ZeroDivisionError:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
433 return None
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
434 else:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
435 return Vertex(x, y, 0)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
436
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
437 def line_segment_intersection_xy(line_1, line_2):
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
438 '''
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
439 Computes 2D line intersection. Only returns a result if it falls
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
440 inside the line segments. Z is ignored.
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
441 '''
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
442 from math import inf
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
443 intersection = line_intersection_xy(line_1, line_2)
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
444 if intersection:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
445 a, b = line_1.vertices
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
446 c, d = line_2.vertices
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
447 try:
30
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
448 t1 = (intersection.x - a.x) / (b.x - a.x)
28
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
449 except ZeroDivisionError:
30
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
450 t1 = inf
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
451 try:
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
452 t2 = (intersection.x - c.x) / (d.x - c.x)
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
453 except ZeroDivisionError:
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
454 t2 = inf
28
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
455 try:
30
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
456 u1 = (intersection.y - a.y) / (b.y - a.y)
28
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
457 except ZeroDivisionError:
30
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
458 u1 = inf
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
459 try:
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
460 u2 = (intersection.y - c.y) / (d.y - c.y)
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
461 except ZeroDivisionError:
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
462 u2 = inf
0d9ca37901ed added test for collinearity, fixed bowtie test
Santeri Piippo
parents: 28
diff changeset
463 if (0 < t1 < 1 and 0 < t2 < 1) or (0 < u1 < 1 and 0 < u2 < 1):
28
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
464 return intersection
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
465 else:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
466 return None
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
467 else:
5933250813a3 Added bowtie check
Santeri Piippo
parents: 24
diff changeset
468 return None

mercurial