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