mesh_inset/offset.py

   1 # SPDX-License-Identifier: GPL-2.0-or-later
   2
   3 """Creating offset polygons inside faces."""
   4
   5 __author__ = "howard.trickey@gmail.com"
   6
   7 import math
   8 from . import triquad
   9 from . import geom
  10 from .triquad import Sub2, Add2, Angle, Ccw, Normalized2, Perp2, Length2, \
  11                     LinInterp2, TOL
  12 from .geom import Points
  13
  14 AREATOL = 1e-4
  15
  16
  17 class Spoke(object):
  18     """A Spoke is a line growing from an outer vertex to an inner one.
  19
  20     A Spoke is contained in an Offset (see below).
  21
  22     Attributes:
  23       origin: int - index of origin point in a Points
  24       dest: int - index of dest point
  25       is_reflex: bool - True if spoke grows from a reflex angle
  26       dir: (float, float, float) - direction vector (normalized)
  27       speed: float - at time t, other end of spoke is
  28           origin + t*dir.  Speed is such that the wavefront
  29           from the face edges moves at speed 1.
  30       face: int - index of face containing this Spoke, in Offset
  31       index: int - index of this Spoke in its face
  32       destindex: int - index of Spoke dest in its face
  33     """
  34
  35     def __init__(self, v, prev, next, face, index, points):
  36         """Set attribute of spoke from points making up initial angle.
  37
  38         The spoke grows from an angle inside a face along the bisector
  39         of that angle.  Its speed is 1/sin(.5a), where a is the angle
  40         formed by (prev, v, next).  That speed means that the perpendicular
  41         from the end of the spoke to either of the prev->v or v->prev
  42         edges will grow at speed 1.
  43
  44         Args:
  45           v: int - index of point spoke grows from
  46           prev: int - index of point before v on boundary (in CCW order)
  47           next: int - index of point after v on boundary (in CCW order)
  48           face: int - index of face containing this spoke, in containing offset
  49           index: int - index of this spoke in its face
  50           points: geom.Points - maps vertex indices to 3d coords
  51         """
  52
  53         self.origin = v
  54         self.dest = v
  55         self.face = face
  56         self.index = index
  57         self.destindex = -1
  58         vmap = points.pos
  59         vp = vmap[v]
  60         prevp = vmap[prev]
  61         nextp = vmap[next]
  62         uin = Normalized2(Sub2(vp, prevp))
  63         uout = Normalized2(Sub2(nextp, vp))
  64         uavg = Normalized2((0.5 * (uin[0] + uout[0]), \
  65             0.5 * (uin[1] + uout[1])))
  66         if abs(Length2(uavg)) < TOL:
  67             # in and out vectors are reverse of each other
  68             self.dir = (uout[0], uout[1], 0.0)
  69             self.is_reflex = False
  70             self.speed = 1e7
  71         else:
  72             # bisector direction is 90 degree CCW rotation of
  73             # average incoming/outgoing
  74             self.dir = (-uavg[1], uavg[0], 0.0)
  75             self.is_reflex = Ccw(next, v, prev, points)
  76             ang = Angle(prev, v, next, points)  # in range [0, 180)
  77             sin_half_ang = math.sin(math.pi * ang / 360.0)
  78             if abs(sin_half_ang) < TOL:
  79                 self.speed = 1e7
  80             else:
  81                 self.speed = 1.0 / sin_half_ang
  82
  83     def __repr__(self):
  84         """Printing representation of a Spoke."""
  85
  86         return "@%d+%gt%s <%d,%d>" % (self.origin, \
  87                 self.speed, str(self.dir), \
  88                 self.face, self.index)
  89
  90     def EndPoint(self, t, points, vspeed):
  91         """Return the coordinates of the non-origin point at time t.
  92
  93         Args:
  94           t: float - time to end of spoke
  95           points: geom.Points - coordinate map
  96           vspeed: float - speed in z direction
  97         Returns:
  98           (float, float, float) - coords of spoke's endpoint at time t
  99         """
 100
 101         p = points.pos[self.origin]
 102         d = self.dir
 103         v = self.speed
 104         return (p[0] + v * t * d[0], p[1] + v * t * d[1], p[2] + vspeed * t)
 105
 106     def VertexEvent(self, other, points):
 107         """Intersect self with other spoke, and return the OffsetEvent, if any.
 108
 109         A vertex event is with one advancing spoke intersects an adjacent
 110         adavancing spoke, forming a new vertex.
 111
 112         Args:
 113           other: Spoke - other spoke to intersect with
 114           points: Geom.points
 115         Returns:
 116           None or OffsetEvent - if there's an intersection in the growing
 117             directions of the spokes, will return the OffsetEvent for
 118             the intersection;
 119             if lines are collinear or parallel, return None
 120         """
 121
 122         vmap = points.pos
 123         a = vmap[self.origin]
 124         b = Add2(a, self.dir)
 125         c = vmap[other.origin]
 126         d = Add2(c, other.dir)
 127         # find intersection of line ab with line cd
 128         u = Sub2(b, a)
 129         v = Sub2(d, c)
 130         w = Sub2(a, c)
 131         pp = Perp2(u, v)
 132         if abs(pp) > TOL:
 133             # lines or neither parallel nor collinear
 134             si = Perp2(v, w) / pp
 135             ti = Perp2(u, w) / pp
 136             if si >= 0 and ti >= 0:
 137                 p = LinInterp2(a, b, si)
 138                 dist_ab = si * Length2(u)
 139                 dist_cd = ti * Length2(v)
 140                 time_ab = dist_ab / self.speed
 141                 time_cd = dist_cd / other.speed
 142                 time = max(time_ab, time_cd)
 143                 return OffsetEvent(True, time, p, self, other)
 144         return None
 145
 146     def EdgeEvent(self, other, offset):
 147         """Intersect self with advancing edge and return OffsetEvent, if any.
 148
 149         An edge event is when one advancing spoke intersects an advancing
 150         edge.  Advancing edges start out as face edges and move perpendicular
 151         to them, at a rate of 1.  The endpoints of the edge are the advancing
 152         spokes on either end of the edge (so the edge shrinks or grows as
 153         it advances). At some time, the edge may shrink to nothing and there
 154         will be no EdgeEvent after that time.
 155
 156         We represent an advancing edge by the first spoke (in CCW order
 157         of face) of the pair of defining spokes.
 158
 159         At time t, end of this spoke is at
 160             o + d*s*t
 161         where o=self.origin, d=self.dir, s= self.speed.
 162         The advancing edge line has this equation:
 163             oo + od*os*t + p*a
 164         where oo, od, os are o, d, s for other spoke, and p is direction
 165         vector parallel to advancing edge, and a is a real parameter.
 166         Equating x and y of intersection point:
 167
 168             o.x + d.x*s*t = oo.x + od.x*os*t + p.x*w
 169             o.y + d.y*s*t = oo.y + od.y*os*t + p.y*w
 170
 171         which can be rearranged into the form
 172
 173             a = bt + cw
 174             d = et + fw
 175
 176         and solved for t, w.
 177
 178         Args:
 179           other: Spoke - the edge out of this spoke's origin is the advancing
 180               edge to be checked for intersection
 181           offset: Offset - the containing Offset
 182         Returns:
 183           None or OffsetEvent - with data about the intersection, if any
 184         """
 185
 186         vmap = offset.polyarea.points.pos
 187         o = vmap[self.origin]
 188         oo = vmap[other.origin]
 189         otherface = offset.facespokes[other.face]
 190         othernext = otherface[(other.index + 1) % len(otherface)]
 191         oonext = vmap[othernext.origin]
 192         p = Normalized2(Sub2(oonext, oo))
 193         a = o[0] - oo[0]
 194         d = o[1] - oo[1]
 195         b = other.dir[0] * other.speed - self.dir[0] * self.speed
 196         e = other.dir[1] * other.speed - self.dir[1] * self.speed
 197         c = p[0]
 198         f = p[1]
 199         if abs(c) > TOL:
 200             dem = e - f * b / c
 201             if abs(dem) > TOL:
 202                 t = (d - f * a / c) / dem
 203                 w = (a - b * t) / c
 204             else:
 205                 return None
 206         elif abs(f) > TOL:
 207             dem = b - c * e / f
 208             if abs(dem) > TOL:
 209                 t = (a - c * d / f) / dem
 210                 w = (d - e * t) / f
 211             else:
 212                 return None
 213         else:
 214             return None
 215         if t < 0.0:
 216             # intersection is in backward direction along self spoke
 217             return None
 218         if w < 0.0:
 219             # intersection on wrong side of first end of advancing line segment
 220             return None
 221         # calculate the equivalent of w for the other end
 222         aa = o[0] - oonext[0]
 223         dd = o[1] - oonext[1]
 224         bb = othernext.dir[0] * othernext.speed - self.dir[0] * self.speed
 225         ee = othernext.dir[1] * othernext.speed - self.dir[1] * self.speed
 226         cc = -p[0]
 227         ff = -p[1]
 228         if abs(cc) > TOL:
 229             ww = (aa - bb * t) / cc
 230         elif abs(ff) > TOL:
 231             ww = (dd - ee * t) / ff
 232         else:
 233             return None
 234         if ww < 0.0:
 235             return None
 236         evertex = (o[0] + self.dir[0] * self.speed * t, \
 237                    o[1] + self.dir[1] * self.speed * t)
 238         return OffsetEvent(False, t, evertex, self, other)
 239
 240
 241 class OffsetEvent(object):
 242     """An event involving a spoke during offset computation.
 243
 244     The events kinds are:
 245       vertex event: the spoke intersects an adjacent spoke and makes a new
 246           vertex
 247       edge event: the spoke hits an advancing edge and splits it
 248
 249     Attributes:
 250       is_vertex_event: True if this is a vertex event (else it is edge event)
 251       time: float - time at which it happens (edges advance at speed 1)
 252       event_vertex: (float, float) - intersection point of event
 253       spoke: Spoke - the spoke that this event is for
 254       other: Spoke - other spoke involved in event; if vertex event, this will
 255         be an adjacent spoke that intersects; if an edge event, this is the
 256         spoke whose origin's outgoing edge grows to hit this event's spoke
 257     """
 258
 259     def __init__(self, isv, time, evertex, spoke, other):
 260         """Creates and initializes attributes of an OffsetEvent."""
 261
 262         self.is_vertex_event = isv
 263         self.time = time
 264         self.event_vertex = evertex
 265         self.spoke = spoke
 266         self.other = other
 267
 268     def __repr__(self):
 269         """Printing representation of an event."""
 270
 271         if self.is_vertex_event:
 272             c = "V"
 273         else:
 274             c = "E"
 275         return "%s t=%5f %s %s %s" % (c, self.time, str(self.event_vertex), \
 276                                       repr(self.spoke), repr(self.other))
 277
 278
 279 class Offset(object):
 280     """Represents an offset polygonal area, and used to construct one.
 281
 282     Currently, the polygonal area must lie approximately in the XY plane.
 283     As well as growing inwards in that plane, the advancing lines also
 284     move in the Z direction at the rate of vspeed.
 285
 286     Attributes:
 287       polyarea: geom.PolyArea - the area we are offsetting from.
 288           We share the polyarea.points, and add to it as points in
 289           the offset polygonal area are computed.
 290       facespokes: list of list of Spoke - each sublist is a closed face
 291           (oriented CCW); the faces may mutually interfere.
 292           These lists are spokes for polyarea.poly + polyarea.holes.
 293       endtime: float - time when this offset hits its first
 294           event (relative to beginning of this offset), or the amount
 295           that takes this offset to the end of the total Build time
 296       timesofar: float - sum of times taken by all containing Offsets
 297       vspeed: float - speed that edges move perpendicular to offset plane
 298       inneroffsets: list of Offset - the offsets that take over after this
 299           (inside it)
 300     """
 301
 302     def __init__(self, polyarea, time, vspeed):
 303         """Set up initial state of Offset from a polyarea.
 304
 305         Args:
 306           polyarea: geom.PolyArea
 307           time: float - time so far
 308         """
 309
 310         self.polyarea = polyarea
 311         self.facespokes = []
 312         self.endtime = 0.0
 313         self.timesofar = time
 314         self.vspeed = vspeed
 315         self.inneroffsets = []
 316         self.InitFaceSpokes(polyarea.poly)
 317         for f in polyarea.holes:
 318             self.InitFaceSpokes(f)
 319
 320     def __repr__(self):
 321         ans = ["Offset: endtime=%g" % self.endtime]
 322         for i, face in enumerate(self.facespokes):
 323             ans.append(("<%d>" % i) + str([str(spoke) for spoke in face]))
 324         return '\n'.join(ans)
 325
 326     def PrintNest(self, indent_level=0):
 327         indent = " " * indent_level * 4
 328         print(indent + "Offset  timesofar=", self.timesofar, "endtime=",
 329             self.endtime)
 330         print(indent + " polyarea=", self.polyarea.poly, self.polyarea.holes)
 331         for o in self.inneroffsets:
 332             o.PrintNest(indent_level + 1)
 333
 334     def InitFaceSpokes(self, face_vertices):
 335         """Initialize the offset representation of a face from vertex list.
 336
 337         If the face has no area or too small an area, don't bother making it.
 338
 339         Args:
 340           face_vertices: list of int - point indices for boundary of face
 341         Side effect:
 342           A new face (list of spokes) may be added to self.facespokes
 343         """
 344
 345         n = len(face_vertices)
 346         if n <= 2:
 347             return
 348         points = self.polyarea.points
 349         area = abs(geom.SignedArea(face_vertices, points))
 350         if area < AREATOL:
 351             return
 352         findex = len(self.facespokes)
 353         fspokes = [Spoke(v, face_vertices[(i - 1) % n], \
 354             face_vertices[(i + 1) % n], findex, i, points) \
 355             for i, v in enumerate(face_vertices)]
 356         self.facespokes.append(fspokes)
 357
 358     def NextSpokeEvents(self, spoke):
 359         """Return the OffsetEvents that will next happen for a given spoke.
 360
 361         It might happen that some events happen essentially simultaneously,
 362         and also it is convenient to separate Edge and Vertex events, so
 363         we return two lists.
 364         But, for vertex events, only look at the event with the next Spoke,
 365         as the event with the previous spoke will be accounted for when we
 366         consider that previous spoke.
 367
 368         Args:
 369           spoke: Spoke - a spoke in one of the faces of this object
 370         Returns:
 371           (float, list of OffsetEvent, list of OffsetEvent) -
 372               time of next event,
 373               next Vertex event list and next Edge event list
 374         """
 375
 376         facespokes = self.facespokes[spoke.face]
 377         n = len(facespokes)
 378         bestt = 1e100
 379         bestv = []
 380         beste = []
 381         # First find vertex event (only the one with next spoke)
 382         next_spoke = facespokes[(spoke.index + 1) % n]
 383         ev = spoke.VertexEvent(next_spoke, self.polyarea.points)
 384         if ev:
 385             bestv = [ev]
 386             bestt = ev.time
 387         # Now find edge events, if this is a reflex vertex
 388         if spoke.is_reflex:
 389             prev_spoke = facespokes[(spoke.index - 1) % n]
 390             for f in self.facespokes:
 391                 for other in f:
 392                     if other == spoke or other == prev_spoke:
 393                         continue
 394                     ev = spoke.EdgeEvent(other, self)
 395                     if ev:
 396                         if ev.time < bestt - TOL:
 397                             beste = []
 398                             bestv = []
 399                             bestt = ev.time
 400                         if abs(ev.time - bestt) < TOL:
 401                             beste.append(ev)
 402         return (bestt, bestv, beste)
 403
 404     def Build(self, target=2e100):
 405         """Build the complete Offset structure or up until target time.
 406
 407         Find the next event(s), makes the appropriate inner Offsets
 408         that are inside this one, and calls Build on those Offsets to continue
 409         the process until only a single point is left or time reaches target.
 410         """
 411
 412         bestt = 1e100
 413         bestevs = [[], []]
 414         for f in self.facespokes:
 415             for s in f:
 416                 (t, ve, ee) = self.NextSpokeEvents(s)
 417                 if t < bestt - TOL:
 418                     bestevs = [[], []]
 419                     bestt = t
 420                 if abs(t - bestt) < TOL:
 421                     bestevs[0].extend(ve)
 422                     bestevs[1].extend(ee)
 423         if bestt == 1e100:
 424             # could happen if polygon is oriented wrong
 425             # or in other special cases
 426             return
 427         if abs(bestt) < TOL:
 428             # seems to be in a loop, so quit
 429             return
 430         self.endtime = bestt
 431         (ve, ee) = bestevs
 432         newfaces = []
 433         splitjoin = None
 434         if target < self.endtime:
 435             self.endtime = target
 436             newfaces = self.MakeNewFaces(self.endtime)
 437         elif ve and not ee:
 438             # Only vertex events.
 439             # Merging of successive vertices in inset face will
 440             # take care of the vertex events
 441             newfaces = self.MakeNewFaces(self.endtime)
 442         else:
 443             # Edge events too
 444             # First make the new faces (handles all vertex events)
 445             newfaces = self.MakeNewFaces(self.endtime)
 446             # Only do one edge event (handle other simultaneous edge
 447             # events in subsequent recursive Build calls)
 448             if newfaces:
 449                 splitjoin = self.SplitJoinFaces(newfaces, ee[0])
 450         nexttarget = target - self.endtime
 451         if len(newfaces) > 0:
 452             pa = geom.PolyArea(points=self.polyarea.points)
 453             pa.data = self.polyarea.data
 454             newt = self.timesofar + self.endtime
 455             pa2 = None  # may make another
 456             if not splitjoin:
 457                 pa.poly = newfaces[0]
 458                 pa.holes = newfaces[1:]
 459             elif splitjoin[0] == 'split':
 460                 (_, findex, newface0, newface1) = splitjoin
 461                 if findex == 0:
 462                     # Outer poly of polyarea was split.
 463                     # Now there will be two polyareas.
 464                     # If there were holes, need to allocate according to
 465                     # which one contains the holes.
 466                     pa.poly = newface0
 467                     pa2 = geom.PolyArea(points=self.polyarea.points)
 468                     pa2.data = self.polyarea.data
 469                     pa2.poly = newface1
 470                     if len(newfaces) > 1:
 471                         # print("need to allocate holes")
 472                         for hf in newfaces[1:]:
 473                             if pa.ContainsPoly(hf, self.polyarea.points):
 474                                 # print("add", hf, "to", pa.poly)
 475                                 pa.holes.append(hf)
 476                             elif pa2.ContainsPoly(hf, self.polyarea.points):
 477                                 # print("add", hf, "to", pa2.poly)
 478                                 pa2.holes.append(hf)
 479                             else:
 480                                 print("whoops, hole in neither poly!")
 481                     self.inneroffsets = [Offset(pa, newt, self.vspeed), \
 482                         Offset(pa2, newt, self.vspeed)]
 483                 else:
 484                     # A hole was split. New faces just replace the split one.
 485                     pa.poly = newfaces[0]
 486                     pa.holes = newfaces[0:findex] + [newface0, newface1] + \
 487                                newfaces[findex + 1:]
 488             else:
 489                 # A join
 490                 (_, findex, othfindex, newface0) = splitjoin
 491                 if findex == 0 or othfindex == 0:
 492                     # Outer poly was joined to one hole.
 493                     pa.poly = newface0
 494                     pa.holes = [f for f in newfaces if f is not None]
 495                 else:
 496                     # Two holes were joined
 497                     pa.poly = newfaces[0]
 498                     pa.holes = [f for f in newfaces if f is not None] + \
 499                         [newface0]
 500             self.inneroffsets = [Offset(pa, newt, self.vspeed)]
 501             if pa2:
 502                 self.inneroffsets.append(Offset(pa2, newt, self.vspeed))
 503             if nexttarget > TOL:
 504                 for o in self.inneroffsets:
 505                     o.Build(nexttarget)
 506
 507     def FaceAtSpokeEnds(self, f, t):
 508         """Return a new face that is at the spoke ends of face f at time t.
 509
 510         Also merges any adjacent approximately equal vertices into one vertex,
 511         so returned list may be smaller than len(f).
 512         Also sets the destindex fields of the spokes to the vertex they
 513         will now end at.
 514
 515         Args:
 516           f: list of Spoke - one of self.faces
 517           t: float - time in this offset
 518         Returns:
 519           list of int - indices into self.polyarea.points
 520           (which has been extended with new ones)
 521         """
 522
 523         newface = []
 524         points = self.polyarea.points
 525         for i in range(0, len(f)):
 526             s = f[i]
 527             vcoords = s.EndPoint(t, points, self.vspeed)
 528             v = points.AddPoint(vcoords)
 529             if newface:
 530                 if v == newface[-1]:
 531                     s.destindex = len(newface) - 1
 532                 elif i == len(f) - 1 and v == newface[0]:
 533                     s.destindex = 0
 534                 else:
 535                     newface.append(v)
 536                     s.destindex = len(newface) - 1
 537             else:
 538                 newface.append(v)
 539                 s.destindex = 0
 540             s.dest = v
 541         return newface
 542
 543     def MakeNewFaces(self, t):
 544         """For each face in this offset, make new face extending spokes
 545         to time t.
 546
 547         Args:
 548           t: double - time
 549         Returns:
 550           list of list of int - list of new faces
 551         """
 552
 553         ans = []
 554         for f in self.facespokes:
 555             newf = self.FaceAtSpokeEnds(f, t)
 556             if len(newf) > 2:
 557                 ans.append(newf)
 558         return ans
 559
 560     def SplitJoinFaces(self, newfaces, ev):
 561         r"""Use event ev to split or join faces.
 562
 563         Given ev, an edge event, use the ev spoke to split the
 564         other spoke's inner edge.
 565         If the ev spoke's face and other's face are the same, this splits the
 566         face into two; if the faces are different, it joins them into one.
 567         We have just made faces at the end of the spokes.
 568         We have to remove the edge going from the other spoke to its
 569         next spoke, and replace it with two edges, going to and from
 570         the event spoke's destination.
 571         General situation:
 572              __  s  ____
 573         c\     b\ | /a       /e
 574           \      \|/        /
 575           f----------------g
 576          /        d        \
 577        o/                   \h
 578
 579         where sd is the event spoke and of is the "other spoke",
 580         hg is a spoke, and cf, fg. ge, ad, and db are edges in
 581         the new inside face.
 582         What we are to do is to split fg into two edges, with the
 583         joining point attached where b,s,a join.
 584         There are a bunch of special cases:
 585          - one of split fg edges might have zero length because end points
 586            are already coincident or nearly coincident.
 587          - maybe c==b or e==a
 588
 589         Args:
 590           newfaces: list of list of int - the new faces
 591           ev: OffsetEvent - an edge event
 592         Side Effects:
 593           faces in newfaces that are involved in split or join are
 594           set to None
 595         Returns: one of:
 596           ('split', int, list of int, list of int) - int is the index in
 597               newfaces of the face that was split, two lists are the
 598               split faces
 599           ('join', int, int, list of int) - two ints are the indices in
 600               newfaces of the faces that were joined, and the list is
 601               the joined face
 602         """
 603
 604         # print("SplitJoinFaces", newfaces, ev)
 605         spoke = ev.spoke
 606         other = ev.other
 607         findex = spoke.face
 608         othfindex = other.face
 609         newface = newfaces[findex]
 610         othface = newfaces[othfindex]
 611         nnf = len(newface)
 612         nonf = len(othface)
 613         d = spoke.destindex
 614         f = other.destindex
 615         c = (f - 1) % nonf
 616         g = (f + 1) % nonf
 617         e = (f + 2) % nonf
 618         a = (d - 1) % nnf
 619         b = (d + 1) % nnf
 620         # print("newface=", newface)
 621         # if findex != othfindex: print("othface=", othface)
 622         # print("d=", d, "f=", f, "c=", c, "g=", g, "e=", e, "a=", a, "b=", b)
 623         newface0 = []
 624         newface1 = []
 625         # The two new faces put spoke si's dest on edge between
 626         # pi's dest and qi (edge after pi)'s dest in original face.
 627         # These are indices in the original face; the current dest face
 628         # may have fewer elements because of merging successive points
 629         if findex == othfindex:
 630             # Case where splitting one new face into two.
 631             # The new new faces are:
 632             # [d, g, e, ..., a] and [d, b, ..., c, f]
 633             # (except we actually want the vertex numbers at those positions)
 634             newface0 = [newface[d]]
 635             i = g
 636             while i != d:
 637                 newface0.append(newface[i])
 638                 i = (i + 1) % nnf
 639             newface1 = [newface[d]]
 640             i = b
 641             while i != f:
 642                 newface1.append(newface[i])
 643                 i = (i + 1) % nnf
 644             newface1.append(newface[f])
 645             # print("newface0=", newface0, "newface1=", newface1)
 646             # now the destindex values for the spokes are messed up
 647             # but I don't think we need them again
 648             newfaces[findex] = None
 649             return ('split', findex, newface0, newface1)
 650         else:
 651             # Case where joining two faces into one.
 652             # The new face is splicing d's face between
 653             # f and g in other face (or the reverse of all of that).
 654             newface0 = [othface[i] for i in range(0, f + 1)]
 655             newface0.append(newface[d])
 656             i = b
 657             while i != d:
 658                 newface0.append(newface[i])
 659                 i = (i + 1) % nnf
 660             newface0.append(newface[d])
 661             if g != 0:
 662                 newface0.extend([othface[i] for i in range(g, nonf)])
 663             # print("newface0=", newface0)
 664             newfaces[findex] = None
 665             newfaces[othfindex] = None
 666             return ('join', findex, othfindex, newface0)
 667
 668     def InnerPolyAreas(self):
 669         """Return the interior of the offset (and contained offsets) as
 670         PolyAreas.
 671
 672         Returns:
 673           geom.PolyAreas
 674         """
 675
 676         ans = geom.PolyAreas()
 677         ans.points = self.polyarea.points
 678         _AddInnerAreas(self, ans)
 679         return ans
 680
 681     def MaxAmount(self):
 682         """Returns the maximum offset amount possible.
 683         Returns:
 684           float - maximum amount
 685         """
 686
 687         # Need to do Build on a copy of points
 688         # so don't add points that won't be used when
 689         # really do a Build with a smaller amount
 690         test_points = geom.Points()
 691         test_points.AddPoints(self.polyarea.points, True)
 692         save_points = self.polyarea.points
 693         self.polyarea.points = test_points
 694         self.Build()
 695         max_amount = self._MaxTime()
 696         self.polyarea.points = save_points
 697         return max_amount
 698
 699     def _MaxTime(self):
 700         if self.inneroffsets:
 701             return max([o._MaxTime() for o in self.inneroffsets])
 702         else:
 703             return self.timesofar + self.endtime
 704
 705
 706 def _AddInnerAreas(off, polyareas):
 707     """Add the innermost areas of offset off to polyareas.
 708
 709     Assume that polyareas is already using the proper shared points.
 710
 711     Arguments:
 712       off: Offset
 713       polyareas: geom.PolyAreas
 714     Side Effects:
 715       Any non-zero-area faces in the very inside of off are
 716       added to polyareas.
 717     """
 718
 719     if off.inneroffsets:
 720         for o in off.inneroffsets:
 721             _AddInnerAreas(o, polyareas)
 722     else:
 723         newpa = geom.PolyArea(polyareas.points)
 724         for i, f in enumerate(off.facespokes):
 725             newface = off.FaceAtSpokeEnds(f, off.endtime)
 726             area = abs(geom.SignedArea(newface, polyareas.points))
 727             if area < AREATOL:
 728                 if i == 0:
 729                     break
 730                 else:
 731                     continue
 732             if i == 0:
 733                 newpa.poly = newface
 734                 newpa.data = off.polyarea.data
 735             else:
 736                 newpa.holes.append(newface)
 737         if newpa.poly:
 738             polyareas.polyareas.append(newpa)