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