Cura/cura_sf/fabmetheus_utilities/euclidean.py

   1 """
   2 Euclidean is a collection of python utilities for complex numbers, paths, polygons & Vector3s.
   3
   4 To use euclidean, install python 2.x on your machine, which is avaliable from http://www.python.org/download/
   5
   6 Then in the folder which euclidean is in, type 'python' in a shell to run the python interpreter.  Finally type 'import euclidean' to import these utilities and 'from vector3 import Vector3' to import the Vector3 class.
   7
   8
   9 Below are examples of euclidean use.
  10
  11 >>> from euclidean import *
  12 >>> origin=complex()
  13 >>> right=complex(1.0,0.0)
  14 >>> back=complex(0.0,1.0)
  15 >>> getMaximum(right,back)
  16 1.0, 1.0
  17 >>> polygon=[origin, right, back]
  18 >>> getLoopLength(polygon)
  19 3.4142135623730949
  20 >>> getAreaLoop(polygon)
  21 0.5
  22 """
  23
  24 from __future__ import absolute_import
  25 try:
  26         import psyco
  27         psyco.full()
  28 except:
  29         pass
  30 #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.
  31 import __init__
  32
  33 from fabmetheus_utilities.vector3 import Vector3
  34 from fabmetheus_utilities import xml_simple_writer
  35 import cStringIO
  36 import math
  37 import random
  38
  39
  40 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
  41 __date__ = '$Date: 2008/21/04 $'
  42 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
  43
  44
  45 globalGoldenAngle = 3.8832220774509332 # (math.sqrt(5.0) - 1.0) * math.pi
  46 globalGoldenRatio = 1.6180339887498948482045868 # math.sqrt(1.25) + 0.5
  47 globalTau = math.pi + math.pi # http://tauday.com/
  48
  49
  50 def addElementToListDictionary(element, key, listDictionary):
  51         'Add an element to the list table.'
  52         if key in listDictionary:
  53                 listDictionary[key].append(element)
  54         else:
  55                 listDictionary[key] = [element]
  56
  57 def addElementToListDictionaryIfNotThere(element, key, listDictionary):
  58         'Add the value to the lists.'
  59         if key in listDictionary:
  60                 elements = listDictionary[key]
  61                 if element not in elements:
  62                         elements.append(element)
  63         else:
  64                 listDictionary[key] = [element]
  65
  66 def addElementToPixelList( element, pixelDictionary, x, y ):
  67         'Add an element to the pixel list.'
  68         addElementToListDictionary( element, (x, y), pixelDictionary )
  69
  70 def addElementToPixelListFromPoint( element, pixelDictionary, point ):
  71         'Add an element to the pixel list.'
  72         addElementToPixelList( element, pixelDictionary, int( round( point.real ) ), int( round( point.imag ) ) )
  73
  74 def addHorizontallyBoundedPoint(begin, center, end, horizontalBegin, horizontalEnd, path):
  75         'Add point if it is within the horizontal bounds.'
  76         if center.real >= horizontalEnd and center.real <= horizontalBegin:
  77                 path.append(center)
  78                 return
  79         if end != None:
  80                 if center.real > horizontalBegin and end.real <= horizontalBegin:
  81                         centerMinusEnd = center - end
  82                         along = (center.real - horizontalBegin) / centerMinusEnd.real
  83                         path.append(center - along * centerMinusEnd)
  84                         return
  85         if begin != None:
  86                 if center.real < horizontalEnd and begin.real >= horizontalEnd:
  87                         centerMinusBegin = center - begin
  88                         along = (center.real - horizontalEnd) / centerMinusBegin.real
  89                         path.append(center - along * centerMinusBegin)
  90
  91 def addListToListTable( elementList, key, listDictionary ):
  92         'Add a list to the list table.'
  93         if key in listDictionary:
  94                 listDictionary[key] += elementList
  95         else:
  96                 listDictionary[key] = elementList
  97
  98 def addLoopToPixelTable( loop, pixelDictionary, width ):
  99         'Add loop to the pixel table.'
 100         for pointIndex in xrange(len(loop)):
 101                 pointBegin = loop[pointIndex]
 102                 pointEnd = loop[(pointIndex + 1) % len(loop)]
 103                 addValueSegmentToPixelTable( pointBegin, pointEnd, pixelDictionary, None, width )
 104
 105 def addNestedRingBeginning(distanceFeedRate, loop, z):
 106         'Add nested ring beginning to gcode output.'
 107         distanceFeedRate.addLine('(<nestedRing>)')
 108         distanceFeedRate.addLine('(<boundaryPerimeter>)')
 109         for point in loop:
 110                 pointVector3 = Vector3(point.real, point.imag, z)
 111                 distanceFeedRate.addLine(distanceFeedRate.getBoundaryLine(pointVector3))
 112
 113 def addPathToPixelTable( path, pixelDictionary, value, width ):
 114         'Add path to the pixel table.'
 115         for pointIndex in xrange( len(path) - 1 ):
 116                 pointBegin = path[pointIndex]
 117                 pointEnd = path[pointIndex + 1]
 118                 addValueSegmentToPixelTable( pointBegin, pointEnd, pixelDictionary, value, width )
 119
 120 def addPixelTableToPixelTable( fromPixelTable, intoPixelTable ):
 121         'Add from pixel table to the into pixel table.'
 122         for fromPixelTableKey in fromPixelTable.keys():
 123                 intoPixelTable[ fromPixelTableKey ] = fromPixelTable[ fromPixelTableKey ]
 124
 125 def addPixelToPixelTableWithSteepness( isSteep, pixelDictionary, value, x, y ):
 126         'Add pixels to the pixel table with steepness.'
 127         if isSteep:
 128                 pixelDictionary[(y, x)] = value
 129         else:
 130                 pixelDictionary[(x, y)] = value
 131
 132 def addPointToPath( path, pixelDictionary, point, value, width ):
 133         'Add a point to a path and the pixel table.'
 134         path.append(point)
 135         if len(path) < 2:
 136                 return
 137         begin = path[-2]
 138         addValueSegmentToPixelTable( begin, point, pixelDictionary, value, width )
 139
 140 def addSegmentToPixelTable( beginComplex, endComplex, pixelDictionary, shortenDistanceBegin, shortenDistanceEnd, width ):
 141         'Add line segment to the pixel table.'
 142         if abs( beginComplex - endComplex ) <= 0.0:
 143                 return
 144         beginComplex /= width
 145         endComplex /= width
 146         if shortenDistanceBegin > 0.0:
 147                 endMinusBeginComplex = endComplex - beginComplex
 148                 endMinusBeginComplexLength = abs( endMinusBeginComplex )
 149                 if endMinusBeginComplexLength < shortenDistanceBegin:
 150                         return
 151                 beginComplex = beginComplex + endMinusBeginComplex * shortenDistanceBegin / endMinusBeginComplexLength
 152         if shortenDistanceEnd > 0.0:
 153                 beginMinusEndComplex = beginComplex - endComplex
 154                 beginMinusEndComplexLength = abs( beginMinusEndComplex )
 155                 if beginMinusEndComplexLength < 0.0:
 156                         return
 157                 endComplex = endComplex + beginMinusEndComplex * shortenDistanceEnd / beginMinusEndComplexLength
 158         deltaX = endComplex.real - beginComplex.real
 159         deltaY = endComplex.imag - beginComplex.imag
 160         isSteep = abs( deltaY ) > abs( deltaX )
 161         if isSteep:
 162                 beginComplex = complex( beginComplex.imag, beginComplex.real )
 163                 endComplex = complex( endComplex.imag, endComplex.real )
 164         if beginComplex.real > endComplex.real:
 165                 endComplex, beginComplex = beginComplex, endComplex
 166         deltaX = endComplex.real - beginComplex.real
 167         deltaY = endComplex.imag - beginComplex.imag
 168         if deltaX > 0.0:
 169                 gradient = deltaY / deltaX
 170         else:
 171                 gradient = 0.0
 172                 print('Warning, deltaX in addSegmentToPixelTable in euclidean is 0.')
 173                 print(beginComplex)
 174                 print(endComplex)
 175                 print(shortenDistanceBegin)
 176                 print(shortenDistanceEnd)
 177                 print(width)
 178         xBegin = int(round(beginComplex.real))
 179         xEnd = int(round(endComplex.real))
 180         yIntersection = beginComplex.imag - beginComplex.real * gradient
 181         if isSteep:
 182                 pixelDictionary[( int( round( beginComplex.imag ) ), xBegin)] = None
 183                 pixelDictionary[( int( round( endComplex.imag ) ), xEnd )] = None
 184                 for x in xrange( xBegin + 1, xEnd ):
 185                         y = int( math.floor( yIntersection + x * gradient ) )
 186                         pixelDictionary[(y, x)] = None
 187                         pixelDictionary[(y + 1, x)] = None
 188         else:
 189                 pixelDictionary[(xBegin, int( round( beginComplex.imag ) ) )] = None
 190                 pixelDictionary[(xEnd, int( round( endComplex.imag ) ) )] = None
 191                 for x in xrange( xBegin + 1, xEnd ):
 192                         y = int( math.floor( yIntersection + x * gradient ) )
 193                         pixelDictionary[(x, y)] = None
 194                         pixelDictionary[(x, y + 1)] = None
 195
 196 def addSquareTwoToPixelDictionary(pixelDictionary, point, value, width):
 197         'Add square with two pixels around the center to pixel dictionary.'
 198         point /= width
 199         x = int(round(point.real))
 200         y = int(round(point.imag))
 201         for xStep in xrange(x - 2, x + 3):
 202                 for yStep in xrange(y - 2, y + 3):
 203                         pixelDictionary[(xStep, yStep)] = value
 204
 205 def addToThreadsFromLoop(extrusionHalfWidth, gcodeType, loop, oldOrderedLocation, skein):
 206         'Add to threads from the last location from loop.'
 207         loop = getLoopStartingClosest(extrusionHalfWidth, oldOrderedLocation.dropAxis(), loop)
 208         oldOrderedLocation.x = loop[0].real
 209         oldOrderedLocation.y = loop[0].imag
 210         gcodeTypeStart = gcodeType
 211         if isWiddershins(loop):
 212                 skein.distanceFeedRate.addLine('(<%s> outer )' % gcodeType)
 213         else:
 214                 skein.distanceFeedRate.addLine('(<%s> inner )' % gcodeType)
 215         skein.addGcodeFromThreadZ(loop + [loop[0]], oldOrderedLocation.z)
 216         skein.distanceFeedRate.addLine('(</%s>)' % gcodeType)
 217
 218 def addToThreadsRemove(extrusionHalfWidth, nestedRings, oldOrderedLocation, skein, threadSequence):
 219         'Add to threads from the last location from nested rings.'
 220         while len(nestedRings) > 0:
 221                 getTransferClosestNestedRing(extrusionHalfWidth, nestedRings, oldOrderedLocation, skein, threadSequence)
 222
 223 def addValueSegmentToPixelTable( beginComplex, endComplex, pixelDictionary, value, width ):
 224         'Add line segment to the pixel table.'
 225         if abs( beginComplex - endComplex ) <= 0.0:
 226                 return
 227         beginComplex /= width
 228         endComplex /= width
 229         deltaX = endComplex.real - beginComplex.real
 230         deltaY = endComplex.imag - beginComplex.imag
 231         isSteep = abs( deltaY ) > abs( deltaX )
 232         if isSteep:
 233                 beginComplex = complex( beginComplex.imag, beginComplex.real )
 234                 endComplex = complex( endComplex.imag, endComplex.real )
 235         if beginComplex.real > endComplex.real:
 236                 endComplex, beginComplex = beginComplex, endComplex
 237         deltaX = endComplex.real - beginComplex.real
 238         deltaY = endComplex.imag - beginComplex.imag
 239         if deltaX > 0.0:
 240                 gradient = deltaY / deltaX
 241         else:
 242                 gradient = 0.0
 243                 print('Warning, deltaX in addValueSegmentToPixelTable in euclidean is 0.')
 244                 print(beginComplex)
 245                 print(value)
 246                 print(endComplex)
 247                 print(width)
 248         xBegin = int(round(beginComplex.real))
 249         xEnd = int(round(endComplex.real))
 250         yIntersection = beginComplex.imag - beginComplex.real * gradient
 251         if isSteep:
 252                 pixelDictionary[(int( round( beginComplex.imag ) ), xBegin)] = value
 253                 pixelDictionary[(int( round( endComplex.imag ) ), xEnd)] = value
 254                 for x in xrange( xBegin + 1, xEnd ):
 255                         y = int( math.floor( yIntersection + x * gradient ) )
 256                         pixelDictionary[(y, x)] = value
 257                         pixelDictionary[(y + 1, x)] = value
 258         else:
 259                 pixelDictionary[(xBegin, int( round( beginComplex.imag ) ))] = value
 260                 pixelDictionary[(xEnd, int( round( endComplex.imag ) ))] = value
 261                 for x in xrange( xBegin + 1, xEnd ):
 262                         y = int( math.floor( yIntersection + x * gradient ) )
 263                         pixelDictionary[(x, y)] = value
 264                         pixelDictionary[(x, y + 1)] = value
 265
 266 def addValueToOutput(depth, keyInput, output, value):
 267         'Add value to the output.'
 268         depthStart = '  ' * depth
 269         output.write('%s%s:' % (depthStart, keyInput))
 270         if value.__class__ == dict:
 271                 output.write('\n')
 272                 keys = value.keys()
 273                 keys.sort()
 274                 for key in keys:
 275                         addValueToOutput(depth + 1, key, output, value[key])
 276                 return
 277         if value.__class__ == list:
 278                 output.write('\n')
 279                 for elementIndex, element in enumerate(value):
 280                         addValueToOutput(depth + 1, elementIndex, output, element)
 281                 return
 282         output.write(' %s\n' % value)
 283
 284 def addXIntersectionIndexesFromLoopListsY( loopLists, xIntersectionIndexList, y ):
 285         'Add the x intersection indexes for the loop lists.'
 286         for loopListIndex in xrange( len(loopLists) ):
 287                 loopList = loopLists[ loopListIndex ]
 288                 addXIntersectionIndexesFromLoopsY( loopList, loopListIndex, xIntersectionIndexList, y )
 289
 290 def addXIntersectionIndexesFromLoopsY( loops, solidIndex, xIntersectionIndexList, y ):
 291         'Add the x intersection indexes for the loops.'
 292         for loop in loops:
 293                 addXIntersectionIndexesFromLoopY( loop, solidIndex, xIntersectionIndexList, y )
 294
 295 def addXIntersectionIndexesFromLoopY( loop, solidIndex, xIntersectionIndexList, y ):
 296         'Add the x intersection indexes for a loop.'
 297         for pointIndex in xrange(len(loop)):
 298                 pointFirst = loop[pointIndex]
 299                 pointSecond = loop[(pointIndex + 1) % len(loop)]
 300                 xIntersection = getXIntersectionIfExists( pointFirst, pointSecond, y )
 301                 if xIntersection != None:
 302                         xIntersectionIndexList.append( XIntersectionIndex( solidIndex, xIntersection ) )
 303
 304 def addXIntersectionIndexesFromSegment( index, segment, xIntersectionIndexList ):
 305         'Add the x intersection indexes from the segment.'
 306         for endpoint in segment:
 307                 xIntersectionIndexList.append( XIntersectionIndex( index, endpoint.point.real ) )
 308
 309 def addXIntersectionIndexesFromSegments( index, segments, xIntersectionIndexList ):
 310         'Add the x intersection indexes from the segments.'
 311         for segment in segments:
 312                 addXIntersectionIndexesFromSegment( index, segment, xIntersectionIndexList )
 313
 314 def addXIntersectionIndexesFromXIntersections( index, xIntersectionIndexList, xIntersections ):
 315         'Add the x intersection indexes from the XIntersections.'
 316         for xIntersection in xIntersections:
 317                 xIntersectionIndexList.append( XIntersectionIndex( index, xIntersection ) )
 318
 319 def addXIntersections( loop, xIntersections, y ):
 320         'Add the x intersections for a loop.'
 321         for pointIndex in xrange(len(loop)):
 322                 pointFirst = loop[pointIndex]
 323                 pointSecond = loop[(pointIndex + 1) % len(loop)]
 324                 xIntersection = getXIntersectionIfExists( pointFirst, pointSecond, y )
 325                 if xIntersection != None:
 326                         xIntersections.append( xIntersection )
 327
 328 def addXIntersectionsFromLoopForTable(loop, xIntersectionsTable, width):
 329         'Add the x intersections for a loop into a table.'
 330         for pointIndex in xrange(len(loop)):
 331                 pointBegin = loop[pointIndex]
 332                 pointEnd = loop[(pointIndex + 1) % len(loop)]
 333                 if pointBegin.imag > pointEnd.imag:
 334                         pointOriginal = pointBegin
 335                         pointBegin = pointEnd
 336                         pointEnd = pointOriginal
 337                 fillBegin = int( math.ceil( pointBegin.imag / width ) )
 338                 fillEnd = int( math.ceil( pointEnd.imag / width ) )
 339                 if fillEnd > fillBegin:
 340                         secondMinusFirstComplex = pointEnd - pointBegin
 341                         secondMinusFirstImaginaryOverReal = secondMinusFirstComplex.real / secondMinusFirstComplex.imag
 342                         beginRealMinusImaginary = pointBegin.real - pointBegin.imag * secondMinusFirstImaginaryOverReal
 343                         for fillLine in xrange( fillBegin, fillEnd ):
 344                                 y = fillLine * width
 345                                 xIntersection = y * secondMinusFirstImaginaryOverReal + beginRealMinusImaginary
 346                                 addElementToListDictionary( xIntersection, fillLine, xIntersectionsTable )
 347
 348 def addXIntersectionsFromLoops(loops, xIntersections, y):
 349         'Add the x intersections for the loops.'
 350         for loop in loops:
 351                 addXIntersections(loop, xIntersections, y)
 352
 353 def addXIntersectionsFromLoopsForTable(loops, xIntersectionsTable, width):
 354         'Add the x intersections for a loop into a table.'
 355         for loop in loops:
 356                 addXIntersectionsFromLoopForTable(loop, xIntersectionsTable, width)
 357
 358 def compareSegmentLength( endpoint, otherEndpoint ):
 359         'Get comparison in order to sort endpoints in ascending order of segment length.'
 360         if endpoint.segmentLength > otherEndpoint.segmentLength:
 361                 return 1
 362         if endpoint.segmentLength < otherEndpoint.segmentLength:
 363                 return - 1
 364         return 0
 365
 366 def concatenateRemovePath(connectedPaths, pathIndex, paths, pixelDictionary, segments, sharpestProduct, width):
 367         'Get connected paths from paths.'
 368         bottomSegment = segments[pathIndex]
 369         path = paths[pathIndex]
 370         if bottomSegment == None:
 371                 connectedPaths.append(path)
 372                 return
 373         endpoints = getEndpointsFromSegments(segments[pathIndex + 1 :])
 374         bottomSegmentEndpoint = bottomSegment[0]
 375         nextEndpoint = bottomSegmentEndpoint.getClosestMissCheckEndpointPath(endpoints, bottomSegmentEndpoint.path, pixelDictionary, sharpestProduct, width)
 376         if nextEndpoint == None:
 377                 bottomSegmentEndpoint = bottomSegment[1]
 378                 nextEndpoint = bottomSegmentEndpoint.getClosestMissCheckEndpointPath(endpoints, bottomSegmentEndpoint.path, pixelDictionary, sharpestProduct, width)
 379         if nextEndpoint == None:
 380                 connectedPaths.append(path)
 381                 return
 382         if len(bottomSegmentEndpoint.path) > 0 and len(nextEndpoint.path) > 0:
 383                 bottomEnd = bottomSegmentEndpoint.path[-1]
 384                 nextBegin = nextEndpoint.path[-1]
 385                 nextMinusBottomNormalized = getNormalized(nextBegin - bottomEnd)
 386                 if len( bottomSegmentEndpoint.path ) > 1:
 387                         bottomPenultimate = bottomSegmentEndpoint.path[-2]
 388                         if getDotProduct(getNormalized(bottomPenultimate - bottomEnd), nextMinusBottomNormalized) > 0.99:
 389                                 connectedPaths.append(path)
 390                                 return
 391                 if len( nextEndpoint.path ) > 1:
 392                         nextPenultimate = nextEndpoint.path[-2]
 393                         if getDotProduct(getNormalized(nextPenultimate - nextBegin), - nextMinusBottomNormalized) > 0.99:
 394                                 connectedPaths.append(path)
 395                                 return
 396         nextEndpoint.path.reverse()
 397         concatenatedPath = bottomSegmentEndpoint.path + nextEndpoint.path
 398         paths[nextEndpoint.pathIndex] = concatenatedPath
 399         segments[nextEndpoint.pathIndex] = getSegmentFromPath(concatenatedPath, nextEndpoint.pathIndex)
 400         addValueSegmentToPixelTable(bottomSegmentEndpoint.point, nextEndpoint.point, pixelDictionary, None, width)
 401
 402 def getAngleAroundZAxisDifference( subtractFromVec3, subtractVec3 ):
 403         'Get the angle around the Z axis difference between a pair of Vector3s.'
 404         subtractVectorMirror = complex( subtractVec3.x , - subtractVec3.y )
 405         differenceVector = getRoundZAxisByPlaneAngle( subtractVectorMirror, subtractFromVec3 )
 406         return math.atan2( differenceVector.y, differenceVector.x )
 407
 408 def getAngleDifferenceByComplex( subtractFromComplex, subtractComplex ):
 409         'Get the angle between a pair of normalized complexes.'
 410         subtractComplexMirror = complex( subtractComplex.real , - subtractComplex.imag )
 411         differenceComplex = subtractComplexMirror * subtractFromComplex
 412         return math.atan2( differenceComplex.imag, differenceComplex.real )
 413
 414 def getAreaLoop(loop):
 415         'Get the area of a complex polygon.'
 416         areaLoopDouble = 0.0
 417         for pointIndex, point in enumerate(loop):
 418                 pointEnd  = loop[(pointIndex + 1) % len(loop)]
 419                 areaLoopDouble += point.real * pointEnd.imag - pointEnd.real * point.imag
 420         return 0.5 * areaLoopDouble
 421
 422 def getAreaLoopAbsolute(loop):
 423         'Get the absolute area of a complex polygon.'
 424         return abs(getAreaLoop(loop))
 425
 426 def getAreaLoops(loops):
 427         'Get the area of a list of complex polygons.'
 428         areaLoops = 0.0
 429         for loop in loops:
 430                 areaLoops += getAreaLoop(loop)
 431         return areaLoops
 432
 433 def getAreaVector3LoopAbsolute(loop):
 434         'Get the absolute area of a vector3 polygon.'
 435         return getAreaLoopAbsolute(getComplexPath(loop))
 436
 437 def getAroundLoop(begin, end, loop):
 438         'Get an arc around a loop.'
 439         aroundLoop = []
 440         if end <= begin:
 441                 end += len(loop)
 442         for pointIndex in xrange(begin, end):
 443                 aroundLoop.append(loop[pointIndex % len(loop)])
 444         return aroundLoop
 445
 446 def getAwayPath(path, radius):
 447         'Get a path with only the points that are far enough away from each other, except for the last point.'
 448         if len(path) < 2:
 449                 return path
 450         lastPoint = path[-1]
 451         awayPath = getAwayPoints(path, radius)
 452         if len(awayPath) == 0:
 453                 return [lastPoint]
 454         if abs(lastPoint - awayPath[-1]) > 0.001 * radius:
 455                 awayPath.append(lastPoint)
 456         return awayPath
 457
 458 def getAwayPoints(points, radius):
 459         'Get a path with only the points that are far enough away from each other.'
 460         awayPoints = []
 461         oneOverOverlapDistance = 1000.0 / radius
 462         pixelDictionary = {}
 463         for point in points:
 464                 x = int(point.real * oneOverOverlapDistance)
 465                 y = int(point.imag * oneOverOverlapDistance)
 466                 if not getSquareIsOccupied(pixelDictionary, x, y):
 467                         awayPoints.append(point)
 468                         pixelDictionary[(x, y)] = None
 469         return awayPoints
 470
 471 def getBooleanFromDictionary(defaultBoolean, dictionary, key):
 472         'Get boolean from the dictionary and key.'
 473         if key not in dictionary:
 474                 return defaultBoolean
 475         return getBooleanFromValue(dictionary[key])
 476
 477 def getBooleanFromValue(value):
 478         'Get boolean from the word.'
 479         firstCharacter = str(value).lower().lstrip()[: 1]
 480         return firstCharacter == 't' or firstCharacter == '1'
 481
 482 def getBottomByPath(path):
 483         'Get the bottom of the path.'
 484         bottom = 987654321987654321.0
 485         for point in path:
 486                 bottom = min(bottom, point.z)
 487         return bottom
 488
 489 def getBottomByPaths(paths):
 490         'Get the bottom of the paths.'
 491         bottom = 987654321987654321.0
 492         for path in paths:
 493                 for point in path:
 494                         bottom = min(bottom, point.z)
 495         return bottom
 496
 497 def getClippedAtEndLoopPath( clip, loopPath ):
 498         'Get a clipped loop path.'
 499         if clip <= 0.0:
 500                 return loopPath
 501         loopPathLength = getPathLength(loopPath)
 502         clip = min( clip, 0.3 * loopPathLength )
 503         lastLength = 0.0
 504         pointIndex = 0
 505         totalLength = 0.0
 506         clippedLength = loopPathLength - clip
 507         while totalLength < clippedLength and pointIndex < len(loopPath) - 1:
 508                 firstPoint = loopPath[pointIndex]
 509                 secondPoint  = loopPath[pointIndex + 1]
 510                 pointIndex += 1
 511                 lastLength = totalLength
 512                 totalLength += abs(firstPoint - secondPoint)
 513         remainingLength = clippedLength - lastLength
 514         clippedLoopPath = loopPath[ : pointIndex ]
 515         ultimateClippedPoint = loopPath[pointIndex]
 516         penultimateClippedPoint = clippedLoopPath[-1]
 517         segment = ultimateClippedPoint - penultimateClippedPoint
 518         segmentLength = abs(segment)
 519         if segmentLength <= 0.0:
 520                 return clippedLoopPath
 521         newUltimatePoint = penultimateClippedPoint + segment * remainingLength / segmentLength
 522         return clippedLoopPath + [newUltimatePoint]
 523
 524 def getClippedLoopPath(clip, loopPath):
 525         'Get a clipped loop path.'
 526         if clip <= 0.0:
 527                 return loopPath
 528         loopPathLength = getPathLength(loopPath)
 529         clip = min(clip, 0.3 * loopPathLength)
 530         lastLength = 0.0
 531         pointIndex = 0
 532         totalLength = 0.0
 533         while totalLength < clip and pointIndex < len(loopPath) - 1:
 534                 firstPoint = loopPath[pointIndex]
 535                 secondPoint  = loopPath[pointIndex + 1]
 536                 pointIndex += 1
 537                 lastLength = totalLength
 538                 totalLength += abs(firstPoint - secondPoint)
 539         remainingLength = clip - lastLength
 540         clippedLoopPath = loopPath[pointIndex :]
 541         ultimateClippedPoint = clippedLoopPath[0]
 542         penultimateClippedPoint = loopPath[pointIndex - 1]
 543         segment = ultimateClippedPoint - penultimateClippedPoint
 544         segmentLength = abs(segment)
 545         loopPath = clippedLoopPath
 546         if segmentLength > 0.0:
 547                 newUltimatePoint = penultimateClippedPoint + segment * remainingLength / segmentLength
 548                 loopPath = [newUltimatePoint] + loopPath
 549         return getClippedAtEndLoopPath(clip, loopPath)
 550
 551 def getClippedSimplifiedLoopPath(clip, loopPath, radius):
 552         'Get a clipped and simplified loop path.'
 553         return getSimplifiedPath(getClippedLoopPath(clip, loopPath), radius)
 554
 555 def getClosestDistanceIndexToLine(point, loop):
 556         'Get the distance squared to the closest segment of the loop and index of that segment.'
 557         smallestDistance = 987654321987654321.0
 558         closestDistanceIndex = None
 559         for pointIndex in xrange(len(loop)):
 560                 segmentBegin = loop[pointIndex]
 561                 segmentEnd = loop[(pointIndex + 1) % len(loop)]
 562                 distance = getDistanceToPlaneSegment(segmentBegin, segmentEnd, point)
 563                 if distance < smallestDistance:
 564                         smallestDistance = distance
 565                         closestDistanceIndex = DistanceIndex(distance, pointIndex)
 566         return closestDistanceIndex
 567
 568 def getClosestPointOnSegment(segmentBegin, segmentEnd, point):
 569         'Get the closest point on the segment.'
 570         segmentDifference = segmentEnd - segmentBegin
 571         if abs(segmentDifference) <= 0.0:
 572                 return segmentBegin
 573         pointMinusSegmentBegin = point - segmentBegin
 574         beginPlaneDot = getDotProduct(pointMinusSegmentBegin, segmentDifference)
 575         differencePlaneDot = getDotProduct(segmentDifference, segmentDifference)
 576         intercept = beginPlaneDot / differencePlaneDot
 577         intercept = max(intercept, 0.0)
 578         intercept = min(intercept, 1.0)
 579         return segmentBegin + segmentDifference * intercept
 580
 581 def getComplexByCommaString( valueCommaString ):
 582         'Get the commaString as a complex.'
 583         try:
 584                 splitLine = valueCommaString.replace(',', ' ').split()
 585                 return complex( float( splitLine[0] ), float(splitLine[1]) )
 586         except:
 587                 pass
 588         return None
 589
 590 def getComplexByWords(words, wordIndex=0):
 591         'Get the complex by the first two words.'
 592         try:
 593                 return complex(float(words[wordIndex]), float(words[wordIndex + 1]))
 594         except:
 595                 pass
 596         return None
 597
 598 def getComplexDefaultByDictionary( defaultComplex, dictionary, key ):
 599         'Get the value as a complex.'
 600         if key in dictionary:
 601                 return complex( dictionary[key].strip().replace('(', '').replace(')', '') )
 602         return defaultComplex
 603
 604 def getComplexDefaultByDictionaryKeys( defaultComplex, dictionary, keyX, keyY ):
 605         'Get the value as a complex.'
 606         x = getFloatDefaultByDictionary( defaultComplex.real, dictionary, keyX )
 607         y = getFloatDefaultByDictionary( defaultComplex.real, dictionary, keyY )
 608         return complex(x, y)
 609
 610 def getComplexPath(vector3Path):
 611         'Get the complex path from the vector3 path.'
 612         complexPath = []
 613         for point in vector3Path:
 614                 complexPath.append(point.dropAxis())
 615         return complexPath
 616
 617 def getComplexPathByMultiplier(multiplier, path):
 618         'Get the multiplied complex path.'
 619         complexPath = []
 620         for point in path:
 621                 complexPath.append(multiplier * point)
 622         return complexPath
 623
 624 def getComplexPaths(vector3Paths):
 625         'Get the complex paths from the vector3 paths.'
 626         complexPaths = []
 627         for vector3Path in vector3Paths:
 628                 complexPaths.append(getComplexPath(vector3Path))
 629         return complexPaths
 630
 631 def getComplexPolygon(center, radius, sides, startAngle=0.0):
 632         'Get the complex polygon.'
 633         complexPolygon = []
 634         sideAngle = 2.0 * math.pi / float(sides)
 635         for side in xrange(abs(sides)):
 636                 unitPolar = getWiddershinsUnitPolar(startAngle)
 637                 complexPolygon.append(unitPolar * radius + center)
 638                 startAngle += sideAngle
 639         return complexPolygon
 640
 641 def getComplexPolygonByComplexRadius(radius, sides, startAngle=0.0):
 642         'Get the complex polygon.'
 643         complexPolygon = []
 644         sideAngle = 2.0 * math.pi / float(sides)
 645         for side in xrange(abs(sides)):
 646                 unitPolar = getWiddershinsUnitPolar(startAngle)
 647                 complexPolygon.append(complex(unitPolar.real * radius.real, unitPolar.imag * radius.imag))
 648                 startAngle += sideAngle
 649         return complexPolygon
 650
 651 def getComplexPolygonByStartEnd(endAngle, radius, sides, startAngle=0.0):
 652         'Get the complex polygon by start and end angle.'
 653         angleExtent = endAngle - startAngle
 654         sideAngle = 2.0 * math.pi / float(sides)
 655         sides = int(math.ceil(abs(angleExtent / sideAngle)))
 656         sideAngle = angleExtent / float(sides)
 657         complexPolygon = []
 658         for side in xrange(abs(sides) + 1):
 659                 unitPolar = getWiddershinsUnitPolar(startAngle)
 660                 complexPolygon.append(unitPolar * radius)
 661                 startAngle += sideAngle
 662         return getLoopWithoutCloseEnds(0.000001 * radius, complexPolygon)
 663
 664 def getConcatenatedList(originalLists):
 665         'Get the lists as one concatenated list.'
 666         concatenatedList = []
 667         for originalList in originalLists:
 668                 concatenatedList += originalList
 669         return concatenatedList
 670
 671 def getConnectedPaths(paths, pixelDictionary, sharpestProduct, width):
 672         'Get connected paths from paths.'
 673         if len(paths) < 2:
 674                 return paths
 675         connectedPaths = []
 676         segments = []
 677         for pathIndex in xrange(len(paths)):
 678                 path = paths[pathIndex]
 679                 segments.append(getSegmentFromPath(path, pathIndex))
 680         for pathIndex in xrange(0, len(paths) - 1):
 681                 concatenateRemovePath(connectedPaths, pathIndex, paths, pixelDictionary, segments, sharpestProduct, width)
 682         connectedPaths.append(paths[-1])
 683         return connectedPaths
 684
 685 def getCrossProduct(firstComplex, secondComplex):
 686         'Get z component cross product of a pair of complexes.'
 687         return firstComplex.real * secondComplex.imag - firstComplex.imag * secondComplex.real
 688
 689 def getDecimalPlacesCarried(extraDecimalPlaces, value):
 690         'Get decimal places carried by the decimal places of the value plus the extraDecimalPlaces.'
 691         return max(0, 1 + int(math.ceil(extraDecimalPlaces - math.log10(value))))
 692
 693 def getDiagonalFlippedLoop(loop):
 694         'Get loop flipped over the dialogonal, in other words with the x and y swapped.'
 695         diagonalFlippedLoop = []
 696         for point in loop:
 697                 diagonalFlippedLoop.append( complex( point.imag, point.real ) )
 698         return diagonalFlippedLoop
 699
 700 def getDiagonalFlippedLoops(loops):
 701         'Get loops flipped over the dialogonal, in other words with the x and y swapped.'
 702         diagonalFlippedLoops = []
 703         for loop in loops:
 704                 diagonalFlippedLoops.append( getDiagonalFlippedLoop(loop) )
 705         return diagonalFlippedLoops
 706
 707 def getDictionaryString(dictionary):
 708         'Get the dictionary string.'
 709         output = cStringIO.StringIO()
 710         keys = dictionary.keys()
 711         keys.sort()
 712         for key in keys:
 713                 addValueToOutput(0, key, output, dictionary[key])
 714         return output.getvalue()
 715
 716 def getDistanceToLine(begin, end, point):
 717         'Get the distance from a vector3 point to an infinite line.'
 718         pointMinusBegin = point - begin
 719         if begin == end:
 720                 return abs(pointMinusBegin)
 721         endMinusBegin = end - begin
 722         return abs(endMinusBegin.cross(pointMinusBegin)) / abs(endMinusBegin)
 723
 724 def getDistanceToLineByPath(begin, end, path):
 725         'Get the maximum distance from a path to an infinite line.'
 726         distanceToLine = -987654321.0
 727         for point in path:
 728                 distanceToLine = max(getDistanceToLine(begin, end, point), distanceToLine)
 729         return distanceToLine
 730
 731 def getDistanceToLineByPaths(begin, end, paths):
 732         'Get the maximum distance from paths to an infinite line.'
 733         distanceToLine = -987654321.0
 734         for path in paths:
 735                 distanceToLine = max(getDistanceToLineByPath(begin, end, path), distanceToLine)
 736         return distanceToLine
 737
 738 def getDistanceToPlaneSegment( segmentBegin, segmentEnd, point ):
 739         'Get the distance squared from a point to the x & y components of a segment.'
 740         segmentDifference = segmentEnd - segmentBegin
 741         pointMinusSegmentBegin = point - segmentBegin
 742         beginPlaneDot = getDotProduct( pointMinusSegmentBegin, segmentDifference )
 743         if beginPlaneDot <= 0.0:
 744                 return abs( point - segmentBegin ) * abs( point - segmentBegin )
 745         differencePlaneDot = getDotProduct( segmentDifference, segmentDifference )
 746         if differencePlaneDot <= beginPlaneDot:
 747                 return abs( point - segmentEnd ) * abs( point - segmentEnd )
 748         intercept = beginPlaneDot / differencePlaneDot
 749         interceptPerpendicular = segmentBegin + segmentDifference * intercept
 750         return abs( point - interceptPerpendicular ) * abs( point - interceptPerpendicular )
 751
 752 def getDotProduct(firstComplex, secondComplex):
 753         'Get the dot product of a pair of complexes.'
 754         return firstComplex.real * secondComplex.real + firstComplex.imag * secondComplex.imag
 755
 756 def getDotProductPlusOne( firstComplex, secondComplex ):
 757         'Get the dot product plus one of the x and y components of a pair of Vector3s.'
 758         return 1.0 + getDotProduct( firstComplex, secondComplex )
 759
 760 def getDurationString( seconds ):
 761         'Get the duration string.'
 762         secondsRounded = int( round( seconds ) )
 763         durationString = getPluralString( secondsRounded % 60, 'second')
 764         if seconds < 60:
 765                 return durationString
 766         durationString =  '%s %s' % ( getPluralString( ( secondsRounded / 60 ) % 60, 'minute'), durationString )
 767         if seconds < 3600:
 768                 return durationString
 769         return  '%s %s' % ( getPluralString( secondsRounded / 3600, 'hour'), durationString )
 770
 771 def getEndpointFromPath( path, pathIndex ):
 772         'Get endpoint segment from a path.'
 773         begin = path[-1]
 774         end = path[-2]
 775         endpointBegin = Endpoint()
 776         endpointEnd = Endpoint().getFromOtherPoint( endpointBegin, end )
 777         endpointBegin.getFromOtherPoint( endpointEnd, begin )
 778         endpointBegin.path = path
 779         endpointBegin.pathIndex = pathIndex
 780         return endpointBegin
 781
 782 def getEndpointsFromSegments( segments ):
 783         'Get endpoints from segments.'
 784         endpoints = []
 785         for segment in segments:
 786                 for endpoint in segment:
 787                         endpoints.append( endpoint )
 788         return endpoints
 789
 790 def getEndpointsFromSegmentTable( segmentTable ):
 791         'Get the endpoints from the segment table.'
 792         endpoints = []
 793         segmentTableKeys = segmentTable.keys()
 794         segmentTableKeys.sort()
 795         for segmentTableKey in segmentTableKeys:
 796                 for segment in segmentTable[ segmentTableKey ]:
 797                         for endpoint in segment:
 798                                 endpoints.append( endpoint )
 799         return endpoints
 800
 801 def getEnumeratorKeys(enumerator, keys):
 802         'Get enumerator keys.'
 803         if len(keys) == 1:
 804                 return keys[0]
 805         return getEnumeratorKeysExceptForOneArgument(enumerator, keys)
 806
 807 def getEnumeratorKeysAlwaysList(enumerator, keys):
 808         'Get enumerator keys.'
 809         if keys.__class__ != list:
 810                 return [keys]
 811         if len(keys) == 1:
 812                 return keys
 813         return getEnumeratorKeysExceptForOneArgument(enumerator, keys)
 814
 815 def getEnumeratorKeysExceptForOneArgument(enumerator, keys):
 816         'Get enumerator keys, except when there is one argument.'
 817         if len(keys) == 0:
 818                 return range(0, len(enumerator))
 819         beginIndex = keys[0]
 820         endIndex = keys[1]
 821         if len(keys) == 2:
 822                 if beginIndex == None:
 823                         beginIndex = 0
 824                 if endIndex == None:
 825                         endIndex = len(enumerator)
 826                 return range(beginIndex, endIndex)
 827         step = keys[2]
 828         beginIndexDefault = 0
 829         endIndexDefault = len(enumerator)
 830         if step < 0:
 831                 beginIndexDefault = endIndexDefault - 1
 832                 endIndexDefault = -1
 833         if beginIndex == None:
 834                 beginIndex = beginIndexDefault
 835         if endIndex == None:
 836                 endIndex = endIndexDefault
 837         return range(beginIndex, endIndex, step)
 838
 839 def getFillOfSurroundings(nestedRings, penultimateFillLoops):
 840         'Get extra fill loops of nested rings.'
 841         fillOfSurroundings = []
 842         for nestedRing in nestedRings:
 843                 fillOfSurroundings += nestedRing.getFillLoops(penultimateFillLoops)
 844         return fillOfSurroundings
 845
 846 def getFlattenedNestedRings(nestedRings):
 847         'Get flattened nested rings.'
 848         flattenedNestedRings = []
 849         for nestedRing in nestedRings:
 850                 nestedRing.addFlattenedNestedRings(flattenedNestedRings)
 851         return flattenedNestedRings
 852
 853 def getFloatDefaultByDictionary( defaultFloat, dictionary, key ):
 854         'Get the value as a float.'
 855         evaluatedFloat = None
 856         if key in dictionary:
 857                 evaluatedFloat = getFloatFromValue(dictionary[key])
 858         if evaluatedFloat == None:
 859                 return defaultFloat
 860         return evaluatedFloat
 861
 862 def getFloatFromValue(value):
 863         'Get the value as a float.'
 864         try:
 865                 return float(value)
 866         except:
 867                 pass
 868         return None
 869
 870 def getFourSignificantFigures(number):
 871         'Get number rounded to four significant figures as a string.'
 872         if number == None:
 873                 return None
 874         absoluteNumber = abs(number)
 875         if absoluteNumber >= 100.0:
 876                 return getRoundedToPlacesString( 2, number )
 877         if absoluteNumber < 0.000000001:
 878                 return getRoundedToPlacesString( 13, number )
 879         return getRoundedToPlacesString( 3 - math.floor( math.log10( absoluteNumber ) ), number )
 880
 881 def getHalfSimplifiedLoop( loop, radius, remainder ):
 882         'Get the loop with half of the points inside the channel removed.'
 883         if len(loop) < 2:
 884                 return loop
 885         channelRadius = radius * .01
 886         simplified = []
 887         addIndex = 0
 888         if remainder == 1:
 889                 addIndex = len(loop) - 1
 890         for pointIndex in xrange(len(loop)):
 891                 point = loop[pointIndex]
 892                 if pointIndex % 2 == remainder or pointIndex == addIndex:
 893                         simplified.append(point)
 894                 elif not isWithinChannel( channelRadius, pointIndex, loop ):
 895                         simplified.append(point)
 896         return simplified
 897
 898 def getHalfSimplifiedPath(path, radius, remainder):
 899         'Get the path with half of the points inside the channel removed.'
 900         if len(path) < 2:
 901                 return path
 902         channelRadius = radius * .01
 903         simplified = [path[0]]
 904         for pointIndex in xrange(1, len(path) - 1):
 905                 point = path[pointIndex]
 906                 if pointIndex % 2 == remainder:
 907                         simplified.append(point)
 908                 elif not isWithinChannel(channelRadius, pointIndex, path):
 909                         simplified.append(point)
 910         simplified.append(path[-1])
 911         return simplified
 912
 913 def getHorizontallyBoundedPath(horizontalBegin, horizontalEnd, path):
 914         'Get horizontally bounded path.'
 915         horizontallyBoundedPath = []
 916         for pointIndex, point in enumerate(path):
 917                 begin = None
 918                 previousIndex = pointIndex - 1
 919                 if previousIndex >= 0:
 920                         begin = path[previousIndex]
 921                 end = None
 922                 nextIndex = pointIndex + 1
 923                 if nextIndex < len(path):
 924                         end = path[nextIndex]
 925                 addHorizontallyBoundedPoint(begin, point, end, horizontalBegin, horizontalEnd, horizontallyBoundedPath)
 926         return horizontallyBoundedPath
 927
 928 def getIncrementFromRank( rank ):
 929         'Get the increment from the rank which is 0 at 1 and increases by three every power of ten.'
 930         rankZone = int( math.floor( rank / 3 ) )
 931         rankModulo = rank % 3
 932         powerOfTen = pow( 10, rankZone )
 933         moduloMultipliers = ( 1, 2, 5 )
 934         return float( powerOfTen * moduloMultipliers[ rankModulo ] )
 935
 936 def getInsidesAddToOutsides( loops, outsides ):
 937         'Add loops to either the insides or outsides.'
 938         insides = []
 939         for loopIndex in xrange( len(loops) ):
 940                 loop = loops[loopIndex]
 941                 if isInsideOtherLoops( loopIndex, loops ):
 942                         insides.append(loop)
 943                 else:
 944                         outsides.append(loop)
 945         return insides
 946
 947 def getIntermediateLocation( alongWay, begin, end ):
 948         'Get the intermediate location between begin and end.'
 949         return begin * ( 1.0 - alongWay ) + end * alongWay
 950
 951 def getIntersectionOfXIntersectionIndexes( totalSolidSurfaceThickness, xIntersectionIndexList ):
 952         'Get x intersections from surrounding layers.'
 953         xIntersectionList = []
 954         solidTable = {}
 955         solid = False
 956         xIntersectionIndexList.sort()
 957         for xIntersectionIndex in xIntersectionIndexList:
 958                 toggleHashtable(solidTable, xIntersectionIndex.index, '')
 959                 oldSolid = solid
 960                 solid = len(solidTable) >= totalSolidSurfaceThickness
 961                 if oldSolid != solid:
 962                         xIntersectionList.append(xIntersectionIndex.x)
 963         return xIntersectionList
 964
 965 def getIntersectionOfXIntersectionsTables(xIntersectionsTables):
 966         'Get the intersection of the XIntersections tables.'
 967         if len(xIntersectionsTables) == 0:
 968                 return {}
 969         intersectionOfXIntersectionsTables = {}
 970         firstIntersectionTable = xIntersectionsTables[0]
 971         for firstIntersectionTableKey in firstIntersectionTable.keys():
 972                 xIntersectionIndexList = []
 973                 for xIntersectionsTableIndex in xrange(len(xIntersectionsTables)):
 974                         xIntersectionsTable = xIntersectionsTables[xIntersectionsTableIndex]
 975                         if firstIntersectionTableKey in xIntersectionsTable:
 976                                 addXIntersectionIndexesFromXIntersections(xIntersectionsTableIndex, xIntersectionIndexList, xIntersectionsTable[firstIntersectionTableKey])
 977                 xIntersections = getIntersectionOfXIntersectionIndexes(len(xIntersectionsTables), xIntersectionIndexList)
 978                 if len(xIntersections) > 0:
 979                         intersectionOfXIntersectionsTables[firstIntersectionTableKey] = xIntersections
 980         return intersectionOfXIntersectionsTables
 981
 982 def getIntFromValue(value):
 983         'Get the value as an int.'
 984         try:
 985                 return int(value)
 986         except:
 987                 pass
 988         return None
 989
 990 def getIsInFilledRegion(loops, point):
 991         'Determine if the point is in the filled region of the loops.'
 992         return getNumberOfIntersectionsToLeftOfLoops(loops, point) % 2 == 1
 993
 994 def getIsInFilledRegionByPaths(loops, paths):
 995         'Determine if the point of any path is in the filled region of the loops.'
 996         for path in paths:
 997                 if len(path) > 0:
 998                         if getIsInFilledRegion(loops, path[0]):
 999                                 return True
