1 # SPDX-License-Identifier: GPL-2.0-or-later
5 """Geometry classes and operations.
6 Also, vector file representation (Art).
9 __author__
= "howard.trickey@gmail.com"
13 # distances less than about DISTTOL will be considered
20 """Container of points without duplication, each mapped to an int.
22 Points are either have dimension at least 2, maybe more.
25 In order to efficiently find duplicates, we quantize the points
26 to triples of ints and map from quantized triples to vertex
30 pos: list of tuple of float - coordinates indexed by
32 invmap: dict of (int, int, int) to int - quantized coordinates
36 def __init__(self
, initlist
=[]):
44 """Quantize the float tuple into an int tuple.
49 tuple of int - scaled by INVDISTTOL and rounded p
52 return tuple([int(round(v
* INVDISTTOL
)) for v
in p
])
54 def AddPoint(self
, p
, allowdups
= False):
55 """Add point p to the Points set and return vertex number.
57 If there is an existing point which quantizes the same,,
58 don't add a new one but instead return existing index.
59 Except if allowdups is True, don't do that deduping.
62 p: tuple of float - coordinates (2-tuple or 3-tuple)
64 int - the vertex number of added (or existing) point
67 qp
= Points
.Quantize(p
)
68 if qp
in self
.invmap
and not allowdups
:
69 return self
.invmap
[qp
]
71 self
.invmap
[qp
] = len(self
.pos
)
73 return len(self
.pos
) - 1
75 def AddPoints(self
, points
, allowdups
= False):
76 """Add another set of points to this set.
78 We need to return a mapping from indices
79 in the argument points space into indices
83 points: Points - to union into this set
85 list of int: maps added indices to new ones
88 vmap
= [0] * len(points
.pos
)
89 for i
in range(len(points
.pos
)):
90 vmap
[i
] = self
.AddPoint(points
.pos
[i
], allowdups
)
93 def AddZCoord(self
, z
):
94 """Change this in place to have a z coordinate, with value z.
96 Assumes the coordinates are currently 2d.
99 z: the value of the z coordinate to add
101 self now has a z-coordinate added
104 assert(len(self
.pos
) == 0 or len(self
.pos
[0]) == 2)
106 for i
, (x
, y
) in enumerate(self
.pos
):
109 newinvmap
[self
.Quantize(newp
)] = i
110 self
.invmap
= newinvmap
112 def AddToZCoord(self
, i
, delta
):
113 """Change the z-coordinate of point with index i to add delta.
115 Assumes the coordinates are currently 3d.
118 i: int - index of a point
119 delta: float - value to add to z-coord
122 (x
, y
, z
) = self
.pos
[i
]
123 self
.pos
[i
] = (x
, y
, z
+ delta
)
126 class PolyArea(object):
127 """Contains a Polygonal Area (polygon with possible holes).
129 A polygon is a list of vertex ids, each an index given by
130 a Points object. The list represents a CCW-oriented
131 outer boundary (implicitly closed).
132 If there are holes, they are lists of CW-oriented vertices
133 that should be contained in the outer boundary.
134 (So the left face of both the poly and the holes is
139 poly: list of vertex ids
140 holes: list of lists of vertex ids (each a hole in poly)
141 data: any - application data (can hold color, e.g.)
144 def __init__(self
, points
=None, poly
=None, holes
=None, data
=None):
145 self
.points
= points
if points
else Points()
146 self
.poly
= poly
if poly
else []
147 self
.holes
= holes
if holes
else []
150 def AddHole(self
, holepa
):
151 """Add a PolyArea's poly as a hole of self.
153 Need to reverse the contour and
154 adjust the the point indexes and self.points.
160 vmap
= self
.points
.AddPoints(holepa
.points
)
161 holepoly
= [vmap
[i
] for i
in holepa
.poly
]
163 self
.holes
.append(holepoly
)
165 def ContainsPoly(self
, poly
, points
):
166 """Tests if poly is contained within self.poly.
169 poly: list of int - indices into points
170 points: Points - maps to coords
172 bool - True if poly is fully contained within self.poly
176 if PointInside(points
.pos
[v
], self
.poly
, self
.points
) == -1:
181 """Returns the normal of the polyarea's main poly."""
183 pos
= self
.points
.pos
185 if len(pos
) == 0 or len(pos
[0]) == 2 or len(poly
) == 0:
186 print("whoops, not enough info to calculate normal")
187 return (0.0, 0.0, 1.0)
188 return Newell(poly
, self
.points
)
191 class PolyAreas(object):
192 """Contains a list of PolyAreas and a shared Points.
195 polyareas: list of PolyArea
201 self
.points
= Points()
203 def scale_and_center(self
, scaled_side_target
):
204 """Adjust the coordinates of the polyareas so that
205 it is centered at the origin and has its longest
206 dimension scaled to be scaled_side_target."""
208 if len(self
.points
.pos
) == 0:
210 (minv
, maxv
) = self
.bounds()
211 maxside
= max([maxv
[i
] - minv
[i
] for i
in range(2)])
213 scale
= scaled_side_target
/ maxside
216 translate
= [-0.5 * (maxv
[i
] + minv
[i
]) for i
in range(2)]
217 dim
= len(self
.points
.pos
[0])
219 translate
.append([0.0])
220 for v
in range(len(self
.points
.pos
)):
221 self
.points
.pos
[v
] = tuple([scale
* (self
.points
.pos
[v
][i
] + \
222 translate
[i
]) for i
in range(dim
)])
225 """Find bounding box of polyareas in xy.
228 ([minx,miny],[maxx,maxy]) - all floats
233 maxv
= [-huge
, -huge
]
234 for pa
in self
.polyareas
:
235 for face
in [pa
.poly
] + pa
.holes
:
237 vcoords
= self
.points
.pos
[v
]
239 if vcoords
[i
] < minv
[i
]:
241 if vcoords
[i
] > maxv
[i
]:
251 """Contains a generic 3d model.
253 A generic 3d model has vertices with 3d coordinates.
254 Each vertex gets a 'vertex id', which is an index that
255 can be used to refer to the vertex and can be used
256 to retrieve the 3d coordinates of the point.
258 The actual visible part of the geometry are the faces,
259 which are n-gons (n>2), specified by a vector of the
261 Faces may also have data associated with them,
262 and the data will be copied into newly created faces
263 from the most likely neighbor faces..
266 points: geom.Points - the 3d vertices
267 faces: list of list of indices (each a CCW traversal of a face)
268 face_data: list of any - if present, is parallel to
269 faces list and holds arbitrary data
273 self
.points
= Points()
279 """Contains a vector art diagram.
282 paths: list of Path objects
290 """A color or pattern to fill or stroke with.
292 For now, just do colors, but could later do
293 patterns or images too.
296 color: (r,g,b) triple of floats, 0.0=no color, 1.0=max color
299 def __init__(self
, r
=0.0, g
=0.0, b
=0.0):
300 self
.color
= (r
, g
, b
)
303 def CMYK(c
, m
, y
, k
):
304 """Return Paint specified in CMYK model.
306 Uses formula from 6.2.4 of PDF Reference.
309 c, m, y, k: float - in range [0, 1]
311 Paint - with components in rgb form now
314 return Paint(1.0 - min(1.0, c
+ k
),
315 1.0 - min(1.0, m
+ k
), 1.0 - min(1.0, y
+ k
))
317 black_paint
= Paint()
318 white_paint
= Paint(1.0, 1.0, 1.0)
321 'aqua': Paint(0.0, 1.0, 1.0),
322 'black': Paint(0.0, 0.0, 0.0),
323 'blue': Paint(0.0, 0.0, 1.0),
324 'fuchsia': Paint(1.0, 0.0, 1.0),
325 'gray': Paint(0.5, 0.5, 0.5),
326 'green': Paint(0.0, 0.5, 0.0),
327 'lime': Paint(0.0, 1.0, 0.0),
328 'maroon': Paint(0.5, 0.0, 0.0),
329 'navy': Paint(0.0, 0.0, 0.5),
330 'olive': Paint(0.5, 0.5, 0.0),
331 'purple': Paint(0.5, 0.0, 0.5),
332 'red': Paint(1.0, 0.0, 0.0),
333 'silver': Paint(0.75, 0.75, 0.75),
334 'teal': Paint(0.0, 0.5, 0.5),
335 'white': Paint(1.0, 1.0, 1.0),
336 'yellow': Paint(1.0, 1.0, 0.0)
341 """Represents a path in the PDF sense, with painting instructions.
344 subpaths: list of Subpath objects
345 filled: True if path is to be filled
346 fillevenodd: True if use even-odd rule to fill (else non-zero winding)
347 stroked: True if path is to be stroked
348 fillpaint: Paint to fill with
349 strokepaint: Paint to stroke with
355 self
.fillevenodd
= False
357 self
.fillpaint
= black_paint
358 self
.strokepaint
= black_paint
360 def AddSubpath(self
, subpath
):
361 """"Add a subpath."""
363 self
.subpaths
.append(subpath
)
366 """Returns True if this Path as no subpaths."""
368 return not self
.subpaths
371 class Subpath(object):
372 """Represents a subpath in PDF sense, either open or closed.
374 We'll represent lines, bezier pieces, circular arc pieces
375 as tuples with letters giving segment type in first position
376 and coordinates (2-tuples of floats) in the other positions.
379 ('L', a, b) - line from a to b
380 ('B', a, b, c, d) - cubic bezier from a to b, with control points c,d
381 ('Q', a, b, c) - quadratic bezier from a to b, with 1 control point c
382 ('A', a, b, rad, xrot, large-arc, ccw) - elliptical arc from a to b,
383 with rad=(rx, ry) as radii, xrot is x-axis rotation in degrees,
384 large-arc is True if arc should be >= 180 degrees,
385 ccw is True if start->end follows counter-clockwise direction
386 (see SVG spec); note that after rad,
387 the rest are floats or bools, not coordinate pairs
388 Note that s[1] and s[2] are the start and end points for any segment s.
391 segments: list of segment tuples (see above)
392 closed: True if closed
400 """Returns True if this subpath as no segments."""
402 return not self
.segments
404 def AddSegment(self
, seg
):
407 self
.segments
.append(seg
)
411 """Return start point for segment.
416 (float, float): the coordinates of the segment's start point
423 """Return end point for segment.
428 (float, float): the coordinates of the segment's end point
434 class TransformMatrix(object):
435 """Transformation matrix for 2d coordinates.
437 The transform matrix is:
441 and coordinate transformation is defined by:
442 [x' y' 1] = [x y 1] x TransformMatrix
445 a, b, c, d, e, f: floats
448 def __init__(self
, a
=1.0, b
=0.0, c
=0.0, d
=1.0, e
=0.0, f
=0.0):
457 return str([self
.a
, self
.b
, self
.c
, self
.d
, self
.e
, self
.f
])
460 """Return a copy of this matrix."""
462 return TransformMatrix(self
.a
, self
.b
, self
.c
, self
.d
, self
.e
, self
.f
)
464 def ComposeTransform(self
, a
, b
, c
, d
, e
, f
):
465 """Apply the transform given the the arguments on top of this one.
467 This is accomplished by returning t x sel
468 where t is the transform matrix that would be formed from the args.
471 a, b, c, d, e, f: float - defines a composing TransformMatrix
474 newa
= a
* self
.a
+ b
* self
.c
475 newb
= a
* self
.b
+ b
* self
.d
476 newc
= c
* self
.a
+ d
* self
.c
477 newd
= c
* self
.b
+ d
* self
.d
478 newe
= e
* self
.a
+ f
* self
.c
+ self
.e
479 newf
= e
* self
.b
+ f
* self
.d
+ self
.f
488 """Return the result of applying this transform to pt = (x,y).
491 (x, y) : (float, float)
493 (x', y'): 2-tuple of floats, the result of [x y 1] x self
497 return (self
.a
* x
+ self
.c
* y
+ self
.e
, \
498 self
.b
* x
+ self
.d
* y
+ self
.f
)
501 def ApproxEqualPoints(p
, q
):
502 """Return True if p and q are approximately the same points.
508 bool - True if the 1-norm <= DISTTOL
511 for i
in range(len(p
)):
512 if abs(p
[i
] - q
[i
]) > DISTTOL
:
517 def PointInside(v
, a
, points
):
518 """Return 1, 0, or -1 as v is inside, on, or outside polygon.
520 Cf. Eric Haines ptinpoly in Graphics Gems IV.
523 v : (float, float) or (float, float, float) - coordinates of a point
524 a : list of vertex indices defining polygon (assumed CCW)
525 points: Points - to get coordinates for polygon
527 1, 0, -1: as v is inside, on, or outside polygon a
530 (xv
, yv
) = (v
[0], v
[1])
531 vlast
= points
.pos
[a
[-1]]
532 (x0
, y0
) = (vlast
[0], vlast
[1])
533 if x0
== xv
and y0
== yv
:
538 for i
in range(0, n
):
539 vi
= points
.pos
[a
[i
]]
540 (x1
, y1
) = (vi
[0], vi
[1])
541 if x1
== xv
and y1
== yv
:
551 z
= x1
- (y1
- yv
) * (x0
- x1
) / (y0
- y1
)
563 def SignedArea(polygon
, points
):
564 """Return the area of the polgon, positive if CCW, negative if CW.
567 polygon: list of vertex indices
570 float - area of polygon, positive if it was CCW, else negative
575 for i
in range(0, n
):
576 u
= points
.pos
[polygon
[i
]]
577 v
= points
.pos
[polygon
[(i
+ 1) % n
]]
578 a
+= u
[0] * v
[1] - u
[1] * v
[0]
583 """Return vector a-b.
589 n-tuple of floats - pairwise addition a+b
594 return tuple([a
[i
] + b
[i
] for i
in range(n
)])
598 """Return vector a-b.
604 n-tuple of floats - pairwise subtraction a-b
609 return tuple([a
[i
] - b
[i
] for i
in range(n
)])
613 """Return the dot product of two vectors.
619 n-tuple of floats - dot product of a and b
631 """Return the Euclidean length of the argument vector.
636 float: the 2-norm of a
645 def Newell(poly
, points
):
646 """Use Newell method to find polygon normal.
648 Assume poly has length at least 3 and points are 3d.
651 poly: list of int - indices into points.pos
652 points: Points - assumed 3d
654 (float, float, float) - the average normal
662 for i
, ai
in enumerate(poly
):
663 bi
= poly
[(i
+ 1) % n
]
666 sumx
+= (a
[1] - b
[1]) * (a
[2] + b
[2])
667 sumy
+= (a
[2] - b
[2]) * (a
[0] + b
[0])
668 sumz
+= (a
[0] - b
[0]) * (a
[1] + b
[1])
669 return Norm3(sumx
, sumy
, sumz
)
673 """Return vector (x,y,z) normalized by dividing by squared length.
674 Return (0.0, 0.0, 1.0) if the result is undefined."""
675 sqrlen
= x
* x
+ y
* y
+ z
* z
677 return (0.0, 0.0, 1.0)
680 d
= math
.sqrt(sqrlen
)
681 return (x
/ d
, y
/ d
, z
/ d
)
683 return (0.0, 0.0, 1.0)
686 # We're using right-hand coord system, where
687 # forefinger=x, middle=y, thumb=z on right hand.
688 # Then, e.g., (1,0,0) x (0,1,0) = (0,0,1)
690 """Return the cross product of two vectors, a x b."""
694 return (ay
* bz
- az
* by
, az
* bx
- ax
* bz
, ax
* by
- ay
* bx
)
698 """Return matrix multiplication of p times m
699 where m is a 4x3 matrix and p is a 3d point, extended with 1."""
702 return (x
* m
[0] + y
* m
[3] + z
* m
[6] + m
[9],
703 x
* m
[1] + y
* m
[4] + z
* m
[7] + m
[10],
704 x
* m
[2] + y
* m
[5] + z
* m
[8] + m
[11])