geometry.py

Tue, 25 Aug 2020 23:24:34 +0300

author
Teemu Piippo <teemu@hecknology.net>
date
Tue, 25 Aug 2020 23:24:34 +0300
changeset 107
909bec645516
parent 103
662de6b8cfc2
permissions
-rw-r--r--

added a reference for colors

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

mercurial