1000         return False
1001
1002 def getIsRadianClose(firstRadian, secondRadian):
1003         'Determine if the firstRadian is close to the secondRadian.'
1004         return abs(math.pi - abs(math.pi - ((firstRadian - secondRadian) % (math.pi + math.pi) ))) < 0.000001
1005
1006 def getIsWiddershinsByVector3( polygon ):
1007         'Determine if the polygon goes round in the widdershins direction.'
1008         return isWiddershins( getComplexPath( polygon ) )
1009
1010 def getJoinOfXIntersectionIndexes( xIntersectionIndexList ):
1011         'Get joined x intersections from surrounding layers.'
1012         xIntersections = []
1013         solidTable = {}
1014         solid = False
1015         xIntersectionIndexList.sort()
1016         for xIntersectionIndex in xIntersectionIndexList:
1017                 toggleHashtable(solidTable, xIntersectionIndex.index, '')
1018                 oldSolid = solid
1019                 solid = len(solidTable) > 0
1020                 if oldSolid != solid:
1021                         xIntersections.append(xIntersectionIndex.x)
1022         return xIntersections
1023
1024 def getLargestLoop(loops):
1025         'Get largest loop from loops.'
1026         largestArea = -987654321.0
1027         largestLoop = []
1028         for loop in loops:
1029                 loopArea = abs(getAreaLoopAbsolute(loop))
1030                 if loopArea > largestArea:
1031                         largestArea = loopArea
1032                         largestLoop = loop
1033         return largestLoop
1034
1035 def getLeftPoint(points):
1036         'Get the leftmost complex point in the points.'
1037         leftmost = 987654321.0
1038         leftPointComplex = None
1039         for pointComplex in points:
1040                 if pointComplex.real < leftmost:
1041                         leftmost = pointComplex.real
1042                         leftPointComplex = pointComplex
1043         return leftPointComplex
1044
1045 def getLeftPointIndex(points):
1046         'Get the index of the leftmost complex point in the points.'
1047         if len(points) < 1:
1048                 return None
1049         leftPointIndex = 0
1050         for pointIndex in xrange( len(points) ):
1051                 if points[pointIndex].real < points[ leftPointIndex ].real:
1052                         leftPointIndex = pointIndex
1053         return leftPointIndex
1054
1055 def getListTableElements( listDictionary ):
1056         'Get all the element in a list table.'
1057         listDictionaryElements = []
1058         for listDictionaryValue in listDictionary.values():
1059                 listDictionaryElements += listDictionaryValue
1060         return listDictionaryElements
1061
1062 def getLoopCentroid(polygonComplex):
1063         'Get the area of a complex polygon using http://en.wikipedia.org/wiki/Centroid.'
1064         polygonDoubleArea = 0.0
1065         polygonTorque = 0.0
1066         for pointIndex in xrange( len(polygonComplex) ):
1067                 pointBegin = polygonComplex[pointIndex]
1068                 pointEnd  = polygonComplex[ (pointIndex + 1) % len(polygonComplex) ]
1069                 doubleArea = pointBegin.real * pointEnd.imag - pointEnd.real * pointBegin.imag
1070                 doubleCenter = complex( pointBegin.real + pointEnd.real, pointBegin.imag + pointEnd.imag )
1071                 polygonDoubleArea += doubleArea
1072                 polygonTorque += doubleArea * doubleCenter
1073         torqueMultiplier = 0.333333333333333333333333 / polygonDoubleArea
1074         return polygonTorque * torqueMultiplier
1075
1076 def getLoopConvex(points):
1077         'Get convex hull of points using gift wrap algorithm.'
1078         loopConvex = []
1079         pointSet = set()
1080         for point in points:
1081                 if point not in pointSet:
1082                         pointSet.add(point)
1083                         loopConvex.append(point)
1084         if len(loopConvex) < 4:
1085                 return loopConvex
1086         leftPoint = getLeftPoint(loopConvex)
1087         lastPoint = leftPoint
1088         pointSet.remove(leftPoint)
1089         loopConvex = [leftPoint]
1090         lastSegment = complex(0.0, 1.0)
1091         while True:
1092                 greatestDotProduct = -9.9
1093                 greatestPoint = None
1094                 greatestSegment = None
1095                 if len(loopConvex) > 2:
1096                         nextSegment = getNormalized(leftPoint - lastPoint)
1097                         if abs(nextSegment) > 0.0:
1098                                 greatestDotProduct = getDotProduct(nextSegment, lastSegment)
1099                 for point in pointSet:
1100                         nextSegment = getNormalized(point - lastPoint)
1101                         if abs(nextSegment) > 0.0:
1102                                 dotProduct = getDotProduct(nextSegment, lastSegment)
1103                                 if dotProduct > greatestDotProduct:
1104                                         greatestDotProduct = dotProduct
1105                                         greatestPoint = point
1106                                         greatestSegment = nextSegment
1107                 if greatestPoint == None:
1108                         return loopConvex
1109                 lastPoint = greatestPoint
1110                 loopConvex.append(greatestPoint)
1111                 pointSet.remove(greatestPoint)
1112                 lastSegment = greatestSegment
1113         return loopConvex
1114
1115 def getLoopConvexCentroid(polygonComplex):
1116         'Get centroid of the convex hull of a complex polygon.'
1117         return getLoopCentroid( getLoopConvex(polygonComplex) )
1118
1119 def getLoopInsideContainingLoop( containingLoop, loops ):
1120         'Get a loop that is inside the containing loop.'
1121         for loop in loops:
1122                 if loop != containingLoop:
1123                         if isPathInsideLoop( containingLoop, loop ):
1124                                 return loop
1125         return None
1126
1127 def getLoopLength( polygon ):
1128         'Get the length of a polygon perimeter.'
1129         polygonLength = 0.0
1130         for pointIndex in xrange( len( polygon ) ):
1131                 point = polygon[pointIndex]
1132                 secondPoint  = polygon[ (pointIndex + 1) % len( polygon ) ]
1133                 polygonLength += abs( point - secondPoint )
1134         return polygonLength
1135
1136 def getLoopStartingClosest(extrusionHalfWidth, location, loop):
1137         'Add to threads from the last location from loop.'
1138         closestIndex = getClosestDistanceIndexToLine(location, loop).index
1139         loop = getAroundLoop(closestIndex, closestIndex, loop)
1140         closestPoint = getClosestPointOnSegment(loop[0], loop[1], location)
1141         if abs(closestPoint - loop[0]) > extrusionHalfWidth and abs(closestPoint - loop[1]) > extrusionHalfWidth:
1142                 loop = [closestPoint] + loop[1 :] + [loop[0]]
1143         elif abs(closestPoint - loop[0]) > abs(closestPoint - loop[1]):
1144                 loop = loop[1 :] + [loop[0]]
1145         return loop
1146
1147 def getLoopWithoutCloseEnds(close, loop):
1148         'Get loop without close ends.'
1149         if len(loop) < 2:
1150                 return loop
1151         if abs(loop[0] - loop[-1]) > close:
1152                 return loop
1153         return loop[: -1]
1154
1155 def getLoopWithoutCloseSequentialPoints(close, loop):
1156         'Get loop without close sequential points.'
1157         if len(loop) < 2:
1158                 return loop
1159         lastPoint = loop[-1]
1160         loopWithoutCloseSequentialPoints = []
1161         for point in loop:
1162                 if abs(point - lastPoint) > close:
1163                         loopWithoutCloseSequentialPoints.append(point)
1164                 lastPoint = point
1165         return loopWithoutCloseSequentialPoints
1166
1167 def getMaximum(firstComplex, secondComplex):
1168         'Get a complex with each component the maximum of the respective components of a pair of complexes.'
1169         return complex(max(firstComplex.real, secondComplex.real), max(firstComplex.imag, secondComplex.imag))
1170
1171 def getMaximumByComplexPath(path):
1172         'Get a complex with each component the maximum of the respective components of a complex path.'
1173         maximum = complex(-987654321987654321.0, -987654321987654321.0)
1174         for point in path:
1175                 maximum = getMaximum(maximum, point)
1176         return maximum
1177
1178 def getMaximumByComplexPaths(paths):
1179         'Get a complex with each component the maximum of the respective components of complex paths.'
1180         maximum = complex(-987654321987654321.0, -987654321987654321.0)
1181         for path in paths:
1182                 for point in path:
1183                         maximum = getMaximum(maximum, point)
1184         return maximum
1185
1186 def getMaximumByVector3Path(path):
1187         'Get a vector3 with each component the maximum of the respective components of a vector3 path.'
1188         maximum = Vector3(-987654321987654321.0, -987654321987654321.0, -987654321987654321.0)
1189         for point in path:
1190                 maximum.maximize(point)
1191         return maximum
1192
1193 def getMaximumByVector3Paths(paths):
1194         'Get a complex with each component the maximum of the respective components of a complex path.'
1195         maximum = Vector3(-987654321987654321.0, -987654231987654321.0, -987654321987654321.0)
1196         for path in paths:
1197                 for point in path:
1198                         maximum.maximize(point)
1199         return maximum
1200
1201 def getMaximumSpan(loop):
1202         'Get the maximum span of the loop.'
1203         extent = getMaximumByComplexPath(loop) - getMinimumByComplexPath(loop)
1204         return max(extent.real, extent.imag)
1205
1206 def getMinimum(firstComplex, secondComplex):
1207         'Get a complex with each component the minimum of the respective components of a pair of complexes.'
1208         return complex(min(firstComplex.real, secondComplex.real), min(firstComplex.imag, secondComplex.imag))
1209
1210 def getMinimumByComplexPath(path):
1211         'Get a complex with each component the minimum of the respective components of a complex path.'
1212         minimum = complex(987654321987654321.0, 987654321987654321.0)
1213         for point in path:
1214                 minimum = getMinimum(minimum, point)
1215         return minimum
1216
1217 def getMinimumByComplexPaths(paths):
1218         'Get a complex with each component the minimum of the respective components of complex paths.'
1219         minimum = complex(987654321987654321.0, 987654321987654321.0)
1220         for path in paths:
1221                 for point in path:
1222                         minimum = getMinimum(minimum, point)
1223         return minimum
1224
1225 def getMinimumByVector3Path(path):
1226         'Get a vector3 with each component the minimum of the respective components of a vector3 path.'
1227         minimum = Vector3(987654321987654321.0, 987654321987654321.0, 987654321987654321.0)
1228         for point in path:
1229                 minimum.minimize(point)
1230         return minimum
1231
1232 def getMinimumByVector3Paths(paths):
1233         'Get a complex with each component the minimum of the respective components of a complex path.'
1234         minimum = Vector3(987654321987654321.0, 987654321987654321.0, 987654321987654321.0)
1235         for path in paths:
1236                 for point in path:
1237                         minimum.minimize(point)
1238         return minimum
1239
1240 def getMirrorPath(path):
1241         "Get mirror path."
1242         close = 0.001 * getPathLength(path)
1243         for pointIndex in xrange(len(path) - 1, -1, -1):
1244                 point = path[pointIndex]
1245                 flipPoint = complex(-point.real, point.imag)
1246                 if abs(flipPoint - path[-1]) > close:
1247                         path.append(flipPoint)
1248         return path
1249
1250 def getNormal(begin, center, end):
1251         'Get normal.'
1252         centerMinusBegin = (center - begin).getNormalized()
1253         endMinusCenter = (end - center).getNormalized()
1254         return centerMinusBegin.cross(endMinusCenter)
1255
1256 def getNormalByPath(path):
1257         'Get normal by path.'
1258         totalNormal = Vector3()
1259         for pointIndex, point in enumerate(path):
1260                 center = path[(pointIndex + 1) % len(path)]
1261                 end = path[(pointIndex + 2) % len(path)]
1262                 totalNormal += getNormalWeighted(point, center, end)
1263         return totalNormal.getNormalized()
1264
1265 def getNormalized(complexNumber):
1266         'Get the normalized complex.'
1267         complexNumberLength = abs(complexNumber)
1268         if complexNumberLength > 0.0:
1269                 return complexNumber / complexNumberLength
1270         return complexNumber
1271
1272 def getNormalWeighted(begin, center, end):
1273         'Get weighted normal.'
1274         return (center - begin).cross(end - center)
1275
1276 def getNumberOfIntersectionsToLeft(loop, point):
1277         'Get the number of intersections through the loop for the line going left.'
1278         numberOfIntersectionsToLeft = 0
1279         for pointIndex in xrange(len(loop)):
1280                 firstPointComplex = loop[pointIndex]
1281                 secondPointComplex = loop[(pointIndex + 1) % len(loop)]
1282                 xIntersection = getXIntersectionIfExists(firstPointComplex, secondPointComplex, point.imag)
1283                 if xIntersection != None:
1284                         if xIntersection < point.real:
1285                                 numberOfIntersectionsToLeft += 1
1286         return numberOfIntersectionsToLeft
1287
1288 def getNumberOfIntersectionsToLeftOfLoops(loops, point):
1289         'Get the number of intersections through the loop for the line starting from the left point and going left.'
1290         totalNumberOfIntersectionsToLeft = 0
1291         for loop in loops:
1292                 totalNumberOfIntersectionsToLeft += getNumberOfIntersectionsToLeft(loop, point)
1293         return totalNumberOfIntersectionsToLeft
1294
1295 def getOrderedNestedRings(nestedRings):
1296         'Get ordered nestedRings from nestedRings.'
1297         insides = []
1298         orderedNestedRings = []
1299         for loopIndex in xrange(len(nestedRings)):
1300                 nestedRing = nestedRings[loopIndex]
1301                 otherLoops = []
1302                 for beforeIndex in xrange(loopIndex):
1303                         otherLoops.append(nestedRings[beforeIndex].boundary)
1304                 for afterIndex in xrange(loopIndex + 1, len(nestedRings)):
1305                         otherLoops.append(nestedRings[afterIndex].boundary)
1306                 if isPathEntirelyInsideLoops(otherLoops, nestedRing.boundary):
1307                         insides.append(nestedRing)
1308                 else:
1309                         orderedNestedRings.append(nestedRing)
1310         for outside in orderedNestedRings:
1311                 outside.getFromInsideSurroundings(insides)
1312         return orderedNestedRings
1313
1314 def getPathCopy(path):
1315         'Get path copy.'
1316         pathCopy = []
1317         for point in path:
1318                 pathCopy.append(point.copy())
1319         return pathCopy
1320
1321 def getPathLength(path):
1322         'Get the length of a path ( an open polyline ).'
1323         pathLength = 0.0
1324         for pointIndex in xrange( len(path) - 1 ):
1325                 firstPoint = path[pointIndex]
1326                 secondPoint  = path[pointIndex + 1]
1327                 pathLength += abs(firstPoint - secondPoint)
1328         return pathLength
1329
1330 def getPathsFromEndpoints(endpoints, maximumConnectionLength, pixelDictionary, sharpestProduct, width):
1331         'Get paths from endpoints.'
1332         if len(endpoints) < 2:
1333                 return []
1334         endpoints = endpoints[:] # so that the first two endpoints aren't removed when used again
1335         for beginningEndpoint in endpoints[: : 2]:
1336                 beginningPoint = beginningEndpoint.point
1337                 addSegmentToPixelTable(beginningPoint, beginningEndpoint.otherEndpoint.point, pixelDictionary, 0, 0, width)
1338         endpointFirst = endpoints[0]
1339         endpoints.remove(endpointFirst)
1340         otherEndpoint = endpointFirst.otherEndpoint
1341         endpoints.remove(otherEndpoint)
1342         nextEndpoint = None
1343         path = []
1344         paths = [path]
1345         if len(endpoints) > 1:
1346                 nextEndpoint = otherEndpoint.getClosestMiss(endpoints, path, pixelDictionary, sharpestProduct, width)
1347                 if nextEndpoint != None:
1348                         if abs(nextEndpoint.point - endpointFirst.point) < abs(nextEndpoint.point - otherEndpoint.point):
1349                                 endpointFirst = endpointFirst.otherEndpoint
1350                                 otherEndpoint = endpointFirst.otherEndpoint
1351         addPointToPath(path, pixelDictionary, endpointFirst.point, None, width)
1352         addPointToPath(path, pixelDictionary, otherEndpoint.point, len(paths) - 1, width)
1353         oneOverEndpointWidth = 1.0 / maximumConnectionLength
1354         endpointTable = {}
1355         for endpoint in endpoints:
1356                 addElementToPixelListFromPoint(endpoint, endpointTable, endpoint.point * oneOverEndpointWidth)
1357         while len(endpointTable) > 0:
1358                 if len(endpointTable) == 1:
1359                         if len(endpointTable.values()[0]) < 2:
1360                                 return []
1361                 endpoints = getSquareValuesFromPoint(endpointTable, otherEndpoint.point * oneOverEndpointWidth)
1362                 nextEndpoint = otherEndpoint.getClosestMiss(endpoints, path, pixelDictionary, sharpestProduct, width)
1363                 if nextEndpoint == None:
1364                         path = []
1365                         paths.append(path)
1366                         endpoints = getListTableElements(endpointTable)
1367                         nextEndpoint = otherEndpoint.getClosestEndpoint(endpoints)
1368 # this commented code should be faster than the getListTableElements code, but it isn't, someday a spiral algorithim could be tried
1369 #                       endpoints = getSquareValuesFromPoint( endpointTable, otherEndpoint.point * oneOverEndpointWidth )
1370 #                       nextEndpoint = otherEndpoint.getClosestEndpoint(endpoints)
1371 #                       if nextEndpoint == None:
1372 #                               endpoints = []
1373 #                               for endpointTableValue in endpointTable.values():
1374 #                                       endpoints.append( endpointTableValue[0] )
1375 #                               nextEndpoint = otherEndpoint.getClosestEndpoint(endpoints)
1376 #                               endpoints = getSquareValuesFromPoint( endpointTable, nextEndpoint.point * oneOverEndpointWidth )
1377 #                               nextEndpoint = otherEndpoint.getClosestEndpoint(endpoints)
1378                 addPointToPath(path, pixelDictionary, nextEndpoint.point, len(paths) - 1, width)
1379                 removeElementFromPixelListFromPoint(nextEndpoint, endpointTable, nextEndpoint.point * oneOverEndpointWidth)
1380                 otherEndpoint = nextEndpoint.otherEndpoint
1381                 addPointToPath(path, pixelDictionary, otherEndpoint.point, len(paths) - 1, width)
1382                 removeElementFromPixelListFromPoint(otherEndpoint, endpointTable, otherEndpoint.point * oneOverEndpointWidth)
1383         return paths
1384
1385 def getPlaneDot( vec3First, vec3Second ):
1386         'Get the dot product of the x and y components of a pair of Vector3s.'
1387         return vec3First.x * vec3Second.x + vec3First.y * vec3Second.y
1388
1389 def getPluralString( number, suffix ):
1390         'Get the plural string.'
1391         if number == 1:
1392                 return '1 %s' % suffix
1393         return '%s %ss' % ( number, suffix )
1394
1395 def getPointPlusSegmentWithLength( length, point, segment ):
1396         'Get point plus a segment scaled to a given length.'
1397         return segment * length / abs(segment) + point
1398
1399 def getPointsByHorizontalDictionary(width, xIntersectionsDictionary):
1400         'Get points from the horizontalXIntersectionsDictionary.'
1401         points = []
1402         xIntersectionsDictionaryKeys = xIntersectionsDictionary.keys()
1403         xIntersectionsDictionaryKeys.sort()
1404         for xIntersectionsDictionaryKey in xIntersectionsDictionaryKeys:
1405                 for xIntersection in xIntersectionsDictionary[xIntersectionsDictionaryKey]:
1406                         points.append(complex(xIntersection, xIntersectionsDictionaryKey * width))
1407         return points
1408
1409 def getPointsByVerticalDictionary(width, xIntersectionsDictionary):
1410         'Get points from the verticalXIntersectionsDictionary.'
1411         points = []
1412         xIntersectionsDictionaryKeys = xIntersectionsDictionary.keys()
1413         xIntersectionsDictionaryKeys.sort()
1414         for xIntersectionsDictionaryKey in xIntersectionsDictionaryKeys:
1415                 for xIntersection in xIntersectionsDictionary[xIntersectionsDictionaryKey]:
1416                         points.append(complex(xIntersectionsDictionaryKey * width, xIntersection))
1417         return points
1418
1419 def getRadiusArealizedMultiplier(sides):
1420         'Get the radius multiplier for a polygon of equal area.'
1421         return math.sqrt(globalTau / sides / math.sin(globalTau / sides))
1422
1423 def getRandomComplex(begin, end):
1424         'Get random complex.'
1425         endMinusBegin = end - begin
1426         return begin + complex(random.random() * endMinusBegin.real, random.random() * endMinusBegin.imag)
1427
1428 def getRank(width):
1429         'Get the rank which is 0 at 1 and increases by three every power of ten.'
1430         return int(math.floor(3.0 * math.log10(width)))
1431
1432 def getRotatedComplexes(planeAngle, points):
1433         'Get points rotated by the plane angle'
1434         rotatedComplexes = []
1435         for point in points:
1436                 rotatedComplexes.append(planeAngle * point)
1437         return rotatedComplexes
1438
1439 def getRotatedComplexLists(planeAngle, pointLists):
1440         'Get point lists rotated by the plane angle'
1441         rotatedComplexLists = []
1442         for pointList in pointLists:
1443                 rotatedComplexLists.append(getRotatedComplexes(planeAngle, pointList))
1444         return rotatedComplexLists
1445
1446 def getRotatedWiddershinsQuarterAroundZAxis(vector3):
1447         'Get Vector3 rotated a quarter widdershins turn around Z axis.'
1448         return Vector3(-vector3.y, vector3.x, vector3.z)
1449
1450 def getRoundedPoint(point):
1451         'Get point with each component rounded.'
1452         return Vector3(round(point.x), round( point.y ), round(point.z))
1453
1454 def getRoundedToPlaces(decimalPlaces, number):
1455         'Get number rounded to a number of decimal places.'
1456         decimalPlacesRounded = max(1, int(round(decimalPlaces)))
1457         return round(number, decimalPlacesRounded)
1458
1459 def getRoundedToPlacesString(decimalPlaces, number):
1460         'Get number rounded to a number of decimal places as a string, without exponential formatting.'
1461         roundedToPlaces = getRoundedToPlaces(decimalPlaces, number)
1462         roundedToPlacesString = str(roundedToPlaces)
1463         if 'e' in roundedToPlacesString:
1464                 return ('%.15f' % roundedToPlaces).rstrip('0')
1465         return roundedToPlacesString
1466
1467 def getRoundedToThreePlaces(number):
1468         'Get number rounded to three places as a string.'
1469         return str(round(number, 3))
1470
1471 def getRoundZAxisByPlaneAngle( planeAngle, vector3 ):
1472         'Get Vector3 rotated by a plane angle.'
1473         return Vector3( vector3.x * planeAngle.real - vector3.y * planeAngle.imag, vector3.x * planeAngle.imag + vector3.y * planeAngle.real, vector3.z )
1474
1475 def getSegmentFromPath( path, pathIndex ):
1476         'Get endpoint segment from a path.'
1477         if len(path) < 2:
1478                 return None
1479         begin = path[-1]
1480         end = path[-2]
1481         forwardEndpoint = getEndpointFromPath( path, pathIndex )
1482         reversePath = path[:]
1483         reversePath.reverse()
1484         reverseEndpoint = getEndpointFromPath( reversePath, pathIndex )
1485         return ( forwardEndpoint, reverseEndpoint )
1486
1487 def getSegmentFromPoints( begin, end ):
1488         'Get endpoint segment from a pair of points.'
1489         endpointFirst = Endpoint()
1490         endpointSecond = Endpoint().getFromOtherPoint( endpointFirst, end )
1491         endpointFirst.getFromOtherPoint( endpointSecond, begin )
1492         return ( endpointFirst, endpointSecond )
1493
1494 def getSegmentsFromXIntersectionIndexes( xIntersectionIndexList, y ):
1495         'Get endpoint segments from the x intersection indexes.'
1496         xIntersections = getXIntersectionsFromIntersections( xIntersectionIndexList )
1497         return getSegmentsFromXIntersections( xIntersections, y )
1498
1499 def getSegmentsFromXIntersections( xIntersections, y ):
1500         'Get endpoint segments from the x intersections.'
1501         segments = []
1502         end = len( xIntersections )
1503         if len( xIntersections ) % 2 == 1:
1504                 end -= 1
1505         for xIntersectionIndex in xrange( 0, end, 2 ):
1506                 firstX = xIntersections[ xIntersectionIndex ]
1507                 secondX = xIntersections[ xIntersectionIndex + 1 ]
1508                 if firstX != secondX:
1509                         segments.append( getSegmentFromPoints( complex( firstX, y ), complex( secondX, y ) ) )
1510         return segments
1511
1512 def getSimplifiedLoop( loop, radius ):
1513         'Get loop with points inside the channel removed.'
1514         if len(loop) < 2:
1515                 return loop
1516         simplificationMultiplication = 256
1517         simplificationRadius = radius / float( simplificationMultiplication )
1518         maximumIndex = len(loop) * simplificationMultiplication
1519         pointIndex = 1
1520         while pointIndex < maximumIndex:
1521                 oldLoopLength = len(loop)
1522                 loop = getHalfSimplifiedLoop( loop, simplificationRadius, 0 )
1523                 loop = getHalfSimplifiedLoop( loop, simplificationRadius, 1 )
1524                 simplificationRadius += simplificationRadius
1525                 if oldLoopLength == len(loop):
1526                         if simplificationRadius > radius:
1527                                 return getAwayPoints( loop, radius )
1528                         else:
1529                                 simplificationRadius *= 1.5
1530                 simplificationRadius = min( simplificationRadius, radius )
1531                 pointIndex += pointIndex
1532         return getAwayPoints( loop, radius )
1533
1534 def getSimplifiedLoops( loops, radius ):
1535         'Get the simplified loops.'
1536         simplifiedLoops = []
1537         for loop in loops:
1538                 simplifiedLoops.append( getSimplifiedLoop( loop, radius ) )
1539         return simplifiedLoops
1540
1541 def getSimplifiedPath(path, radius):
1542         'Get path with points inside the channel removed.'
1543         if len(path) < 2:
1544                 return path
1545         simplificationMultiplication = 256
1546         simplificationRadius = radius / float(simplificationMultiplication)
1547         maximumIndex = len(path) * simplificationMultiplication
1548         pointIndex = 1
1549         while pointIndex < maximumIndex:
1550                 oldPathLength = len(path)
1551                 path = getHalfSimplifiedPath(path, simplificationRadius, 0)
1552                 path = getHalfSimplifiedPath(path, simplificationRadius, 1)
1553                 simplificationRadius += simplificationRadius
1554                 if oldPathLength == len(path):
1555                         if simplificationRadius > radius:
1556                                 return getAwayPath(path, radius)
1557                         else:
1558                                 simplificationRadius *= 1.5
1559                 simplificationRadius = min(simplificationRadius, radius)
1560                 pointIndex += pointIndex
1561         return getAwayPath(path, radius)
1562
1563 def getSquareIsOccupied( pixelDictionary, x, y ):
1564         'Determine if a square around the x and y pixel coordinates is occupied.'
1565         squareValues = []
1566         for xStep in xrange(x - 1, x + 2):
1567                 for yStep in xrange(y - 1, y + 2):
1568                         if (xStep, yStep) in pixelDictionary:
1569                                 return True
1570         return False
1571
1572 def getSquareLoopWiddershins(beginComplex, endComplex):
1573         'Get a square loop from the beginning to the end and back.'
1574         loop = [beginComplex, complex(endComplex.real, beginComplex.imag), endComplex]
1575         loop.append(complex(beginComplex.real, endComplex.imag))
1576         return loop
1577
1578 def getSquareValues( pixelDictionary, x, y ):
1579         'Get a list of the values in a square around the x and y pixel coordinates.'
1580         squareValues = []
1581         for xStep in xrange(x - 1, x + 2):
1582                 for yStep in xrange(y - 1, y + 2):
1583                         stepKey = (xStep, yStep)
1584                         if stepKey in pixelDictionary:
1585                                 squareValues += pixelDictionary[ stepKey ]
1586         return squareValues
1587
1588 def getSquareValuesFromPoint( pixelDictionary, point ):
1589         'Get a list of the values in a square around the point.'
1590         return getSquareValues(pixelDictionary, int(round(point.real)), int(round(point.imag)))
1591
1592 def getStepKeyFromPoint(point):
1593         'Get step key for the point.'
1594         return (int(round(point.real)), int(round(point.imag)))
1595
1596 def getThreeSignificantFigures(number):
1597         'Get number rounded to three significant figures as a string.'
1598         absoluteNumber = abs(number)
1599         if absoluteNumber >= 10.0:
1600                 return getRoundedToPlacesString( 1, number )
1601         if absoluteNumber < 0.000000001:
1602                 return getRoundedToPlacesString( 12, number )
1603         return getRoundedToPlacesString( 1 - math.floor( math.log10( absoluteNumber ) ), number )
1604
1605 def getTopPath(path):
1606         'Get the top of the path.'
1607         top = -987654321987654321.0
1608         for point in path:
1609                 top = max(top, point.z)
1610         return top
1611
1612 def getTopPaths(paths):
1613         'Get the top of the paths.'
1614         top = -987654321987654321.0
1615         for path in paths:
1616                 for point in path:
1617                         top = max(top, point.z)
1618         return top
1619
1620 def getTransferClosestNestedRing(extrusionHalfWidth, nestedRings, oldOrderedLocation, skein, threadSequence):
1621         'Get and transfer the closest remaining nested ring.'
1622         if len(nestedRings) > 0:
1623                 oldOrderedLocation.z = nestedRings[0].z
1624         closestDistance = 987654321987654321.0
1625         closestNestedRing = None
1626         for remainingNestedRing in nestedRings:
1627                 distance = getClosestDistanceIndexToLine(oldOrderedLocation.dropAxis(), remainingNestedRing.boundary).distance
1628                 if distance < closestDistance:
1629                         closestDistance = distance
1630                         closestNestedRing = remainingNestedRing
1631         nestedRings.remove(closestNestedRing)
1632         closestNestedRing.addToThreads(extrusionHalfWidth, oldOrderedLocation, skein, threadSequence)
1633         return closestNestedRing
1634
1635 def getTransferredNestedRings( insides, loop ):
1636         'Get transferred paths from inside nested rings.'
1637         transferredSurroundings = []
1638         for insideIndex in xrange( len( insides ) - 1, - 1, - 1 ):
1639                 insideSurrounding = insides[ insideIndex ]
1640                 if isPathInsideLoop( loop, insideSurrounding.boundary ):
1641                         transferredSurroundings.append( insideSurrounding )
1642                         del insides[ insideIndex ]
1643         return transferredSurroundings
1644
1645 def getTransferredPaths( insides, loop ):
1646         'Get transferred paths from inside paths.'
1647         transferredPaths = []
1648         for insideIndex in xrange( len( insides ) - 1, - 1, - 1 ):
1649                 inside = insides[ insideIndex ]
1650                 if isPathInsideLoop( loop, inside ):
1651                         transferredPaths.append( inside )
1652                         del insides[ insideIndex ]
1653         return transferredPaths
1654
1655 def getTranslatedComplexPath(path, translateComplex):
1656         'Get the translated complex path.'
1657         translatedComplexPath = []
1658         for point in path:
1659                 translatedComplexPath.append(point + translateComplex)
1660         return translatedComplexPath
1661
1662 def getVector3Path(complexPath, z=0.0):
1663         'Get the vector3 path from the complex path.'
1664         vector3Path = []
1665         for complexPoint in complexPath:
1666                 vector3Path.append(Vector3(complexPoint.real, complexPoint.imag, z))
1667         return vector3Path
1668
1669 def getVector3Paths(complexPaths, z=0.0):
1670         'Get the vector3 paths from the complex paths.'
1671         vector3Paths = []
1672         for complexPath in complexPaths:
1673                 vector3Paths.append(getVector3Path(complexPath, z))
1674         return vector3Paths
1675
1676 def getWiddershinsUnitPolar(angle):
1677         'Get polar complex from counterclockwise angle from 1, 0.'
1678         return complex(math.cos(angle), math.sin(angle))
1679
1680 def getXIntersectionIfExists( beginComplex, endComplex, y ):
1681         'Get the x intersection if it exists.'
1682         if ( y > beginComplex.imag ) == ( y > endComplex.imag ):
1683                 return None
1684         endMinusBeginComplex = endComplex - beginComplex
1685         return ( y - beginComplex.imag ) / endMinusBeginComplex.imag * endMinusBeginComplex.real + beginComplex.real
1686
1687 def getXIntersectionsFromIntersections( xIntersectionIndexList ):
1688         'Get x intersections from the x intersection index list, in other words subtract non negative intersections from negatives.'
1689         xIntersections = []
1690         fill = False
1691         solid = False
1692         solidTable = {}
1693         xIntersectionIndexList.sort()
1694         for solidX in xIntersectionIndexList:
1695                 if solidX.index >= 0:
1696                         toggleHashtable( solidTable, solidX.index, '' )
1697                 else:
1698                         fill = not fill
1699                 oldSolid = solid
1700                 solid = ( len( solidTable ) == 0 and fill )
1701                 if oldSolid != solid:
1702                         xIntersections.append( solidX.x )
1703         return xIntersections
1704
1705 def getXYComplexFromVector3(vector3):
1706         'Get an xy complex from a vector3 if it exists, otherwise return None.'
1707         if vector3 == None:
1708                 return None
1709         return vector3.dropAxis()
1710
1711 def getYIntersectionIfExists( beginComplex, endComplex, x ):
1712         'Get the y intersection if it exists.'
1713         if ( x > beginComplex.real ) == ( x > endComplex.real ):
1714                 return None
1715         endMinusBeginComplex = endComplex - beginComplex
1716         return ( x - beginComplex.real ) / endMinusBeginComplex.real * endMinusBeginComplex.imag + beginComplex.imag
1717
1718 def getZComponentCrossProduct( vec3First, vec3Second ):
1719         'Get z component cross product of a pair of Vector3s.'
1720         return vec3First.x * vec3Second.y - vec3First.y * vec3Second.x
1721
1722 def isInsideOtherLoops( loopIndex, loops ):
1723         'Determine if a loop in a list is inside another loop in that list.'
1724         return isPathInsideLoops( loops[ : loopIndex ] + loops[loopIndex + 1 :], loops[loopIndex] )
1725
1726 def isLineIntersectingInsideXSegment( beginComplex, endComplex, segmentFirstX, segmentSecondX, y ):
1727         'Determine if the line is crossing inside the x segment.'
1728         xIntersection = getXIntersectionIfExists( beginComplex, endComplex, y )
1729         if xIntersection == None:
1730                 return False
1731         if xIntersection < min( segmentFirstX, segmentSecondX ):
1732                 return False
1733         return xIntersection <= max( segmentFirstX, segmentSecondX )
1734
1735 def isLineIntersectingLoop( loop, pointBegin, pointEnd ):
1736         'Determine if the line is intersecting loops.'
1737         normalizedSegment = pointEnd - pointBegin
1738         normalizedSegmentLength = abs( normalizedSegment )
1739         if normalizedSegmentLength > 0.0:
1740                 normalizedSegment /= normalizedSegmentLength
1741                 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
1742                 pointBeginRotated = segmentYMirror * pointBegin
1743                 pointEndRotated = segmentYMirror * pointEnd
1744                 if isLoopIntersectingInsideXSegment( loop, pointBeginRotated.real, pointEndRotated.real, segmentYMirror, pointBeginRotated.imag ):
1745                         return True
1746         return False
1747
1748 def isLineIntersectingLoops( loops, pointBegin, pointEnd ):
1749         'Determine if the line is intersecting loops.'
1750         normalizedSegment = pointEnd - pointBegin
1751         normalizedSegmentLength = abs( normalizedSegment )
1752         if normalizedSegmentLength > 0.0:
1753                 normalizedSegment /= normalizedSegmentLength
1754                 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
1755                 pointBeginRotated = segmentYMirror * pointBegin
1756                 pointEndRotated = segmentYMirror * pointEnd
1757                 if isLoopListIntersectingInsideXSegment( loops, pointBeginRotated.real, pointEndRotated.real, segmentYMirror, pointBeginRotated.imag ):
1758                         return True
1759         return False
1760
1761 def isLoopIntersectingInsideXSegment( loop, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1762         'Determine if the loop is intersecting inside the x segment.'
1763         rotatedLoop = getRotatedComplexes( segmentYMirror, loop )
1764         for pointIndex in xrange( len( rotatedLoop ) ):
1765                 pointFirst = rotatedLoop[pointIndex]
1766                 pointSecond = rotatedLoop[ (pointIndex + 1) % len( rotatedLoop ) ]
1767                 if isLineIntersectingInsideXSegment( pointFirst, pointSecond, segmentFirstX, segmentSecondX, y ):
1768                         return True
1769         return False
1770
1771 def isLoopIntersectingLoop( loop, otherLoop ):
1772         'Determine if the loop is intersecting the other loop.'
1773         for pointIndex in xrange(len(loop)):
1774                 pointBegin = loop[pointIndex]
1775                 pointEnd = loop[(pointIndex + 1) % len(loop)]
1776                 if isLineIntersectingLoop( otherLoop, pointBegin, pointEnd ):
1777                         return True
1778         return False
1779
1780 def isLoopIntersectingLoops( loop, otherLoops ):
1781         'Determine if the loop is intersecting other loops.'
1782         for pointIndex in xrange(len(loop)):
1783                 pointBegin = loop[pointIndex]
1784                 pointEnd = loop[(pointIndex + 1) % len(loop)]
1785                 if isLineIntersectingLoops( otherLoops, pointBegin, pointEnd ):
1786                         return True
1787         return False
1788
1789 def isLoopListIntersecting(loops):
1790         'Determine if a loop in the list is intersecting the other loops.'
1791         for loopIndex in xrange(len(loops) - 1):
1792                 loop = loops[loopIndex]
1793                 if isLoopIntersectingLoops(loop, loops[loopIndex + 1 :]):
1794                         return True
1795         return False
1796
1797 def isLoopListIntersectingInsideXSegment( loopList, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1798         'Determine if the loop list is crossing inside the x segment.'
1799         for alreadyFilledLoop in loopList:
1800                 if isLoopIntersectingInsideXSegment( alreadyFilledLoop, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1801                         return True
1802         return False
1803
1804 def isPathEntirelyInsideLoop(loop, path):
1805         'Determine if a path is entirely inside another loop.'
1806         for point in path:
1807                 if not isPointInsideLoop(loop, point):
1808                         return False
1809         return True
1810
1811 def isPathEntirelyInsideLoops(loops, path):
1812         'Determine if a path is entirely inside another loop in a list.'
1813         for loop in loops:
1814                 if isPathEntirelyInsideLoop(loop, path):
1815                         return True
1816         return False
1817
1818 def isPathInsideLoop(loop, path):
1819         'Determine if a path is inside another loop.'
1820         return isPointInsideLoop(loop, getLeftPoint(path))
1821
1822 def isPathInsideLoops(loops, path):
1823         'Determine if a path is inside another loop in a list.'
1824         for loop in loops:
1825                 if isPathInsideLoop(loop, path):
1826                         return True
1827         return False
1828
1829 def isPixelTableIntersecting( bigTable, littleTable, maskTable = {} ):
1830         'Add path to the pixel table.'
1831         littleTableKeys = littleTable.keys()
1832         for littleTableKey in littleTableKeys:
1833                 if littleTableKey not in maskTable:
1834                         if littleTableKey in bigTable:
1835                                 return True
1836         return False
1837
1838 def isPointInsideLoop(loop, point):
1839         'Determine if a point is inside another loop.'
1840         return getNumberOfIntersectionsToLeft(loop, point) % 2 == 1
1841
1842 def isSegmentCompletelyInX( segment, xFirst, xSecond ):
1843         'Determine if the segment overlaps within x.'
1844         segmentFirstX = segment[0].point.real
1845         segmentSecondX = segment[1].point.real
1846         if max( segmentFirstX, segmentSecondX ) > max( xFirst, xSecond ):
1847                 return False
1848         return min( segmentFirstX, segmentSecondX ) >= min( xFirst, xSecond )
1849
1850 def isWiddershins(polygonComplex):
1851         'Determine if the complex polygon goes round in the widdershins direction.'
1852         return getAreaLoop(polygonComplex) > 0.0
1853
1854 def isWithinChannel( channelRadius, pointIndex, loop ):
1855         'Determine if the the point is within the channel between two adjacent points.'
1856         point = loop[pointIndex]
1857         behindSegmentComplex = loop[(pointIndex + len(loop) - 1) % len(loop)] - point
1858         behindSegmentComplexLength = abs( behindSegmentComplex )
1859         if behindSegmentComplexLength < channelRadius:
1860                 return True
1861         aheadSegmentComplex = loop[(pointIndex + 1) % len(loop)] - point
1862         aheadSegmentComplexLength = abs( aheadSegmentComplex )
1863         if aheadSegmentComplexLength < channelRadius:
1864                 return True
1865         behindSegmentComplex /= behindSegmentComplexLength
1866         aheadSegmentComplex /= aheadSegmentComplexLength
1867         absoluteZ = getDotProductPlusOne( aheadSegmentComplex, behindSegmentComplex )
1868         if behindSegmentComplexLength * absoluteZ < channelRadius:
1869                 return True
1870         return aheadSegmentComplexLength * absoluteZ < channelRadius
1871
1872 def isXSegmentIntersectingPath( path, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1873         'Determine if a path is crossing inside the x segment.'
1874         rotatedPath = getRotatedComplexes( segmentYMirror, path )
1875         for pointIndex in xrange( len( rotatedPath ) - 1 ):
1876                 pointFirst = rotatedPath[pointIndex]
1877                 pointSecond = rotatedPath[pointIndex + 1]
1878                 if isLineIntersectingInsideXSegment( pointFirst, pointSecond, segmentFirstX, segmentSecondX, y ):
1879                         return True
1880         return False
1881
1882 def isXSegmentIntersectingPaths( paths, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1883         'Determine if a path list is crossing inside the x segment.'
1884         for path in paths:
1885                 if isXSegmentIntersectingPath( path, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1886                         return True
1887         return False
1888
1889 def joinSegmentTables( fromTable, intoTable ):
1890         'Join both segment tables and put the join into the intoTable.'
1891         intoTableKeys = intoTable.keys()
1892         fromTableKeys = fromTable.keys()
1893         joinedKeyTable = {}
1894         concatenatedTableKeys = intoTableKeys + fromTableKeys
1895         for concatenatedTableKey in concatenatedTableKeys:
1896                 joinedKeyTable[ concatenatedTableKey ] = None
1897         joinedKeys = joinedKeyTable.keys()
1898         joinedKeys.sort()
1899         for joinedKey in joinedKeys:
1900                 xIntersectionIndexList = []
1901                 if joinedKey in intoTable:
1902                         addXIntersectionIndexesFromSegments( 0, intoTable[ joinedKey ], xIntersectionIndexList )
1903                 if joinedKey in fromTable:
1904                         addXIntersectionIndexesFromSegments( 1, fromTable[ joinedKey ], xIntersectionIndexList )
1905                 xIntersections = getJoinOfXIntersectionIndexes( xIntersectionIndexList )
1906                 lineSegments = getSegmentsFromXIntersections( xIntersections, joinedKey )
1907                 if len( lineSegments ) > 0:
1908                         intoTable[ joinedKey ] = lineSegments
1909                 else:
1910                         print('This should never happen, there are no line segments in joinSegments in euclidean')
1911
1912 def joinXIntersectionsTables( fromTable, intoTable ):
1913         'Join both XIntersections tables and put the join into the intoTable.'
1914         joinedKeyTable = {}
1915         concatenatedTableKeys = fromTable.keys() + intoTable.keys()
1916         for concatenatedTableKey in concatenatedTableKeys:
1917                 joinedKeyTable[ concatenatedTableKey ] = None
1918         for joinedKey in joinedKeyTable.keys():
1919                 xIntersectionIndexList = []
1920                 if joinedKey in intoTable:
1921                         addXIntersectionIndexesFromXIntersections( 0, xIntersectionIndexList, intoTable[ joinedKey ] )
1922                 if joinedKey in fromTable:
1923                         addXIntersectionIndexesFromXIntersections( 1, xIntersectionIndexList, fromTable[ joinedKey ] )
1924                 xIntersections = getJoinOfXIntersectionIndexes( xIntersectionIndexList )
1925                 if len( xIntersections ) > 0:
1926                         intoTable[ joinedKey ] = xIntersections
1927                 else:
1928                         print('This should never happen, there are no line segments in joinSegments in euclidean')
1929
1930 def overwriteDictionary(fromDictionary, keys, toDictionary):
1931         'Overwrite the dictionary.'
1932         for key in keys:
1933                 if key in fromDictionary:
1934                         toDictionary[key] = fromDictionary[key]
1935
1936 def removeElementFromDictionary(dictionary, key):
1937         'Remove element from the dictionary.'
1938         if key in dictionary:
1939                 del dictionary[key]
1940
1941 def removeElementFromListTable(element, key, listDictionary):
1942         'Remove an element from the list table.'
1943         if key not in listDictionary:
1944                 return
1945         elementList = listDictionary[key]
1946         if len( elementList ) < 2:
1947                 del listDictionary[key]
1948                 return
1949         if element in elementList:
1950                 elementList.remove(element)
1951
1952 def removeElementFromPixelListFromPoint( element, pixelDictionary, point ):
1953         'Remove an element from the pixel list.'
1954         stepKey = getStepKeyFromPoint(point)
1955         removeElementFromListTable( element, stepKey, pixelDictionary )
1956
1957 def removeElementsFromDictionary(dictionary, keys):
1958         'Remove list from the dictionary.'
1959         for key in keys:
1960                 removeElementFromDictionary(dictionary, key)
1961
1962 def removePixelTableFromPixelTable( pixelDictionaryToBeRemoved, pixelDictionaryToBeRemovedFrom ):
1963         'Remove pixel from the pixel table.'
1964         removeElementsFromDictionary( pixelDictionaryToBeRemovedFrom, pixelDictionaryToBeRemoved.keys() )
1965
1966 def removePrefixFromDictionary( dictionary, prefix ):
1967         'Remove the attributes starting with the prefix from the dictionary.'
1968         for key in dictionary.keys():
1969                 if key.startswith( prefix ):
1970                         del dictionary[key]
1971
1972 def removeTrueFromDictionary(dictionary, key):
1973         'Remove key from the dictionary in the value is true.'
1974         if key in dictionary:
1975                 if getBooleanFromValue(dictionary[key]):
1976                         del dictionary[key]
1977
1978 def removeTrueListFromDictionary( dictionary, keys ):
1979         'Remove list from the dictionary in the value is true.'
1980         for key in keys:
1981                 removeTrueFromDictionary( dictionary, key )
1982
1983 def subtractXIntersectionsTable( subtractFromTable, subtractTable ):
1984         'Subtract the subtractTable from the subtractFromTable.'
1985         subtractFromTableKeys = subtractFromTable.keys()
1986         subtractFromTableKeys.sort()
1987         for subtractFromTableKey in subtractFromTableKeys:
1988                 xIntersectionIndexList = []
1989                 addXIntersectionIndexesFromXIntersections( - 1, xIntersectionIndexList, subtractFromTable[ subtractFromTableKey ] )
1990                 if subtractFromTableKey in subtractTable:
1991                         addXIntersectionIndexesFromXIntersections( 0, xIntersectionIndexList, subtractTable[ subtractFromTableKey ] )
1992                 xIntersections = getXIntersectionsFromIntersections( xIntersectionIndexList )
1993                 if len( xIntersections ) > 0:
1994                         subtractFromTable[ subtractFromTableKey ] = xIntersections
1995                 else:
1996                         del subtractFromTable[ subtractFromTableKey ]
1997
1998 def swapList( elements, indexBegin, indexEnd ):
1999         'Swap the list elements.'
2000         elements[ indexBegin ], elements[ indexEnd ] = elements[ indexEnd ], elements[ indexBegin ]
2001
2002 def toggleHashtable( hashtable, key, value ):
2003         'Toggle a hashtable between having and not having a key.'
2004         if key in hashtable:
2005                 del hashtable[key]
2006         else:
2007                 hashtable[key] = value
2008
2009 def transferClosestFillLoop(extrusionHalfWidth, oldOrderedLocation, remainingFillLoops, skein):
2010         'Transfer the closest remaining fill loop.'
2011         closestDistance = 987654321987654321.0
2012         closestFillLoop = None
2013         for remainingFillLoop in remainingFillLoops:
2014                 distance = getClosestDistanceIndexToLine(oldOrderedLocation.dropAxis(), remainingFillLoop).distance
2015                 if distance < closestDistance:
2016                         closestDistance = distance
2017                         closestFillLoop = remainingFillLoop
2018         newClosestFillLoop = getLoopInsideContainingLoop(closestFillLoop, remainingFillLoops)
2019         while newClosestFillLoop != None:
2020                 closestFillLoop = newClosestFillLoop
2021                 newClosestFillLoop = getLoopInsideContainingLoop(closestFillLoop, remainingFillLoops)
2022         remainingFillLoops.remove(closestFillLoop)
2023         addToThreadsFromLoop(extrusionHalfWidth, 'loop', closestFillLoop[:], oldOrderedLocation, skein)
2024
2025 def transferClosestPath( oldOrderedLocation, remainingPaths, skein ):
2026         'Transfer the closest remaining path.'
2027         closestDistance = 987654321987654321.0
2028         closestPath = None
2029         oldOrderedLocationComplex = oldOrderedLocation.dropAxis()
2030         for remainingPath in remainingPaths:
2031                 distance = min( abs( oldOrderedLocationComplex - remainingPath[0] ), abs( oldOrderedLocationComplex - remainingPath[-1] ) )
2032                 if distance < closestDistance:
2033                         closestDistance = distance
2034                         closestPath = remainingPath
2035         remainingPaths.remove( closestPath )
2036         skein.addGcodeFromThreadZ( closestPath, oldOrderedLocation.z )
2037         oldOrderedLocation.x = closestPath[-1].real
2038         oldOrderedLocation.y = closestPath[-1].imag
2039
2040 def transferClosestPaths(oldOrderedLocation, remainingPaths, skein):
2041         'Transfer the closest remaining paths.'
2042         while len(remainingPaths) > 0:
2043                 transferClosestPath(oldOrderedLocation, remainingPaths, skein)
2044
2045 def transferPathsToNestedRings(nestedRings, paths):
2046         'Transfer paths to nested rings.'
2047         for nestedRing in nestedRings:
2048                 nestedRing.transferPaths(paths)
2049
2050 def translateVector3Path(path, translateVector3):
2051         'Translate the vector3 path.'
2052         for point in path:
2053                 point.setToVector3(point + translateVector3)
2054
2055 def translateVector3Paths(paths, translateVector3):
2056         'Translate the vector3 paths.'
2057         for path in paths:
2058                 translateVector3Path(path, translateVector3)
2059
2060 def unbuckleBasis( basis, maximumUnbuckling, normal ):
2061         'Unbuckle space.'
2062         normalDot = basis.dot( normal )
2063         dotComplement = math.sqrt( 1.0 - normalDot * normalDot )
2064         unbuckling = maximumUnbuckling
2065         if dotComplement > 0.0:
2066                 unbuckling = min( 1.0 / dotComplement, maximumUnbuckling )
2067         basis.setToVector3( basis * unbuckling )
2068
2069
2070 class DistanceIndex:
2071         'A class to hold the distance and the index of the loop.'
2072         def __init__(self, distance, index):
2073                 'Initialize.'
2074                 self.distance = distance
2075                 self.index = index
2076
2077         def __repr__(self):
2078                 'Get the string representation of this distance index.'
2079                 return '%s, %s' % (self.distance, self.index)
2080
2081
2082 class Endpoint:
2083         'The endpoint of a segment.'
2084         def __repr__(self):
2085                 'Get the string representation of this Endpoint.'
2086                 return 'Endpoint %s, %s' % ( self.point, self.otherEndpoint.point )
2087
2088         def getClosestEndpoint( self, endpoints ):
2089                 'Get closest endpoint.'
2090                 smallestDistance = 987654321987654321.0
2091                 closestEndpoint = None
2092                 for endpoint in endpoints:
2093                         distance = abs( self.point - endpoint.point )
2094                         if distance < smallestDistance:
2095                                 smallestDistance = distance
2096                                 closestEndpoint = endpoint
2097                 return closestEndpoint
2098
2099         def getClosestMiss(self, endpoints, path, pixelDictionary, sharpestProduct, width):
2100                 'Get the closest endpoint which the segment to that endpoint misses the other extrusions.'
2101                 pathMaskTable = {}
2102                 smallestDistance = 987654321.0
2103                 penultimateMinusPoint = complex(0.0, 0.0)
2104                 if len(path) > 1:
2105                         penultimatePoint = path[-2]
2106                         addSegmentToPixelTable(penultimatePoint, self.point, pathMaskTable, 0, 0, width)
2107                         penultimateMinusPoint = penultimatePoint - self.point
2108                         if abs(penultimateMinusPoint) > 0.0:
2109                                 penultimateMinusPoint /= abs(penultimateMinusPoint)
2110                 for endpoint in endpoints:
2111                         endpoint.segment = endpoint.point - self.point
2112                         endpoint.segmentLength = abs(endpoint.segment)
2113                         if endpoint.segmentLength <= 0.0:
2114                                 return endpoint
2115                 endpoints.sort(compareSegmentLength)
2116                 for endpoint in endpoints[: 15]: # increasing the number of searched endpoints increases the search time, with 20 fill took 600 seconds for cilinder.gts, with 10 fill took 533 seconds
2117                         normalizedSegment = endpoint.segment / endpoint.segmentLength
2118                         isOverlappingSelf = getDotProduct(penultimateMinusPoint, normalizedSegment) > sharpestProduct
2119                         if not isOverlappingSelf:
2120                                 if len(path) > 2:
2121                                         segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2122                                         pointRotated = segmentYMirror * self.point
2123                                         endpointPointRotated = segmentYMirror * endpoint.point
2124                                         if isXSegmentIntersectingPath(path[max(0, len(path) - 21) : -1], pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2125                                                 isOverlappingSelf = True
2126                         if not isOverlappingSelf:
2127                                 totalMaskTable = pathMaskTable.copy()
2128                                 addSegmentToPixelTable(endpoint.point, endpoint.otherEndpoint.point, totalMaskTable, 0, 0, width)
2129                                 segmentTable = {}
2130                                 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2131                                 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
2132                                         return endpoint
2133                 return None
2134
2135         def getClosestMissCheckEndpointPath(self, endpoints, path, pixelDictionary, sharpestProduct, width):
2136                 'Get the closest endpoint which the segment to that endpoint misses the other extrusions, also checking the path of the endpoint.'
2137                 pathMaskTable = {}
2138                 smallestDistance = 987654321.0
2139                 penultimateMinusPoint = complex(0.0, 0.0)
2140                 if len(path) > 1:
2141                         penultimatePoint = path[-2]
2142                         addSegmentToPixelTable(penultimatePoint, self.point, pathMaskTable, 0, 0, width)
2143                         penultimateMinusPoint = penultimatePoint - self.point
2144                         if abs(penultimateMinusPoint) > 0.0:
2145                                 penultimateMinusPoint /= abs(penultimateMinusPoint)
2146                 for endpoint in endpoints:
2147                         endpoint.segment = endpoint.point - self.point
2148                         endpoint.segmentLength = abs(endpoint.segment)
2149                         if endpoint.segmentLength <= 0.0:
2150                                 return endpoint
2151                 endpoints.sort( compareSegmentLength )
2152                 for endpoint in endpoints[ : 15 ]: # increasing the number of searched endpoints increases the search time, with 20 fill took 600 seconds for cilinder.gts, with 10 fill took 533 seconds
2153                         normalizedSegment = endpoint.segment / endpoint.segmentLength
2154                         isOverlappingSelf = getDotProduct(penultimateMinusPoint, normalizedSegment) > sharpestProduct
2155                         if not isOverlappingSelf:
2156                                 if len(path) > 2:
2157                                         segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2158                                         pointRotated = segmentYMirror * self.point
2159                                         endpointPointRotated = segmentYMirror * endpoint.point
2160                                         if isXSegmentIntersectingPath(path[ max(0, len(path) - 21) : -1], pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2161                                                 isOverlappingSelf = True
2162                                 endpointPath = endpoint.path
2163                                 if len(endpointPath) > 2:
2164                                         segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2165                                         pointRotated = segmentYMirror * self.point
2166                                         endpointPointRotated = segmentYMirror * endpoint.point
2167                                         if isXSegmentIntersectingPath(endpointPath, pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2168                                                 isOverlappingSelf = True
2169                         if not isOverlappingSelf:
2170                                 totalMaskTable = pathMaskTable.copy()
2171                                 addSegmentToPixelTable(endpoint.point, endpoint.otherEndpoint.point, totalMaskTable, 0, 0, width)
2172                                 segmentTable = {}
2173                                 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2174                                 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
2175                                         return endpoint
2176                 return None
2177
2178         def getFromOtherPoint( self, otherEndpoint, point ):
2179                 'Initialize from other endpoint.'
2180                 self.otherEndpoint = otherEndpoint
2181                 self.point = point
2182                 return self
2183
2184
2185 class LoopLayer:
2186         'Loops with a z.'
2187         def __init__(self, z):
2188                 'Initialize.'
2189                 self.loops = []
2190                 self.z = z
2191
2192         def __repr__(self):
2193                 'Get the string representation of this loop layer.'
2194                 return '%s, %s' % (self.z, self.loops)
2195
2196
2197 class NestedRing:
2198         'A nested ring.'
2199         def __init__(self):
2200                 'Initialize.'
2201                 self.boundary = []
2202                 self.innerNestedRings = None
2203
2204         def __repr__(self):
2205                 'Get the string representation of this nested ring.'
2206                 return str(self.__dict__)
2207
2208         def addFlattenedNestedRings(self, flattenedNestedRings):
2209                 'Add flattened nested rings.'
2210                 flattenedNestedRings.append(self)
2211                 for innerNestedRing in self.innerNestedRings:
2212                         flattenedNestedRings += getFlattenedNestedRings(innerNestedRing.innerNestedRings)
2213
2214         def getFromInsideSurroundings(self, inputSurroundingInsides):
2215                 'Initialize from inside nested rings.'
2216                 transferredSurroundings = getTransferredNestedRings(inputSurroundingInsides, self.boundary)
2217                 self.innerNestedRings = getOrderedNestedRings(transferredSurroundings)
2218                 return self
2219
2220
2221 class NestedBand(NestedRing):
2222         'A loop that surrounds paths.'
2223         def __init__(self):
2224                 'Initialize.'
2225                 NestedRing.__init__(self)
2226                 self.edgePaths = []
2227                 self.extraLoops = []
2228                 self.infillBoundaries = []
2229                 self.infillPaths = []
2230 #               self.lastExistingFillLoops = None
2231                 self.lastFillLoops = None
2232                 self.loop = None
2233                 self.penultimateFillLoops = []
2234                 self.z = None
2235
2236         def __repr__(self):
2237                 'Get the string representation of this nested ring.'
2238                 stringRepresentation = 'boundary\n%s\n' % self.boundary
2239                 stringRepresentation += 'loop\n%s\n' % self.loop
2240                 stringRepresentation += 'inner nested rings\n%s\n' % self.innerNestedRings
2241                 stringRepresentation += 'infillPaths\n'
2242                 for infillPath in self.infillPaths:
2243                         stringRepresentation += 'infillPath\n%s\n' % infillPath
2244                 stringRepresentation += 'edgePaths\n'
2245                 for edgePath in self.edgePaths:
2246                         stringRepresentation += 'edgePath\n%s\n' % edgePath
2247                 return stringRepresentation + '\n'
2248
2249         def addPerimeterInner(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2250                 'Add to the edge and the inner island.'
2251                 if self.loop == None:
2252                         skein.distanceFeedRate.addLine('(<edgePath>)')
2253                         transferClosestPaths(oldOrderedLocation, self.edgePaths[:], skein)
2254                         skein.distanceFeedRate.addLine('(</edgePath>)')
2255                 else:
2256                         addToThreadsFromLoop(extrusionHalfWidth, 'edge', self.loop[:], oldOrderedLocation, skein)
2257                 skein.distanceFeedRate.addLine('(</boundaryPerimeter>)')
2258                 addToThreadsRemove(extrusionHalfWidth, self.innerNestedRings[:], oldOrderedLocation, skein, threadSequence)
2259
2260         def addToBoundary(self, vector3):
2261                 'Add vector3 to boundary.'
2262                 self.boundary.append(vector3.dropAxis())
2263                 self.z = vector3.z
2264
2265         def addToLoop(self, vector3):
2266                 'Add vector3 to loop.'
2267                 if self.loop == None:
2268                         self.loop = []
2269                 self.loop.append(vector3.dropAxis())
2270                 self.z = vector3.z
2271
2272         def addToThreads(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2273                 'Add to paths from the last location.'
2274                 addNestedRingBeginning(skein.distanceFeedRate, self.boundary, self.z)
2275                 threadFunctionDictionary = {
2276                         'infill' : self.transferInfillPaths, 'loops' : self.transferClosestFillLoops, 'edge' : self.addPerimeterInner}
2277                 for threadType in threadSequence:
2278                         threadFunctionDictionary[threadType](extrusionHalfWidth, oldOrderedLocation, skein, threadSequence)
2279                 skein.distanceFeedRate.addLine('(</nestedRing>)')
2280
2281         def getFillLoops(self, penultimateFillLoops):
2282                 'Get last fill loops from the outside loop and the loops inside the inside loops.'
2283                 fillLoops = self.getLoopsToBeFilled()[:]
2284                 surroundingBoundaries = self.getSurroundingBoundaries()
2285                 withinLoops = []
2286                 if penultimateFillLoops == None:
2287                         penultimateFillLoops = self.penultimateFillLoops
2288                 if penultimateFillLoops == None:
2289                         print('Warning, penultimateFillLoops == None in getFillLoops in NestedBand in euclidean.')
2290                         return fillLoops
2291                 for penultimateFillLoop in penultimateFillLoops:
2292                         if len(penultimateFillLoop) > 2:
2293                                 if getIsInFilledRegion(surroundingBoundaries, penultimateFillLoop[0]):
2294                                         withinLoops.append(penultimateFillLoop)
2295                 if not getIsInFilledRegionByPaths(self.penultimateFillLoops, fillLoops):
2296                         fillLoops += self.penultimateFillLoops
2297                 for nestedRing in self.innerNestedRings:
2298                         fillLoops += getFillOfSurroundings(nestedRing.innerNestedRings, penultimateFillLoops)
2299                 return fillLoops
2300 #
2301 #       def getLastExistingFillLoops(self):
2302 #               'Get last existing fill loops.'
2303 #               lastExistingFillLoops = self.lastExistingFillLoops[:]
2304 #               for nestedRing in self.innerNestedRings:
2305 #                       lastExistingFillLoops += nestedRing.getLastExistingFillLoops()
2306 #               return lastExistingFillLoops
2307
2308         def getLoopsToBeFilled(self):
2309                 'Get last fill loops from the outside loop and the loops inside the inside loops.'
2310                 if self.lastFillLoops == None:
2311                         return self.getSurroundingBoundaries()
2312                 return self.lastFillLoops
2313
2314         def getSurroundingBoundaries(self):
2315                 'Get the boundary of the surronding loop plus any boundaries of the innerNestedRings.'
2316                 surroundingBoundaries = [self.boundary]
2317                 for nestedRing in self.innerNestedRings:
2318                         surroundingBoundaries.append(nestedRing.boundary)
2319                 return surroundingBoundaries
2320
2321         def transferClosestFillLoops(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2322                 'Transfer closest fill loops.'
2323                 if len( self.extraLoops ) < 1:
2324                         return
2325                 remainingFillLoops = self.extraLoops[:]
2326                 while len( remainingFillLoops ) > 0:
2327                         transferClosestFillLoop(extrusionHalfWidth, oldOrderedLocation, remainingFillLoops, skein)
2328
2329         def transferInfillPaths(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2330                 'Transfer the infill paths.'
2331                 if len(self.infillBoundaries) == 0 and len(self.infillPaths) == 0:
2332                         return
2333                 skein.distanceFeedRate.addLine('(<infill>)')
2334                 for infillBoundary in self.infillBoundaries:
2335                         skein.distanceFeedRate.addLine('(<infillBoundary>)')
2336                         for infillPoint in infillBoundary:
2337                                 infillPointVector3 = Vector3(infillPoint.real, infillPoint.imag, self.z)
2338                                 skein.distanceFeedRate.addLine(skein.distanceFeedRate.getInfillBoundaryLine(infillPointVector3))
2339                         skein.distanceFeedRate.addLine('(</infillBoundary>)')
2340                 transferClosestPaths(oldOrderedLocation, self.infillPaths[:], skein)
2341                 skein.distanceFeedRate.addLine('(</infill>)')
2342
2343         def transferPaths(self, paths):
2344                 'Transfer paths.'
2345                 for nestedRing in self.innerNestedRings:
2346                         transferPathsToNestedRings(nestedRing.innerNestedRings, paths)
2347                 self.infillPaths = getTransferredPaths(paths, self.boundary)
2348
2349
2350 class PathZ:
2351         'Complex path with a z.'
2352         def __init__( self, z ):
2353                 self.path = []
2354                 self.z = z
2355
2356         def __repr__(self):
2357                 'Get the string representation of this path z.'
2358                 return '%s, %s' % ( self.z, self.path )
2359
2360
2361 class ProjectiveSpace:
2362         'Class to define a projective space.'
2363         def __init__( self, basisX = Vector3(1.0, 0.0, 0.0), basisY = Vector3( 0.0, 1.0, 0.0 ), basisZ = Vector3(0.0, 0.0, 1.0) ):
2364                 'Initialize the basis vectors.'
2365                 self.basisX = basisX
2366                 self.basisY = basisY
2367                 self.basisZ = basisZ
2368
2369         def __repr__(self):
2370                 'Get the string representation of this ProjectivePlane.'
2371                 return '%s, %s, %s' % ( self.basisX, self.basisY, self.basisZ )
2372
2373         def getByBasisXZ( self, basisX, basisZ ):
2374                 'Get by x basis x and y basis.'
2375                 self.basisX = basisX
2376                 self.basisZ = basisZ
2377                 self.basisX.normalize()
2378                 self.basisY = basisZ.cross(self.basisX)
2379                 self.basisY.normalize()
2380                 return self
2381
2382         def getByBasisZFirst(self, basisZ, firstVector3):
2383                 'Get by basisZ and first.'
2384                 self.basisZ = basisZ
2385                 self.basisY = basisZ.cross(firstVector3)
2386                 self.basisY.normalize()
2387                 self.basisX = self.basisY.cross(self.basisZ)
2388                 self.basisX.normalize()
2389                 return self
2390
2391         def getByBasisZTop(self, basisZ, top):
2392                 'Get by basisZ and top.'
2393                 return self.getByBasisXZ(top.cross(basisZ), basisZ)
2394
2395         def getByLatitudeLongitude( self, viewpointLatitude, viewpointLongitude ):
2396                 'Get by latitude and longitude.'
2397                 longitudeComplex = getWiddershinsUnitPolar( math.radians( 90.0 - viewpointLongitude ) )
2398                 viewpointLatitudeRatio = getWiddershinsUnitPolar( math.radians( viewpointLatitude ) )
2399                 basisZ = Vector3( viewpointLatitudeRatio.imag * longitudeComplex.real, viewpointLatitudeRatio.imag * longitudeComplex.imag, viewpointLatitudeRatio.real )
2400                 return self.getByBasisXZ( Vector3( - longitudeComplex.imag, longitudeComplex.real, 0.0 ), basisZ )
2401
2402         def getByTilt( self, tilt ):
2403                 'Get by latitude and longitude.'
2404                 xPlaneAngle = getWiddershinsUnitPolar( tilt.real )
2405                 self.basisX = Vector3( xPlaneAngle.real, 0.0,  xPlaneAngle.imag )
2406                 yPlaneAngle = getWiddershinsUnitPolar( tilt.imag )
2407                 self.basisY = Vector3( 0.0,  yPlaneAngle.real, yPlaneAngle.imag )
2408                 self.basisZ = self.basisX.cross(self.basisY)
2409                 return self
2410
2411         def getComplexByComplex( self, pointComplex ):
2412                 'Get complex by complex point.'
2413                 return self.basisX.dropAxis() * pointComplex.real + self.basisY.dropAxis() * pointComplex.imag
2414
2415         def getCopy(self):
2416                 'Get copy.'
2417                 return ProjectiveSpace( self.basisX, self.basisY, self.basisZ )
2418
2419         def getDotComplex(self, point):
2420                 'Get the dot complex.'
2421                 return complex( point.dot(self.basisX), point.dot(self.basisY) )
2422
2423         def getDotVector3(self, point):
2424                 'Get the dot vector3.'
2425                 return Vector3(point.dot(self.basisX), point.dot(self.basisY), point.dot(self.basisZ))
2426
2427         def getNextSpace( self, nextNormal ):
2428                 'Get next space by next normal.'
2429                 nextSpace = self.getCopy()
2430                 nextSpace.normalize()
2431                 dotNext = nextSpace.basisZ.dot( nextNormal )
2432                 if dotNext > 0.999999:
2433                         return nextSpace
2434                 if dotNext < - 0.999999:
2435                         nextSpace.basisX = - nextSpace.basisX
2436                         return nextSpace
2437                 crossNext = nextSpace.basisZ.cross( nextNormal )
2438                 oldBasis = ProjectiveSpace().getByBasisZTop( nextSpace.basisZ, crossNext )
2439                 newBasis = ProjectiveSpace().getByBasisZTop( nextNormal, crossNext )
2440                 nextSpace.basisX = newBasis.getVector3ByPoint( oldBasis.getDotVector3( nextSpace.basisX ) )
2441                 nextSpace.basisY = newBasis.getVector3ByPoint( oldBasis.getDotVector3( nextSpace.basisY ) )
2442                 nextSpace.basisZ = newBasis.getVector3ByPoint( oldBasis.getDotVector3( nextSpace.basisZ ) )
2443                 nextSpace.normalize()
2444                 return nextSpace
2445
2446         def getSpaceByXYScaleAngle( self, angle, scale ):
2447                 'Get space by angle and scale.'
2448                 spaceByXYScaleRotation = ProjectiveSpace()
2449                 planeAngle = getWiddershinsUnitPolar(angle)
2450                 spaceByXYScaleRotation.basisX = self.basisX * scale.real * planeAngle.real + self.basisY * scale.imag * planeAngle.imag
2451                 spaceByXYScaleRotation.basisY = - self.basisX * scale.real * planeAngle.imag + self.basisY * scale.imag * planeAngle.real
2452                 spaceByXYScaleRotation.basisZ = self.basisZ
2453                 return spaceByXYScaleRotation
2454
2455         def getVector3ByPoint(self, point):
2456                 'Get vector3 by point.'
2457                 return self.basisX * point.x + self.basisY * point.y + self.basisZ * point.z
2458
2459         def normalize(self):
2460                 'Normalize.'
2461                 self.basisX.normalize()
2462                 self.basisY.normalize()
2463                 self.basisZ.normalize()
2464
2465         def unbuckle( self, maximumUnbuckling, normal ):
2466                 'Unbuckle space.'
2467                 unbuckleBasis( self.basisX, maximumUnbuckling, normal )
2468                 unbuckleBasis( self.basisY, maximumUnbuckling, normal )
2469
2470
2471 class XIntersectionIndex:
2472         'A class to hold the x intersection position and the index of the loop which intersected.'
2473         def __init__( self, index, x ):
2474                 'Initialize.'
2475                 self.index = index
2476                 self.x = x
2477
2478         def __cmp__(self, other):
2479                 'Get comparison in order to sort x intersections in ascending order of x.'
2480                 if self.x < other.x:
2481                         return - 1
2482                 return int( self.x > other.x )
2483
2484         def __eq__(self, other):
2485                 'Determine whether this XIntersectionIndex is identical to other one.'
2486                 if other == None:
2487                         return False
2488                 if other.__class__ != self.__class__:
2489                         return False
2490                 return self.index == other.index and self.x == other.x
2491
2492         def __ne__(self, other):
2493                 'Determine whether this XIntersectionIndex is not identical to other one.'
2494                 return not self.__eq__(other)
2495
2496         def __repr__(self):
2497                 'Get the string representation of this x intersection.'
2498                 return 'XIntersectionIndex index %s; x %s ' % ( self.index, self.x )