mesh_inset/offset.py

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