Cura/cura_sf/fabmetheus_utilities/intercircle.py

   1 """
   2 Intercircle is a collection of utilities for intersecting circles, used to get smooth loops around a collection of points and inset & outset loops.
   3
   4 """
   5
   6 from __future__ import absolute_import
   7 try:
   8         import psyco
   9         psyco.full()
  10 except:
  11         pass
  12 #Init has to be imported first because it has code to workaround the python bug where relative imports don't work if the module is imported as a main module.
  13 import __init__
  14
  15 from fabmetheus_utilities.vector3 import Vector3
  16 from fabmetheus_utilities import euclidean
  17 import math
  18
  19
  20 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
  21 __date__ = '$Date: 2008/21/04 $'
  22 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
  23
  24
  25 globalDecreasingRadiusMultipliers = [1.0, 0.55, 0.35, 0.2]
  26 globalIntercircleMultiplier = 1.04 # 1.02 is enough to stop known intersection
  27
  28
  29 def addCircleIntersectionLoop(circleIntersectionLoop, circleIntersections):
  30         'Add a circle intersection loop.'
  31         firstCircleIntersection = circleIntersectionLoop[0]
  32         circleIntersectionAhead = firstCircleIntersection
  33         for circleIntersectionIndex in xrange(len(circleIntersections) + 1):
  34                 circleIntersectionAhead = circleIntersectionAhead.getCircleIntersectionAhead()
  35                 if circleIntersectionAhead == firstCircleIntersection or circleIntersectionAhead == None:
  36                         firstCircleIntersection.steppedOn = True
  37                         return
  38                 circleIntersectionAhead.addToList(circleIntersectionLoop)
  39         firstCircleIntersection.steppedOn = True
  40         print('Warning, addCircleIntersectionLoop would have gone into an endless loop.')
  41         print('circleIntersectionLoop')
  42         for circleIntersection in circleIntersectionLoop:
  43                 print(circleIntersection)
  44                 print(circleIntersection.circleNodeAhead)
  45                 print(circleIntersection.circleNodeBehind)
  46         print('firstCircleIntersection')
  47         print(firstCircleIntersection)
  48         print('circleIntersections')
  49         for circleIntersection in circleIntersections:
  50                 print(circleIntersection)
  51
  52 def addEndCap(begin, end, points, radius):
  53         'Get circular end cap.'
  54         beginMinusEnd = begin - end
  55         beginMinusEndLength = abs(beginMinusEnd)
  56         if beginMinusEndLength <= 0.0:
  57                 points.append(begin)
  58                 return
  59         beginMinusEnd *= radius / beginMinusEndLength
  60         perpendicular = complex(-beginMinusEnd.imag, beginMinusEnd.real)
  61         numberOfSides = 20 # to end up with close to unit length corners, 5 * 4
  62         numberOfPositiveSides = numberOfSides / 2
  63         totalAngle = 0.0
  64         angle = euclidean.globalTau / float(numberOfSides)
  65         # dotProductMultiplier to compensate for the corner outset in addInsetPointFromClockwiseTriple
  66         dotProductMultiplier = 2.0 - 1.0 / math.cos(0.5 * angle)
  67         for sideIndex in xrange(numberOfPositiveSides + 1):
  68                 circumferentialPoint = math.sin(totalAngle) * beginMinusEnd + math.cos(totalAngle) * perpendicular
  69                 points.append(begin + circumferentialPoint * dotProductMultiplier)
  70                 totalAngle += angle
  71
  72 def addHalfPath(path, points, radius, thresholdRatio=0.9):
  73         'Add the points from every point on a half path and between points.'
  74         lessThanRadius = 0.75 * radius
  75         for pointIndex in xrange(len(path) - 1):
  76                 begin = path[pointIndex]
  77                 center = path[pointIndex + 1]
  78                 centerBegin = getWiddershinsByLength(begin, center, radius)
  79                 if centerBegin != None:
  80                         addPointsFromSegment(begin + centerBegin, center + centerBegin, points, lessThanRadius, thresholdRatio)
  81                 endIndex = pointIndex + 2
  82                 if endIndex < len(path):
  83                         end = path[endIndex]
  84                         centerEnd = getWiddershinsByLength(center, end, radius)
  85                         if centerBegin != None and centerEnd != None:
  86                                 centerPerpendicular = 0.5 * (centerBegin + centerEnd)
  87                                 points.append(center + centerPerpendicular)
  88                                 if euclidean.getCrossProduct(centerBegin, centerEnd) < 0.0:
  89                                         points.append(center + centerBegin)
  90                                         points.append(center + centerEnd)
  91                         else:
  92                                 points.append(center)
  93         addEndCap(path[0], path[1], points, radius)
  94
  95 def addInsetPointFromClockwiseTriple(begin, center, end, loop, radius):
  96         'Get inset point with possible intersection from clockwise triple, out from widdershins loop.'
  97         centerMinusBegin = center - begin
  98         centerMinusBeginLength = abs(centerMinusBegin)
  99         centerMinusBeginClockwise = None
 100         if centerMinusBeginLength > 0.0:
 101                 centerMinusBeginClockwise = complex(centerMinusBegin.imag, -centerMinusBegin.real) / centerMinusBeginLength
 102         endMinusCenter = end - center
 103         endMinusCenterLength = abs(endMinusCenter)
 104         endMinusCenterClockwise = None
 105         if endMinusCenterLength > 0.0:
 106                 endMinusCenterClockwise = complex(endMinusCenter.imag, -endMinusCenter.real) / endMinusCenterLength
 107         if centerMinusBeginClockwise == None and endMinusCenterClockwise == None:
 108                 return
 109         if centerMinusBeginClockwise == None:
 110                 loop.append(center + endMinusCenterClockwise * radius)
 111                 return
 112         if endMinusCenterClockwise == None:
 113                 loop.append(center + centerMinusBeginClockwise * radius)
 114                 return
 115         centerClockwise = 0.5 * (centerMinusBeginClockwise + endMinusCenterClockwise)
 116         dotProduct = euclidean.getDotProduct(centerMinusBeginClockwise, centerClockwise)
 117         loop.append(center + centerClockwise * radius / max(0.4, abs(dotProduct))) # 0.4 to avoid pointy corners
 118
 119 def addOrbits( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z ):
 120         'Add orbits with the extruder off.'
 121         timeInOrbit = 0.0
 122         while timeInOrbit < temperatureChangeTime:
 123                 for point in loop:
 124                         distanceFeedRate.addGcodeMovementZWithFeedRate( 60.0 * orbitalFeedRatePerSecond, point, z )
 125                 timeInOrbit += euclidean.getLoopLength(loop) / orbitalFeedRatePerSecond
 126
 127 def addOrbitsIfLarge( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z ):
 128         'Add orbits with the extruder off if the orbits are large enough.'
 129         if orbitsAreLarge( loop, temperatureChangeTime ):
 130                 addOrbits( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z )
 131
 132 def addPointsFromSegment( pointBegin, pointEnd, points, radius, thresholdRatio=0.9 ):
 133         'Add point complexes between the endpoints of a segment.'
 134         if radius <= 0.0:
 135                 print('This should never happen, radius should never be zero or less in addPointsFromSegment in intercircle.')
 136         thresholdRadius = radius * thresholdRatio # a higher number would be faster but would leave bigger dangling loops and extra dangling loops.
 137         thresholdDiameter = thresholdRadius + thresholdRadius
 138         segment = pointEnd - pointBegin
 139         segmentLength = abs(segment)
 140         extraCircles = int( math.floor( segmentLength / thresholdDiameter ) )
 141         if extraCircles < 1:
 142                 return
 143         if segmentLength == 0.0:
 144                 print('Warning, segmentLength = 0.0 in intercircle.')
 145                 print('pointBegin')
 146                 print(pointBegin)
 147                 print(pointEnd)
 148                 return
 149         if extraCircles < 2:
 150                 lengthIncrement = segmentLength / ( float(extraCircles) + 1.0 )
 151                 segment *= lengthIncrement / segmentLength
 152                 pointBegin += segment
 153         else:
 154                 pointBegin += segment * thresholdDiameter / segmentLength
 155                 remainingLength = segmentLength - thresholdDiameter - thresholdDiameter
 156                 lengthIncrement = remainingLength / ( float(extraCircles) - 1.0 )
 157                 segment *= lengthIncrement / segmentLength
 158         for circleIndex in xrange(extraCircles):
 159                 points.append( pointBegin )
 160                 pointBegin += segment
 161
 162 def directLoop(isWiddershins, loop):
 163         'Direct the loop.'
 164         if euclidean.isWiddershins(loop) != isWiddershins:
 165                 loop.reverse()
 166
 167 def directLoopLists(isWiddershins, loopLists):
 168         'Direct the loop lists.'
 169         for loopList in loopLists:
 170                 directLoops(isWiddershins, loopList)
 171
 172 def directLoops(isWiddershins, loops):
 173         'Direct the loops.'
 174         for loop in loops:
 175                 directLoop(isWiddershins, loop)
 176
 177 def getAroundsFromLoop(loop, radius, thresholdRatio=0.9):
 178         'Get the arounds from the loop.'
 179         return getAroundsFromPoints(getPointsFromLoop(loop, radius, thresholdRatio), radius)
 180
 181 def getAroundsFromLoops( loops, radius, thresholdRatio=0.9 ):
 182         'Get the arounds from the loops.'
 183         return getAroundsFromPoints(getPointsFromLoops(loops, radius, thresholdRatio), radius)
 184
 185 def getAroundsFromPath(path, radius, thresholdRatio=0.9):
 186         'Get the arounds from the path.'
 187         radius = abs(radius)
 188         points = getPointsFromPath(path, radius, thresholdRatio)
 189         return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
 190
 191 def getAroundsFromPathPoints(points, radius, thresholdRatio=0.9):
 192         'Get the arounds from the path.'
 193         centers = getCentersFromPoints(points, 0.8 * radius)
 194         arounds = []
 195         for center in centers:
 196                 if euclidean.isWiddershins(center):
 197                         arounds.append(euclidean.getSimplifiedPath(center, radius))
 198         return arounds
 199
 200 def getAroundsFromPaths(paths, radius, thresholdRatio=0.9):
 201         'Get the arounds from the path.'
 202         radius = abs(radius)
 203         points = []
 204         for path in paths:
 205                 points += getPointsFromPath(path, radius, thresholdRatio)
 206         return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
 207
 208 def getAroundsFromPoints( points, radius ):
 209         'Get the arounds from the points.'
 210         arounds = []
 211         radius = abs(radius)
 212         centers = getCentersFromPoints(points, globalIntercircleMultiplier * radius)
 213         for center in centers:
 214                 inset = getSimplifiedInsetFromClockwiseLoop(center, radius)
 215                 if isLargeSameDirection(inset, center, radius):
 216                         arounds.append(inset)
 217         return arounds
 218
 219 def getCentersFromCircleNodes( circleNodes, radius ):
 220         'Get the complex centers of the circle intersection loops from circle nodes.'
 221         if len( circleNodes ) < 2:
 222                 return []
 223         circleIntersections = getCircleIntersectionsFromCircleNodes( circleNodes )
 224         circleIntersectionLoops = getCircleIntersectionLoops( circleIntersections )
 225         return getCentersFromIntersectionLoops( circleIntersectionLoops, radius )
 226
 227 def getCentersFromIntersectionLoop(circleIntersectionLoop, radius):
 228         'Get the centers from the intersection loop.'
 229         loop = []
 230         for circleIntersection in circleIntersectionLoop:
 231                 loop.append(circleIntersection.circleNodeAhead.actualPoint)
 232         return loop
 233
 234 def getCentersFromIntersectionLoops( circleIntersectionLoops, radius ):
 235         'Get the centers from the intersection loops.'
 236         centers = []
 237         for circleIntersectionLoop in circleIntersectionLoops:
 238                 centers.append( getCentersFromIntersectionLoop( circleIntersectionLoop, radius ) )
 239         return centers
 240
 241 def getCentersFromLoop( loop, radius ):
 242         'Get the centers of the loop.'
 243         circleNodes = getCircleNodesFromLoop( loop, radius )
 244         return getCentersFromCircleNodes( circleNodes, radius )
 245
 246 def getCentersFromLoopDirection( isWiddershins, loop, radius ):
 247         'Get the centers of the loop which go around in the given direction.'
 248         centers = getCentersFromLoop( loop, radius )
 249         return getLoopsFromLoopsDirection( isWiddershins, centers )
 250
 251 def getCentersFromPoints(points, radius):
 252         'Get the centers from the points.'
 253         circleNodes = getCircleNodesFromPoints(points, abs(radius))
 254         return getCentersFromCircleNodes(circleNodes, abs(radius))
 255
 256 def getCircleIntersectionLoops( circleIntersections ):
 257         'Get all the loops going through the circle intersections.'
 258         circleIntersectionLoops = []
 259         for circleIntersection in circleIntersections:
 260                 if not circleIntersection.steppedOn:
 261                         circleIntersectionLoop = [ circleIntersection ]
 262                         circleIntersectionLoops.append( circleIntersectionLoop )
 263                         addCircleIntersectionLoop( circleIntersectionLoop, circleIntersections )
 264         return circleIntersectionLoops
 265
 266 def getCircleIntersectionsFromCircleNodes(circleNodes):
 267         'Get all the circle intersections which exist between all the circle nodes.'
 268         if len( circleNodes ) < 1:
 269                 return []
 270         circleIntersections = []
 271         index = 0
 272         pixelTable = {}
 273         for circleNode in circleNodes:
 274                 euclidean.addElementToPixelListFromPoint(circleNode, pixelTable, circleNode.dividedPoint)
 275         accumulatedCircleNodeTable = {}
 276         for circleNodeIndex in xrange(len(circleNodes)):
 277                 circleNodeBehind = circleNodes[circleNodeIndex]
 278                 circleNodeIndexMinusOne = circleNodeIndex - 1
 279                 if circleNodeIndexMinusOne >= 0:
 280                         circleNodeAdditional = circleNodes[circleNodeIndexMinusOne]
 281                         euclidean.addElementToPixelListFromPoint(circleNodeAdditional, accumulatedCircleNodeTable, 0.5 * circleNodeAdditional.dividedPoint)
 282                 withinNodes = circleNodeBehind.getWithinNodes(accumulatedCircleNodeTable)
 283                 for circleNodeAhead in withinNodes:
 284                         circleIntersectionForward = CircleIntersection(circleNodeAhead, index, circleNodeBehind)
 285                         if not circleIntersectionForward.isWithinCircles(pixelTable):
 286                                 circleIntersections.append(circleIntersectionForward)
 287                                 circleNodeBehind.circleIntersections.append(circleIntersectionForward)
 288                                 index += 1
 289                         circleIntersectionBackward = CircleIntersection(circleNodeBehind, index, circleNodeAhead)
 290                         if not circleIntersectionBackward.isWithinCircles(pixelTable):
 291                                 circleIntersections.append(circleIntersectionBackward)
 292                                 circleNodeAhead.circleIntersections.append(circleIntersectionBackward)
 293                                 index += 1
 294         return circleIntersections
 295
 296 def getCircleNodesFromLoop(loop, radius, thresholdRatio=0.9):
 297         'Get the circle nodes from every point on a loop and between points.'
 298         radius = abs(radius)
 299         points = getPointsFromLoop( loop, radius, thresholdRatio )
 300         return getCircleNodesFromPoints( points, radius )
 301
 302 def getCircleNodesFromPoints(points, radius):
 303         'Get the circle nodes from a path.'
 304         if radius == 0.0:
 305                 print('Warning, radius is 0 in getCircleNodesFromPoints in intercircle.')
 306                 print(points)
 307                 return []
 308         circleNodes = []
 309         oneOverRadius = 1.000001 / radius # to avoid problem of accidentally integral radius
 310         points = euclidean.getAwayPoints(points, radius)
 311         for point in points:
 312                 circleNodes.append(CircleNode(oneOverRadius, point))
 313         return circleNodes
 314
 315 def getInsetLoopsFromLoop(loop, radius, thresholdRatio=0.9):
 316         'Get the inset loops, which might overlap.'
 317         if radius == 0.0:
 318                 return [loop]
 319         isInset = radius > 0
 320         insetLoops = []
 321         isLoopWiddershins = euclidean.isWiddershins(loop)
 322         arounds = getAroundsFromLoop(loop, radius, thresholdRatio)
 323         for around in arounds:
 324                 leftPoint = euclidean.getLeftPoint(around)
 325                 shouldBeWithin = (isInset == isLoopWiddershins)
 326                 if euclidean.isPointInsideLoop(loop, leftPoint) == shouldBeWithin:
 327                         if isLoopWiddershins != euclidean.isWiddershins(around):
 328                                 around.reverse()
 329                         insetLoops.append(around)
 330         return insetLoops
 331
 332 def getInsetLoopsFromLoops(loops, radius):
 333         'Get the inset loops, which might overlap.'
 334         insetLoops = []
 335         for loop in loops:
 336                 insetLoops += getInsetLoopsFromLoop(loop, radius)
 337         return insetLoops
 338
 339 def getInsetLoopsFromVector3Loop(loop, radius, thresholdRatio=0.9):
 340         'Get the inset loops from vector3 loop, which might overlap.'
 341         if len(loop) < 2:
 342                 return [loop]
 343         loopComplex = euclidean.getComplexPath(loop)
 344         loopComplexes = getInsetLoopsFromLoop(loopComplex, radius)
 345         return euclidean.getVector3Paths(loopComplexes, loop[0].z)
 346
 347 def getInsetSeparateLoopsFromLoops(loops, radius, thresholdRatio=0.9):
 348         'Get the separate inset loops.'
 349         if radius == 0.0:
 350                 return loops
 351         isInset = radius > 0
 352         insetSeparateLoops = []
 353         arounds = getAroundsFromLoops(loops, abs(radius), thresholdRatio)
 354         for around in arounds:
 355                 if isInset == euclidean.getIsInFilledRegion(loops, around[0]):
 356                         if isInset:
 357                                 around.reverse()
 358                         insetSeparateLoops.append(around)
 359         return insetSeparateLoops
 360
 361 def getInsetSeparateLoopsFromAroundLoops(loops, radius, radiusAround, thresholdRatio=0.9):
 362         'Get the separate inset loops.'
 363         if radius == 0.0:
 364                 return loops
 365         isInset = radius > 0
 366         insetSeparateLoops = []
 367         radius = abs(radius)
 368         radiusAround = max(abs(radiusAround), radius)
 369         points = getPointsFromLoops(loops, radiusAround, thresholdRatio)
 370         centers = getCentersFromPoints(points, globalIntercircleMultiplier * radiusAround)
 371         for center in centers:
 372                 inset = getSimplifiedInsetFromClockwiseLoop(center, radius)
 373                 if isLargeSameDirection(inset, center, radius):
 374                         if isInset == euclidean.getIsInFilledRegion(loops, inset[0]):
 375                                 if isInset:
 376                                         inset.reverse()
 377                                 insetSeparateLoops.append(inset)
 378         return insetSeparateLoops
 379
 380 def getIsLarge(loop, radius):
 381         'Determine if the loop is large enough.'
 382         return euclidean.getMaximumSpan(loop) > 2.01 * abs(radius)
 383
 384 def getLargestCenterOutsetLoopFromLoop(loop, radius, thresholdRatio=0.9):
 385         'Get the largest circle outset loop from the loop.'
 386         if radius == 0.0:
 387                 return loop
 388         radius = abs(radius)
 389         points = getPointsFromLoop(loop, radius, thresholdRatio)
 390         centers = getCentersFromPoints(points, globalIntercircleMultiplier * radius)
 391         largestCenterOutset = None
 392         largestOutsetArea = -987654321.0
 393         for center in centers:
 394                 outset = getSimplifiedInsetFromClockwiseLoop(center, radius)
 395                 if isLargeSameDirection(outset, center, radius):
 396                         if euclidean.isPathInsideLoop(loop, outset) != euclidean.isWiddershins(loop):
 397                                 centerOutset = CenterOutset(center, outset)
 398                                 outsetArea = abs(euclidean.getAreaLoop(outset))
 399                                 if outsetArea > largestOutsetArea:
 400                                         largestOutsetArea = outsetArea
 401                                         largestCenterOutset = centerOutset
 402         if largestCenterOutset == None:
 403                 return None
 404         largestCenterOutset.center = euclidean.getSimplifiedLoop(largestCenterOutset.center, radius)
 405         return largestCenterOutset
 406
 407 def getLargestCenterOutsetLoopFromLoopRegardless(loop, radius):
 408         'Get the largest circle outset loop from the loop, even if the radius has to be shrunk and even if there is still no outset loop.'
 409         global globalDecreasingRadiusMultipliers
 410         for decreasingRadiusMultiplier in globalDecreasingRadiusMultipliers:
 411                 decreasingRadius = radius * decreasingRadiusMultiplier
 412                 largestCenterOutsetLoop = getLargestCenterOutsetLoopFromLoop(loop, decreasingRadius)
 413                 if largestCenterOutsetLoop != None:
 414                         return largestCenterOutsetLoop
 415         return CenterOutset(loop, loop)
 416
 417 def getLargestInsetLoopFromLoop(loop, radius):
 418         'Get the largest inset loop from the loop.'
 419         loops = getInsetLoopsFromLoop(loop, radius)
 420         return euclidean.getLargestLoop(loops)
 421
 422 def getLargestInsetLoopFromLoopRegardless( loop, radius ):
 423         'Get the largest inset loop from the loop, even if the radius has to be shrunk and even if there is still no inset loop.'
 424         global globalDecreasingRadiusMultipliers
 425         for decreasingRadiusMultiplier in globalDecreasingRadiusMultipliers:
 426                 decreasingRadius = radius * decreasingRadiusMultiplier
 427                 largestInsetLoop = getLargestInsetLoopFromLoop( loop, decreasingRadius )
 428                 if len( largestInsetLoop ) > 0:
 429                         return largestInsetLoop
 430         print('Warning, there should always be a largestInsetLoop in getLargestInsetLoopFromLoopRegardless in intercircle.')
 431         print(loop)
 432         return loop
 433
 434 def getLoopsFromLoopsDirection( isWiddershins, loops ):
 435         'Get the loops going round in a given direction.'
 436         directionalLoops = []
 437         for loop in loops:
 438                 if euclidean.isWiddershins(loop) == isWiddershins:
 439                         directionalLoops.append(loop)
 440         return directionalLoops
 441
 442 def getPointsFromLoop(loop, radius, thresholdRatio=0.9):
 443         'Get the points from every point on a loop and between points.'
 444         if radius == 0.0:
 445                 print('Warning, radius is 0 in getPointsFromLoop in intercircle.')
 446                 print(loop)
 447                 return loop
 448         radius = abs(radius)
 449         points = []
 450         for pointIndex in xrange(len(loop)):
 451                 pointBegin = loop[pointIndex]
 452                 pointEnd = loop[(pointIndex + 1) % len(loop)]
 453                 points.append( pointBegin )
 454                 addPointsFromSegment( pointBegin, pointEnd, points, radius, thresholdRatio )
 455         return points
 456
 457 def getPointsFromLoops(loops, radius, thresholdRatio=0.9):
 458         'Get the points from every point on a loop and between points.'
 459         points = []
 460         for loop in loops:
 461                 points += getPointsFromLoop(loop, radius, thresholdRatio)
 462         return points
 463
 464 def getPointsFromPath(path, radius, thresholdRatio=0.9):
 465         'Get the points from every point on a path and between points.'
 466         if len(path) < 1:
 467                 return []
 468         if len(path) < 2:
 469                 return path
 470         radius = abs(radius)
 471         points = []
 472         addHalfPath(path, points, radius, thresholdRatio)
 473         addHalfPath(path[: : -1], points, radius, thresholdRatio)
 474         return points
 475
 476 def getSimplifiedInsetFromClockwiseLoop(loop, radius):
 477         'Get loop inset from clockwise loop, out from widdershins loop.'
 478         inset = []
 479         for pointIndex, begin in enumerate(loop):
 480                 center = loop[(pointIndex + 1) % len(loop)]
 481                 end = loop[(pointIndex + 2) % len(loop)]
 482                 addInsetPointFromClockwiseTriple(begin, center, end, inset, radius)
 483         return getWithoutIntersections(euclidean.getSimplifiedLoop(inset, radius))
 484
 485 def getWiddershinsByLength(begin, end, length):
 486         'Get the widdershins by length.'
 487         endMinusBegin = end - begin
 488         endMinusBeginLength = abs(endMinusBegin)
 489         if endMinusBeginLength <= 0.0:
 490                 return None
 491         endMinusBegin *= length / endMinusBeginLength
 492         return complex(-endMinusBegin.imag, endMinusBegin.real)
 493
 494 def getWithoutIntersections( loop ):
 495         'Get loop without intersections.'
 496         lastLoopLength = len( loop )
 497         while lastLoopLength > 3:
 498                 removeIntersection( loop )
 499                 if len( loop ) == lastLoopLength:
 500                         return loop
 501                 lastLoopLength = len( loop )
 502         return loop
 503
 504 def isLargeSameDirection(inset, loop, radius):
 505         'Determine if the inset is in the same direction as the loop and it is large enough.'
 506         if euclidean.isWiddershins(inset) != euclidean.isWiddershins(loop):
 507                 return False
 508         return getIsLarge(inset, radius) and len(inset) > 2
 509
 510 def isLoopIntersectingLoop( anotherLoop, loop ):
 511         'Determine if the a loop is intersecting another loop.'
 512         for pointIndex in xrange(len(loop)):
 513                 pointFirst = loop[pointIndex]
 514                 pointSecond = loop[(pointIndex + 1) % len(loop)]
 515                 segment = pointFirst - pointSecond
 516                 normalizedSegment = euclidean.getNormalized(segment)
 517                 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
 518                 segmentFirstPoint = segmentYMirror * pointFirst
 519                 segmentSecondPoint = segmentYMirror * pointSecond
 520                 if euclidean.isLoopIntersectingInsideXSegment( anotherLoop, segmentFirstPoint.real, segmentSecondPoint.real, segmentYMirror, segmentFirstPoint.imag ):
 521                         return True
 522         return False
 523
 524 def orbitsAreLarge( loop, temperatureChangeTime ):
 525         'Determine if the orbits are large enough.'
 526         if len(loop) < 1:
 527                 print('Zero length loop which was skipped over, this should never happen.')
 528                 return False
 529         return temperatureChangeTime > 1.5
 530
 531 def removeIntersection( loop ):
 532         'Get loop without the first intersection.'
 533         for pointIndex, ahead in enumerate(loop):
 534                 behind = loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ]
 535                 behindEnd = loop[ ( pointIndex + len( loop ) - 2 ) % len( loop ) ]
 536                 behindMidpoint = 0.5 * ( behind + behindEnd )
 537                 aheadEnd = loop[ (pointIndex + 1) % len( loop ) ]
 538                 aheadMidpoint = 0.5 * ( ahead + aheadEnd )
 539                 normalizedSegment = behind - behindMidpoint
 540                 normalizedSegmentLength = abs( normalizedSegment )
 541                 if normalizedSegmentLength > 0.0:
 542                         normalizedSegment /= normalizedSegmentLength
 543                         segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
 544                         behindRotated = segmentYMirror * behind
 545                         behindMidpointRotated = segmentYMirror * behindMidpoint
 546                         aheadRotated = segmentYMirror * ahead
 547                         aheadMidpointRotated = segmentYMirror * aheadMidpoint
 548                         y = behindRotated.imag
 549                         xIntersection = euclidean.getXIntersectionIfExists( aheadRotated, aheadMidpointRotated, y )
 550                         if xIntersection != None:
 551                                 if xIntersection > min( behindMidpointRotated.real, behindRotated.real ) and xIntersection < max( behindMidpointRotated.real, behindRotated.real ):
 552                                         intersectionPoint = normalizedSegment * complex( xIntersection, y )
 553                                         loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ] = intersectionPoint
 554                                         del loop[pointIndex]
 555                                         return
 556
 557
 558 class BoundingLoop:
 559         'A class to hold a bounding loop composed of a minimum complex, a maximum complex and an outset loop.'
 560         def __eq__(self, other):
 561                 'Determine whether this bounding loop is identical to other one.'
 562                 if other == None:
 563                         return False
 564                 return self.minimum == other.minimum and self.maximum == other.maximum and self.loop == other.loop
 565
 566         def __repr__(self):
 567                 'Get the string representation of this bounding loop.'
 568                 return '%s, %s, %s' % ( self.minimum, self.maximum, self.loop )
 569
 570         def getFromLoop( self, loop ):
 571                 'Get the bounding loop from a path.'
 572                 self.loop = loop
 573                 self.maximum = euclidean.getMaximumByComplexPath(loop)
 574                 self.minimum = euclidean.getMinimumByComplexPath(loop)
 575                 return self
 576
 577         def getOutsetBoundingLoop( self, outsetDistance ):
 578                 'Outset the bounding rectangle and loop by a distance.'
 579                 outsetBoundingLoop = BoundingLoop()
 580                 outsetBoundingLoop.maximum = self.maximum + complex( outsetDistance, outsetDistance )
 581                 outsetBoundingLoop.minimum = self.minimum - complex( outsetDistance, outsetDistance )
 582                 greaterThanOutsetDistance = 1.1 * outsetDistance
 583                 centers = getCentersFromLoopDirection( True, self.loop, greaterThanOutsetDistance )
 584                 outsetBoundingLoop.loop = getSimplifiedInsetFromClockwiseLoop( centers[0], outsetDistance )
 585                 return outsetBoundingLoop
 586
 587         def isEntirelyInsideAnother( self, anotherBoundingLoop ):
 588                 'Determine if this bounding loop is entirely inside another bounding loop.'
 589                 if self.minimum.imag < anotherBoundingLoop.minimum.imag or self.minimum.real < anotherBoundingLoop.minimum.real:
 590                         return False
 591                 if self.maximum.imag > anotherBoundingLoop.maximum.imag or self.maximum.real > anotherBoundingLoop.maximum.real:
 592                         return False
 593                 for point in self.loop:
 594                         if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 0:
 595                                 return False
 596                 return not isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
 597
 598         def isOverlappingAnother( self, anotherBoundingLoop ):
 599                 'Determine if this bounding loop is intersecting another bounding loop.'
 600                 if self.isRectangleMissingAnother( anotherBoundingLoop ):
 601                         return False
 602                 for point in self.loop:
 603                         if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 1:
 604                                 return True
 605                 for point in anotherBoundingLoop.loop:
 606                         if euclidean.getNumberOfIntersectionsToLeft( self.loop, point ) % 2 == 1:
 607                                 return True
 608                 return isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
 609
 610         def isOverlappingAnotherInList( self, boundingLoops ):
 611                 'Determine if this bounding loop is intersecting another bounding loop in a list.'
 612                 for boundingLoop in boundingLoops:
 613                         if self.isOverlappingAnother( boundingLoop ):
 614                                 return True
 615                 return False
 616
 617         def isRectangleMissingAnother( self, anotherBoundingLoop ):
 618                 'Determine if the rectangle of this bounding loop is missing the rectangle of another bounding loop.'
 619                 if self.maximum.imag < anotherBoundingLoop.minimum.imag or self.maximum.real < anotherBoundingLoop.minimum.real:
 620                         return True
 621                 return self.minimum.imag > anotherBoundingLoop.maximum.imag or self.minimum.real > anotherBoundingLoop.maximum.real
 622
 623
 624 class CenterOutset:
 625         'A class to hold a center and an outset.'
 626         def __init__(self, center, outset):
 627                 'Set the center and outset.'
 628                 self.center = center
 629                 self.outset = outset
 630
 631         def __repr__(self):
 632                 'Get the string representation of this CenterOutset.'
 633                 return '%s\n%s' % (self.center, self.outset)
 634
 635
 636 class CircleIntersection:
 637         'An intersection of two complex circles.'
 638         def __init__( self, circleNodeAhead, index, circleNodeBehind ):
 639                 self.aheadMinusBehind = 0.5 * ( circleNodeAhead.dividedPoint - circleNodeBehind.dividedPoint )
 640                 self.circleNodeAhead = circleNodeAhead
 641                 self.circleNodeBehind = circleNodeBehind
 642                 self.index = index
 643                 self.steppedOn = False
 644                 demichordWidth = math.sqrt( 1.0 - self.aheadMinusBehind.real * self.aheadMinusBehind.real - self.aheadMinusBehind.imag * self.aheadMinusBehind.imag )
 645                 rotatedClockwiseQuarter = complex( self.aheadMinusBehind.imag, - self.aheadMinusBehind.real )
 646                 rotatedClockwiseQuarterLength = abs( rotatedClockwiseQuarter )
 647                 if rotatedClockwiseQuarterLength == 0:
 648                         print('Warning, rotatedClockwiseQuarter in getDemichord in intercircle is 0')
 649                         print(circleNodeAhead.dividedPoint)
 650                         print(circleNodeBehind.dividedPoint)
 651                         self.demichord = 0.0
 652                 else:
 653                         self.demichord = rotatedClockwiseQuarter * demichordWidth / rotatedClockwiseQuarterLength
 654                 self.positionRelativeToBehind = self.aheadMinusBehind + self.demichord
 655
 656         def __repr__(self):
 657                 'Get the string representation of this CircleIntersection.'
 658                 return '%s, %s, %s, %s' % (self.index, self.getAbsolutePosition(), self.circleNodeBehind, self.circleNodeAhead)
 659
 660         def addToList( self, circleIntersectionPath ):
 661                 'Add this to the circle intersection path, setting stepped on to be true.'
 662                 self.steppedOn = True
 663                 circleIntersectionPath.append(self)
 664
 665         def getAbsolutePosition(self):
 666                 'Get the absolute position.'
 667                 return self.positionRelativeToBehind + self.circleNodeBehind.dividedPoint
 668
 669         def getCircleIntersectionAhead(self):
 670                 'Get the first circle intersection on the circle node ahead.'
 671                 circleIntersections = self.circleNodeAhead.circleIntersections
 672                 circleIntersectionAhead = None
 673                 largestDot = -912345678.0
 674                 for circleIntersection in circleIntersections:
 675                         if not circleIntersection.steppedOn:
 676                                 circleIntersectionRelativeToMidpoint = euclidean.getNormalized(circleIntersection.positionRelativeToBehind + self.aheadMinusBehind)
 677                                 dot = euclidean.getDotProduct(self.demichord, circleIntersectionRelativeToMidpoint)
 678                                 if dot > largestDot:
 679                                         largestDot = dot
 680                                         circleIntersectionAhead = circleIntersection
 681                 if circleIntersectionAhead == None:
 682                         print('Warning, circleIntersectionAhead in getCircleIntersectionAhead in intercircle is None for:')
 683                         print(self.circleNodeAhead.dividedPoint)
 684                         print('circleIntersectionsAhead')
 685                         for circleIntersection in circleIntersections:
 686                                 print(circleIntersection.circleNodeAhead.dividedPoint)
 687                         print('circleIntersectionsBehind')
 688                         for circleIntersection in self.circleNodeBehind.circleIntersections:
 689                                 print(circleIntersection.circleNodeAhead.dividedPoint)
 690                         print('This may lead to a loop not being sliced.')
 691                         print('If this is a problem, you may as well send a bug report, even though I probably can not fix this particular problem.')
 692                 return circleIntersectionAhead
 693
 694         def isWithinCircles(self, pixelTable):
 695                 'Determine if this circle intersection is within the circle node circles.'
 696                 absolutePosition = self.getAbsolutePosition()
 697                 squareValues = euclidean.getSquareValuesFromPoint(pixelTable, absolutePosition)
 698                 for squareValue in squareValues:
 699                         if abs(squareValue.dividedPoint - absolutePosition) < 1.0:
 700                                 if squareValue != self.circleNodeAhead and squareValue != self.circleNodeBehind:
 701                                         return True
 702                 return False
 703
 704
 705 class CircleNode:
 706         'A complex node of complex circle intersections.'
 707         def __init__(self, oneOverRadius, point):
 708                 self.actualPoint = point
 709                 self.circleIntersections = []
 710                 self.dividedPoint = point * oneOverRadius
 711 #               self.index = index # when debugging bring back index
 712
 713         def __repr__(self):
 714                 'Get the string representation of this CircleNode.'
 715 #               return '%s, %s, %s' % (self.index, self.dividedPoint, len(self.circleIntersections)) # when debugging bring back index
 716                 return '%s, %s' % (self.dividedPoint, len(self.circleIntersections))
 717
 718         def getWithinNodes(self, pixelTable):
 719                 'Get the nodes this circle node is within.'
 720                 withinNodes = []
 721                 squareValues = euclidean.getSquareValuesFromPoint(pixelTable, 0.5 * self.dividedPoint)
 722                 for squareValue in squareValues:
 723                         if abs(self.dividedPoint - squareValue.dividedPoint) < 2.0:
 724                                 withinNodes.append(squareValue)
 725                 return withinNodes