2 Euclidean is a collection of python utilities for complex numbers, paths, polygons & Vector3s.
4 To use euclidean, install python 2.x on your machine, which is avaliable from http://www.python.org/download/
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.
9 Below are examples of euclidean use.
11 >>> from euclidean import *
13 >>> right=complex(1.0,0.0)
14 >>> back=complex(0.0,1.0)
15 >>> getMaximum(right,back)
17 >>> polygon=[origin, right, back]
18 >>> getLoopLength(polygon)
20 >>> getAreaLoop(polygon)
24 from __future__ import absolute_import
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.
33 from fabmetheus_utilities.vector3 import Vector3
34 from fabmetheus_utilities import xml_simple_writer
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'
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/
50 def addElementToListDictionary(element, key, listDictionary):
51 'Add an element to the list table.'
52 if key in listDictionary:
53 listDictionary[key].append(element)
55 listDictionary[key] = [element]
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)
64 listDictionary[key] = [element]
66 def addElementToPixelList( element, pixelDictionary, x, y ):
67 'Add an element to the pixel list.'
68 addElementToListDictionary( element, (x, y), pixelDictionary )
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 ) ) )
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:
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)
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)
91 def addListToListTable( elementList, key, listDictionary ):
92 'Add a list to the list table.'
93 if key in listDictionary:
94 listDictionary[key] += elementList
96 listDictionary[key] = elementList
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 )
105 def addNestedRingBeginning(distanceFeedRate, loop, z):
106 'Add nested ring beginning to gcode output.'
107 distanceFeedRate.addLine('(<nestedRing>)')
108 distanceFeedRate.addLine('(<boundaryPerimeter>)')
110 pointVector3 = Vector3(point.real, point.imag, z)
111 distanceFeedRate.addLine(distanceFeedRate.getBoundaryLine(pointVector3))
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 )
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 ]
125 def addPixelToPixelTableWithSteepness( isSteep, pixelDictionary, value, x, y ):
126 'Add pixels to the pixel table with steepness.'
128 pixelDictionary[(y, x)] = value
130 pixelDictionary[(x, y)] = value
132 def addPointToPath( path, pixelDictionary, point, value, width ):
133 'Add a point to a path and the pixel table.'
138 addValueSegmentToPixelTable( begin, point, pixelDictionary, value, width )
140 def addSegmentToPixelTable( beginComplex, endComplex, pixelDictionary, shortenDistanceBegin, shortenDistanceEnd, width ):
141 'Add line segment to the pixel table.'
142 if abs( beginComplex - endComplex ) <= 0.0:
144 beginComplex /= width
146 if shortenDistanceBegin > 0.0:
147 endMinusBeginComplex = endComplex - beginComplex
148 endMinusBeginComplexLength = abs( endMinusBeginComplex )
149 if endMinusBeginComplexLength < shortenDistanceBegin:
151 beginComplex = beginComplex + endMinusBeginComplex * shortenDistanceBegin / endMinusBeginComplexLength
152 if shortenDistanceEnd > 0.0:
153 beginMinusEndComplex = beginComplex - endComplex
154 beginMinusEndComplexLength = abs( beginMinusEndComplex )
155 if beginMinusEndComplexLength < 0.0:
157 endComplex = endComplex + beginMinusEndComplex * shortenDistanceEnd / beginMinusEndComplexLength
158 deltaX = endComplex.real - beginComplex.real
159 deltaY = endComplex.imag - beginComplex.imag
160 isSteep = abs( deltaY ) > abs( deltaX )
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
169 gradient = deltaY / deltaX
172 print('Warning, deltaX in addSegmentToPixelTable in euclidean is 0.')
175 print(shortenDistanceBegin)
176 print(shortenDistanceEnd)
178 xBegin = int(round(beginComplex.real))
179 xEnd = int(round(endComplex.real))
180 yIntersection = beginComplex.imag - beginComplex.real * gradient
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
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
196 def addSquareTwoToPixelDictionary(pixelDictionary, point, value, width):
197 'Add square with two pixels around the center to pixel dictionary.'
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
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)
214 skein.distanceFeedRate.addLine('(<%s> inner )' % gcodeType)
215 skein.addGcodeFromThreadZ(loop + [loop[0]], oldOrderedLocation.z)
216 skein.distanceFeedRate.addLine('(</%s>)' % gcodeType)
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)
223 def addValueSegmentToPixelTable( beginComplex, endComplex, pixelDictionary, value, width ):
224 'Add line segment to the pixel table.'
225 if abs( beginComplex - endComplex ) <= 0.0:
227 beginComplex /= width
229 deltaX = endComplex.real - beginComplex.real
230 deltaY = endComplex.imag - beginComplex.imag
231 isSteep = abs( deltaY ) > abs( deltaX )
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
240 gradient = deltaY / deltaX
243 print('Warning, deltaX in addValueSegmentToPixelTable in euclidean is 0.')
248 xBegin = int(round(beginComplex.real))
249 xEnd = int(round(endComplex.real))
250 yIntersection = beginComplex.imag - beginComplex.real * gradient
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
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
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:
275 addValueToOutput(depth + 1, key, output, value[key])
277 if value.__class__ == list:
279 for elementIndex, element in enumerate(value):
280 addValueToOutput(depth + 1, elementIndex, output, element)
282 output.write(' %s\n' % value)
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 )
290 def addXIntersectionIndexesFromLoopsY( loops, solidIndex, xIntersectionIndexList, y ):
291 'Add the x intersection indexes for the loops.'
293 addXIntersectionIndexesFromLoopY( loop, solidIndex, xIntersectionIndexList, y )
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 ) )
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 ) )
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 )
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 ) )
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 )
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 ):
345 xIntersection = y * secondMinusFirstImaginaryOverReal + beginRealMinusImaginary
346 addElementToListDictionary( xIntersection, fillLine, xIntersectionsTable )
348 def addXIntersectionsFromLoops(loops, xIntersections, y):
349 'Add the x intersections for the loops.'
351 addXIntersections(loop, xIntersections, y)
353 def addXIntersectionsFromLoopsForTable(loops, xIntersectionsTable, width):
354 'Add the x intersections for a loop into a table.'
356 addXIntersectionsFromLoopForTable(loop, xIntersectionsTable, width)
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:
362 if endpoint.segmentLength < otherEndpoint.segmentLength:
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)
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)
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)
391 if len( nextEndpoint.path ) > 1:
392 nextPenultimate = nextEndpoint.path[-2]
393 if getDotProduct(getNormalized(nextPenultimate - nextBegin), - nextMinusBottomNormalized) > 0.99:
394 connectedPaths.append(path)
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)
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 )
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 )
414 def getAreaLoop(loop):
415 'Get the area of a complex polygon.'
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
422 def getAreaLoopAbsolute(loop):
423 'Get the absolute area of a complex polygon.'
424 return abs(getAreaLoop(loop))
426 def getAreaLoops(loops):
427 'Get the area of a list of complex polygons.'
430 areaLoops += getAreaLoop(loop)
433 def getAreaVector3LoopAbsolute(loop):
434 'Get the absolute area of a vector3 polygon.'
435 return getAreaLoopAbsolute(getComplexPath(loop))
437 def getAroundLoop(begin, end, loop):
438 'Get an arc around a loop.'
442 for pointIndex in xrange(begin, end):
443 aroundLoop.append(loop[pointIndex % len(loop)])
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.'
451 awayPath = getAwayPoints(path, radius)
452 if len(awayPath) == 0:
454 if abs(lastPoint - awayPath[-1]) > 0.001 * radius:
455 awayPath.append(lastPoint)
458 def getAwayPoints(points, radius):
459 'Get a path with only the points that are far enough away from each other.'
461 oneOverOverlapDistance = 1000.0 / radius
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
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])
477 def getBooleanFromValue(value):
478 'Get boolean from the word.'
479 firstCharacter = str(value).lower().lstrip()[: 1]
480 return firstCharacter == 't' or firstCharacter == '1'
482 def getBottomByPath(path):
483 'Get the bottom of the path.'
484 bottom = 987654321987654321.0
486 bottom = min(bottom, point.z)
489 def getBottomByPaths(paths):
490 'Get the bottom of the paths.'
491 bottom = 987654321987654321.0
494 bottom = min(bottom, point.z)
497 def getClippedAtEndLoopPath( clip, loopPath ):
498 'Get a clipped loop path.'
501 loopPathLength = getPathLength(loopPath)
502 clip = min( clip, 0.3 * loopPathLength )
506 clippedLength = loopPathLength - clip
507 while totalLength < clippedLength and pointIndex < len(loopPath) - 1:
508 firstPoint = loopPath[pointIndex]
509 secondPoint = loopPath[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]
524 def getClippedLoopPath(clip, loopPath):
525 'Get a clipped loop path.'
528 loopPathLength = getPathLength(loopPath)
529 clip = min(clip, 0.3 * loopPathLength)
533 while totalLength < clip and pointIndex < len(loopPath) - 1:
534 firstPoint = loopPath[pointIndex]
535 secondPoint = loopPath[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)
551 def getClippedSimplifiedLoopPath(clip, loopPath, radius):
552 'Get a clipped and simplified loop path.'
553 return getSimplifiedPath(getClippedLoopPath(clip, loopPath), radius)
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
568 def getClosestPointOnSegment(segmentBegin, segmentEnd, point):
569 'Get the closest point on the segment.'
570 segmentDifference = segmentEnd - segmentBegin
571 if abs(segmentDifference) <= 0.0:
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
581 def getComplexByCommaString( valueCommaString ):
582 'Get the commaString as a complex.'
584 splitLine = valueCommaString.replace(',', ' ').split()
585 return complex( float( splitLine[0] ), float(splitLine[1]) )
590 def getComplexByWords(words, wordIndex=0):
591 'Get the complex by the first two words.'
593 return complex(float(words[wordIndex]), float(words[wordIndex + 1]))
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
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 )
610 def getComplexPath(vector3Path):
611 'Get the complex path from the vector3 path.'
613 for point in vector3Path:
614 complexPath.append(point.dropAxis())
617 def getComplexPathByMultiplier(multiplier, path):
618 'Get the multiplied complex path.'
621 complexPath.append(multiplier * point)
624 def getComplexPaths(vector3Paths):
625 'Get the complex paths from the vector3 paths.'
627 for vector3Path in vector3Paths:
628 complexPaths.append(getComplexPath(vector3Path))
631 def getComplexPolygon(center, radius, sides, startAngle=0.0):
632 'Get the complex polygon.'
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
641 def getComplexPolygonByComplexRadius(radius, sides, startAngle=0.0):
642 'Get the complex polygon.'
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
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)
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)
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
671 def getConnectedPaths(paths, pixelDictionary, sharpestProduct, width):
672 'Get connected paths from paths.'
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
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
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))))
693 def getDiagonalFlippedLoop(loop):
694 'Get loop flipped over the dialogonal, in other words with the x and y swapped.'
695 diagonalFlippedLoop = []
697 diagonalFlippedLoop.append( complex( point.imag, point.real ) )
698 return diagonalFlippedLoop
700 def getDiagonalFlippedLoops(loops):
701 'Get loops flipped over the dialogonal, in other words with the x and y swapped.'
702 diagonalFlippedLoops = []
704 diagonalFlippedLoops.append( getDiagonalFlippedLoop(loop) )
705 return diagonalFlippedLoops
707 def getDictionaryString(dictionary):
708 'Get the dictionary string.'
709 output = cStringIO.StringIO()
710 keys = dictionary.keys()
713 addValueToOutput(0, key, output, dictionary[key])
714 return output.getvalue()
716 def getDistanceToLine(begin, end, point):
717 'Get the distance from a vector3 point to an infinite line.'
718 pointMinusBegin = point - begin
720 return abs(pointMinusBegin)
721 endMinusBegin = end - begin
722 return abs(endMinusBegin.cross(pointMinusBegin)) / abs(endMinusBegin)
724 def getDistanceToLineByPath(begin, end, path):
725 'Get the maximum distance from a path to an infinite line.'
726 distanceToLine = -987654321.0
728 distanceToLine = max(getDistanceToLine(begin, end, point), distanceToLine)
729 return distanceToLine
731 def getDistanceToLineByPaths(begin, end, paths):
732 'Get the maximum distance from paths to an infinite line.'
733 distanceToLine = -987654321.0
735 distanceToLine = max(getDistanceToLineByPath(begin, end, path), distanceToLine)
736 return distanceToLine
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 )
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
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 )
760 def getDurationString( seconds ):
761 'Get the duration string.'
762 secondsRounded = int( round( seconds ) )
763 durationString = getPluralString( secondsRounded % 60, 'second')
765 return durationString
766 durationString = '%s %s' % ( getPluralString( ( secondsRounded / 60 ) % 60, 'minute'), durationString )
768 return durationString
769 return '%s %s' % ( getPluralString( secondsRounded / 3600, 'hour'), durationString )
771 def getEndpointFromPath( path, pathIndex ):
772 'Get endpoint segment from a path.'
775 endpointBegin = Endpoint()
776 endpointEnd = Endpoint().getFromOtherPoint( endpointBegin, end )
777 endpointBegin.getFromOtherPoint( endpointEnd, begin )
778 endpointBegin.path = path
779 endpointBegin.pathIndex = pathIndex
782 def getEndpointsFromSegments( segments ):
783 'Get endpoints from segments.'
785 for segment in segments:
786 for endpoint in segment:
787 endpoints.append( endpoint )
790 def getEndpointsFromSegmentTable( segmentTable ):
791 'Get the endpoints from the segment table.'
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 )
801 def getEnumeratorKeys(enumerator, keys):
802 'Get enumerator keys.'
805 return getEnumeratorKeysExceptForOneArgument(enumerator, keys)
807 def getEnumeratorKeysAlwaysList(enumerator, keys):
808 'Get enumerator keys.'
809 if keys.__class__ != list:
813 return getEnumeratorKeysExceptForOneArgument(enumerator, keys)
815 def getEnumeratorKeysExceptForOneArgument(enumerator, keys):
816 'Get enumerator keys, except when there is one argument.'
818 return range(0, len(enumerator))
822 if beginIndex == None:
825 endIndex = len(enumerator)
826 return range(beginIndex, endIndex)
828 beginIndexDefault = 0
829 endIndexDefault = len(enumerator)
831 beginIndexDefault = endIndexDefault - 1
833 if beginIndex == None:
834 beginIndex = beginIndexDefault
836 endIndex = endIndexDefault
837 return range(beginIndex, endIndex, step)
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
846 def getFlattenedNestedRings(nestedRings):
847 'Get flattened nested rings.'
848 flattenedNestedRings = []
849 for nestedRing in nestedRings:
850 nestedRing.addFlattenedNestedRings(flattenedNestedRings)
851 return flattenedNestedRings
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:
860 return evaluatedFloat
862 def getFloatFromValue(value):
863 'Get the value as a float.'
870 def getFourSignificantFigures(number):
871 'Get number rounded to four significant figures as a string.'
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 )
881 def getHalfSimplifiedLoop( loop, radius, remainder ):
882 'Get the loop with half of the points inside the channel removed.'
885 channelRadius = radius * .01
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)
898 def getHalfSimplifiedPath(path, radius, remainder):
899 'Get the path with half of the points inside the channel removed.'
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])
913 def getHorizontallyBoundedPath(horizontalBegin, horizontalEnd, path):
914 'Get horizontally bounded path.'
915 horizontallyBoundedPath = []
916 for pointIndex, point in enumerate(path):
918 previousIndex = pointIndex - 1
919 if previousIndex >= 0:
920 begin = path[previousIndex]
922 nextIndex = pointIndex + 1
923 if nextIndex < len(path):
924 end = path[nextIndex]
925 addHorizontallyBoundedPoint(begin, point, end, horizontalBegin, horizontalEnd, horizontallyBoundedPath)
926 return horizontallyBoundedPath
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 ] )
936 def getInsidesAddToOutsides( loops, outsides ):
937 'Add loops to either the insides or outsides.'
939 for loopIndex in xrange( len(loops) ):
940 loop = loops[loopIndex]
941 if isInsideOtherLoops( loopIndex, loops ):
944 outsides.append(loop)
947 def getIntermediateLocation( alongWay, begin, end ):
948 'Get the intermediate location between begin and end.'
949 return begin * ( 1.0 - alongWay ) + end * alongWay
951 def getIntersectionOfXIntersectionIndexes( totalSolidSurfaceThickness, xIntersectionIndexList ):
952 'Get x intersections from surrounding layers.'
953 xIntersectionList = []
956 xIntersectionIndexList.sort()
957 for xIntersectionIndex in xIntersectionIndexList:
958 toggleHashtable(solidTable, xIntersectionIndex.index, '')
960 solid = len(solidTable) >= totalSolidSurfaceThickness
961 if oldSolid != solid:
962 xIntersectionList.append(xIntersectionIndex.x)
963 return xIntersectionList
965 def getIntersectionOfXIntersectionsTables(xIntersectionsTables):
966 'Get the intersection of the XIntersections tables.'
967 if len(xIntersectionsTables) == 0:
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
982 def getIntFromValue(value):
983 'Get the value as an int.'
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
994 def getIsInFilledRegionByPaths(loops, paths):
995 'Determine if the point of any path is in the filled region of the loops.'
998 if getIsInFilledRegion(loops, path[0]):
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
1006 def getIsWiddershinsByVector3( polygon ):
1007 'Determine if the polygon goes round in the widdershins direction.'
1008 return isWiddershins( getComplexPath( polygon ) )
1010 def getJoinOfXIntersectionIndexes( xIntersectionIndexList ):
1011 'Get joined x intersections from surrounding layers.'
1015 xIntersectionIndexList.sort()
1016 for xIntersectionIndex in xIntersectionIndexList:
1017 toggleHashtable(solidTable, xIntersectionIndex.index, '')
1019 solid = len(solidTable) > 0
1020 if oldSolid != solid:
1021 xIntersections.append(xIntersectionIndex.x)
1022 return xIntersections
1024 def getLargestLoop(loops):
1025 'Get largest loop from loops.'
1026 largestArea = -987654321.0
1029 loopArea = abs(getAreaLoopAbsolute(loop))
1030 if loopArea > largestArea:
1031 largestArea = loopArea
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
1045 def getLeftPointIndex(points):
1046 'Get the index of the leftmost complex point in the points.'
1050 for pointIndex in xrange( len(points) ):
1051 if points[pointIndex].real < points[ leftPointIndex ].real:
1052 leftPointIndex = pointIndex
1053 return leftPointIndex
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
1062 def getLoopCentroid(polygonComplex):
1063 'Get the area of a complex polygon using http://en.wikipedia.org/wiki/Centroid.'
1064 polygonDoubleArea = 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
1076 def getLoopConvex(points):
1077 'Get convex hull of points using gift wrap algorithm.'
1080 for point in points:
1081 if point not in pointSet:
1083 loopConvex.append(point)
1084 if len(loopConvex) < 4:
1086 leftPoint = getLeftPoint(loopConvex)
1087 lastPoint = leftPoint
1088 pointSet.remove(leftPoint)
1089 loopConvex = [leftPoint]
1090 lastSegment = complex(0.0, 1.0)
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:
1109 lastPoint = greatestPoint
1110 loopConvex.append(greatestPoint)
1111 pointSet.remove(greatestPoint)
1112 lastSegment = greatestSegment
1115 def getLoopConvexCentroid(polygonComplex):
1116 'Get centroid of the convex hull of a complex polygon.'
1117 return getLoopCentroid( getLoopConvex(polygonComplex) )
1119 def getLoopInsideContainingLoop( containingLoop, loops ):
1120 'Get a loop that is inside the containing loop.'
1122 if loop != containingLoop:
1123 if isPathInsideLoop( containingLoop, loop ):
1127 def getLoopLength( polygon ):
1128 'Get the length of a polygon perimeter.'
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
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]]
1147 def getLoopWithoutCloseEnds(close, loop):
1148 'Get loop without close ends.'
1151 if abs(loop[0] - loop[-1]) > close:
1155 def getLoopWithoutCloseSequentialPoints(close, loop):
1156 'Get loop without close sequential points.'
1159 lastPoint = loop[-1]
1160 loopWithoutCloseSequentialPoints = []
1162 if abs(point - lastPoint) > close:
1163 loopWithoutCloseSequentialPoints.append(point)
1165 return loopWithoutCloseSequentialPoints
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))
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)
1175 maximum = getMaximum(maximum, point)
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)
1183 maximum = getMaximum(maximum, point)
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)
1190 maximum.maximize(point)
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)
1198 maximum.maximize(point)
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)
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))
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)
1214 minimum = getMinimum(minimum, point)
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)
1222 minimum = getMinimum(minimum, point)
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)
1229 minimum.minimize(point)
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)
1237 minimum.minimize(point)
1240 def getMirrorPath(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)
1250 def getNormal(begin, center, end):
1252 centerMinusBegin = (center - begin).getNormalized()
1253 endMinusCenter = (end - center).getNormalized()
1254 return centerMinusBegin.cross(endMinusCenter)
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()
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
1272 def getNormalWeighted(begin, center, end):
1273 'Get weighted normal.'
1274 return (center - begin).cross(end - center)
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
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
1292 totalNumberOfIntersectionsToLeft += getNumberOfIntersectionsToLeft(loop, point)
1293 return totalNumberOfIntersectionsToLeft
1295 def getOrderedNestedRings(nestedRings):
1296 'Get ordered nestedRings from nestedRings.'
1298 orderedNestedRings = []
1299 for loopIndex in xrange(len(nestedRings)):
1300 nestedRing = nestedRings[loopIndex]
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)
1309 orderedNestedRings.append(nestedRing)
1310 for outside in orderedNestedRings:
1311 outside.getFromInsideSurroundings(insides)
1312 return orderedNestedRings
1314 def getPathCopy(path):
1318 pathCopy.append(point.copy())
1321 def getPathLength(path):
1322 'Get the length of a path ( an open polyline ).'
1324 for pointIndex in xrange( len(path) - 1 ):
1325 firstPoint = path[pointIndex]
1326 secondPoint = path[pointIndex + 1]
1327 pathLength += abs(firstPoint - secondPoint)
1330 def getPathsFromEndpoints(endpoints, maximumConnectionLength, pixelDictionary, sharpestProduct, width):
1331 'Get paths from endpoints.'
1332 if len(endpoints) < 2:
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)
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
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:
1361 endpoints = getSquareValuesFromPoint(endpointTable, otherEndpoint.point * oneOverEndpointWidth)
1362 nextEndpoint = otherEndpoint.getClosestMiss(endpoints, path, pixelDictionary, sharpestProduct, width)
1363 if nextEndpoint == None:
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:
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)
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
1389 def getPluralString( number, suffix ):
1390 'Get the plural string.'
1392 return '1 %s' % suffix
1393 return '%s %ss' % ( number, suffix )
1395 def getPointPlusSegmentWithLength( length, point, segment ):
1396 'Get point plus a segment scaled to a given length.'
1397 return segment * length / abs(segment) + point
1399 def getPointsByHorizontalDictionary(width, xIntersectionsDictionary):
1400 'Get points from the horizontalXIntersectionsDictionary.'
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))
1409 def getPointsByVerticalDictionary(width, xIntersectionsDictionary):
1410 'Get points from the verticalXIntersectionsDictionary.'
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))
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))
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)
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)))
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
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
1446 def getRotatedWiddershinsQuarterAroundZAxis(vector3):
1447 'Get Vector3 rotated a quarter widdershins turn around Z axis.'
1448 return Vector3(-vector3.y, vector3.x, vector3.z)
1450 def getRoundedPoint(point):
1451 'Get point with each component rounded.'
1452 return Vector3(round(point.x), round( point.y ), round(point.z))
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)
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
1467 def getRoundedToThreePlaces(number):
1468 'Get number rounded to three places as a string.'
1469 return str(round(number, 3))
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 )
1475 def getSegmentFromPath( path, pathIndex ):
1476 'Get endpoint segment from a path.'
1481 forwardEndpoint = getEndpointFromPath( path, pathIndex )
1482 reversePath = path[:]
1483 reversePath.reverse()
1484 reverseEndpoint = getEndpointFromPath( reversePath, pathIndex )
1485 return ( forwardEndpoint, reverseEndpoint )
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 )
1494 def getSegmentsFromXIntersectionIndexes( xIntersectionIndexList, y ):
1495 'Get endpoint segments from the x intersection indexes.'
1496 xIntersections = getXIntersectionsFromIntersections( xIntersectionIndexList )
1497 return getSegmentsFromXIntersections( xIntersections, y )
1499 def getSegmentsFromXIntersections( xIntersections, y ):
1500 'Get endpoint segments from the x intersections.'
1502 end = len( xIntersections )
1503 if len( xIntersections ) % 2 == 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 ) ) )
1512 def getSimplifiedLoop( loop, radius ):
1513 'Get loop with points inside the channel removed.'
1516 simplificationMultiplication = 256
1517 simplificationRadius = radius / float( simplificationMultiplication )
1518 maximumIndex = len(loop) * simplificationMultiplication
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 )
1529 simplificationRadius *= 1.5
1530 simplificationRadius = min( simplificationRadius, radius )
1531 pointIndex += pointIndex
1532 return getAwayPoints( loop, radius )
1534 def getSimplifiedLoops( loops, radius ):
1535 'Get the simplified loops.'
1536 simplifiedLoops = []
1538 simplifiedLoops.append( getSimplifiedLoop( loop, radius ) )
1539 return simplifiedLoops
1541 def getSimplifiedPath(path, radius):
1542 'Get path with points inside the channel removed.'
1545 simplificationMultiplication = 256
1546 simplificationRadius = radius / float(simplificationMultiplication)
1547 maximumIndex = len(path) * simplificationMultiplication
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)
1558 simplificationRadius *= 1.5
1559 simplificationRadius = min(simplificationRadius, radius)
1560 pointIndex += pointIndex
1561 return getAwayPath(path, radius)
1563 def getSquareIsOccupied( pixelDictionary, x, y ):
1564 'Determine if a square around the x and y pixel coordinates is occupied.'
1566 for xStep in xrange(x - 1, x + 2):
1567 for yStep in xrange(y - 1, y + 2):
1568 if (xStep, yStep) in pixelDictionary:
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))
1578 def getSquareValues( pixelDictionary, x, y ):
1579 'Get a list of the values in a square around the x and y pixel coordinates.'
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 ]
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)))
1592 def getStepKeyFromPoint(point):
1593 'Get step key for the point.'
1594 return (int(round(point.real)), int(round(point.imag)))
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 )
1605 def getTopPath(path):
1606 'Get the top of the path.'
1607 top = -987654321987654321.0
1609 top = max(top, point.z)
1612 def getTopPaths(paths):
1613 'Get the top of the paths.'
1614 top = -987654321987654321.0
1617 top = max(top, point.z)
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
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
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
1655 def getTranslatedComplexPath(path, translateComplex):
1656 'Get the translated complex path.'
1657 translatedComplexPath = []
1659 translatedComplexPath.append(point + translateComplex)
1660 return translatedComplexPath
1662 def getVector3Path(complexPath, z=0.0):
1663 'Get the vector3 path from the complex path.'
1665 for complexPoint in complexPath:
1666 vector3Path.append(Vector3(complexPoint.real, complexPoint.imag, z))
1669 def getVector3Paths(complexPaths, z=0.0):
1670 'Get the vector3 paths from the complex paths.'
1672 for complexPath in complexPaths:
1673 vector3Paths.append(getVector3Path(complexPath, z))
1676 def getWiddershinsUnitPolar(angle):
1677 'Get polar complex from counterclockwise angle from 1, 0.'
1678 return complex(math.cos(angle), math.sin(angle))
1680 def getXIntersectionIfExists( beginComplex, endComplex, y ):
1681 'Get the x intersection if it exists.'
1682 if ( y > beginComplex.imag ) == ( y > endComplex.imag ):
1684 endMinusBeginComplex = endComplex - beginComplex
1685 return ( y - beginComplex.imag ) / endMinusBeginComplex.imag * endMinusBeginComplex.real + beginComplex.real
1687 def getXIntersectionsFromIntersections( xIntersectionIndexList ):
1688 'Get x intersections from the x intersection index list, in other words subtract non negative intersections from negatives.'
1693 xIntersectionIndexList.sort()
1694 for solidX in xIntersectionIndexList:
1695 if solidX.index >= 0:
1696 toggleHashtable( solidTable, solidX.index, '' )
1700 solid = ( len( solidTable ) == 0 and fill )
1701 if oldSolid != solid:
1702 xIntersections.append( solidX.x )
1703 return xIntersections
1705 def getXYComplexFromVector3(vector3):
1706 'Get an xy complex from a vector3 if it exists, otherwise return None.'
1709 return vector3.dropAxis()
1711 def getYIntersectionIfExists( beginComplex, endComplex, x ):
1712 'Get the y intersection if it exists.'
1713 if ( x > beginComplex.real ) == ( x > endComplex.real ):
1715 endMinusBeginComplex = endComplex - beginComplex
1716 return ( x - beginComplex.real ) / endMinusBeginComplex.real * endMinusBeginComplex.imag + beginComplex.imag
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
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] )
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:
1731 if xIntersection < min( segmentFirstX, segmentSecondX ):
1733 return xIntersection <= max( segmentFirstX, segmentSecondX )
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 ):
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 ):
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 ):
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 ):
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 ):
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 :]):
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 ):
1804 def isPathEntirelyInsideLoop(loop, path):
1805 'Determine if a path is entirely inside another loop.'
1807 if not isPointInsideLoop(loop, point):
1811 def isPathEntirelyInsideLoops(loops, path):
1812 'Determine if a path is entirely inside another loop in a list.'
1814 if isPathEntirelyInsideLoop(loop, path):
1818 def isPathInsideLoop(loop, path):
1819 'Determine if a path is inside another loop.'
1820 return isPointInsideLoop(loop, getLeftPoint(path))
1822 def isPathInsideLoops(loops, path):
1823 'Determine if a path is inside another loop in a list.'
1825 if isPathInsideLoop(loop, path):
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:
1838 def isPointInsideLoop(loop, point):
1839 'Determine if a point is inside another loop.'
1840 return getNumberOfIntersectionsToLeft(loop, point) % 2 == 1
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 ):
1848 return min( segmentFirstX, segmentSecondX ) >= min( xFirst, xSecond )
1850 def isWiddershins(polygonComplex):
1851 'Determine if the complex polygon goes round in the widdershins direction.'
1852 return getAreaLoop(polygonComplex) > 0.0
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:
1861 aheadSegmentComplex = loop[(pointIndex + 1) % len(loop)] - point
1862 aheadSegmentComplexLength = abs( aheadSegmentComplex )
1863 if aheadSegmentComplexLength < channelRadius:
1865 behindSegmentComplex /= behindSegmentComplexLength
1866 aheadSegmentComplex /= aheadSegmentComplexLength
1867 absoluteZ = getDotProductPlusOne( aheadSegmentComplex, behindSegmentComplex )
1868 if behindSegmentComplexLength * absoluteZ < channelRadius:
1870 return aheadSegmentComplexLength * absoluteZ < channelRadius
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 ):
1882 def isXSegmentIntersectingPaths( paths, segmentFirstX, segmentSecondX, segmentYMirror, y ):
1883 'Determine if a path list is crossing inside the x segment.'
1885 if isXSegmentIntersectingPath( path, segmentFirstX, segmentSecondX, segmentYMirror, y ):
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()
1894 concatenatedTableKeys = intoTableKeys + fromTableKeys
1895 for concatenatedTableKey in concatenatedTableKeys:
1896 joinedKeyTable[ concatenatedTableKey ] = None
1897 joinedKeys = joinedKeyTable.keys()
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
1910 print('This should never happen, there are no line segments in joinSegments in euclidean')
1912 def joinXIntersectionsTables( fromTable, intoTable ):
1913 'Join both XIntersections tables and put the join into the intoTable.'
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
1928 print('This should never happen, there are no line segments in joinSegments in euclidean')
1930 def overwriteDictionary(fromDictionary, keys, toDictionary):
1931 'Overwrite the dictionary.'
1933 if key in fromDictionary:
1934 toDictionary[key] = fromDictionary[key]
1936 def removeElementFromDictionary(dictionary, key):
1937 'Remove element from the dictionary.'
1938 if key in dictionary:
1941 def removeElementFromListTable(element, key, listDictionary):
1942 'Remove an element from the list table.'
1943 if key not in listDictionary:
1945 elementList = listDictionary[key]
1946 if len( elementList ) < 2:
1947 del listDictionary[key]
1949 if element in elementList:
1950 elementList.remove(element)
1952 def removeElementFromPixelListFromPoint( element, pixelDictionary, point ):
1953 'Remove an element from the pixel list.'
1954 stepKey = getStepKeyFromPoint(point)
1955 removeElementFromListTable( element, stepKey, pixelDictionary )
1957 def removeElementsFromDictionary(dictionary, keys):
1958 'Remove list from the dictionary.'
1960 removeElementFromDictionary(dictionary, key)
1962 def removePixelTableFromPixelTable( pixelDictionaryToBeRemoved, pixelDictionaryToBeRemovedFrom ):
1963 'Remove pixel from the pixel table.'
1964 removeElementsFromDictionary( pixelDictionaryToBeRemovedFrom, pixelDictionaryToBeRemoved.keys() )
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 ):
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]):
1978 def removeTrueListFromDictionary( dictionary, keys ):
1979 'Remove list from the dictionary in the value is true.'
1981 removeTrueFromDictionary( dictionary, key )
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
1996 del subtractFromTable[ subtractFromTableKey ]
1998 def swapList( elements, indexBegin, indexEnd ):
1999 'Swap the list elements.'
2000 elements[ indexBegin ], elements[ indexEnd ] = elements[ indexEnd ], elements[ indexBegin ]
2002 def toggleHashtable( hashtable, key, value ):
2003 'Toggle a hashtable between having and not having a key.'
2004 if key in hashtable:
2007 hashtable[key] = value
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)
2025 def transferClosestPath( oldOrderedLocation, remainingPaths, skein ):
2026 'Transfer the closest remaining path.'
2027 closestDistance = 987654321987654321.0
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
2040 def transferClosestPaths(oldOrderedLocation, remainingPaths, skein):
2041 'Transfer the closest remaining paths.'
2042 while len(remainingPaths) > 0:
2043 transferClosestPath(oldOrderedLocation, remainingPaths, skein)
2045 def transferPathsToNestedRings(nestedRings, paths):
2046 'Transfer paths to nested rings.'
2047 for nestedRing in nestedRings:
2048 nestedRing.transferPaths(paths)
2050 def translateVector3Path(path, translateVector3):
2051 'Translate the vector3 path.'
2053 point.setToVector3(point + translateVector3)
2055 def translateVector3Paths(paths, translateVector3):
2056 'Translate the vector3 paths.'
2058 translateVector3Path(path, translateVector3)
2060 def unbuckleBasis( basis, maximumUnbuckling, normal ):
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 )
2070 class DistanceIndex:
2071 'A class to hold the distance and the index of the loop.'
2072 def __init__(self, distance, index):
2074 self.distance = distance
2078 'Get the string representation of this distance index.'
2079 return '%s, %s' % (self.distance, self.index)
2083 'The endpoint of a segment.'
2085 'Get the string representation of this Endpoint.'
2086 return 'Endpoint %s, %s' % ( self.point, self.otherEndpoint.point )
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
2099 def getClosestMiss(self, endpoints, path, pixelDictionary, sharpestProduct, width):
2100 'Get the closest endpoint which the segment to that endpoint misses the other extrusions.'
2102 smallestDistance = 987654321.0
2103 penultimateMinusPoint = complex(0.0, 0.0)
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:
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:
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)
2130 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2131 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
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.'
2138 smallestDistance = 987654321.0
2139 penultimateMinusPoint = complex(0.0, 0.0)
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:
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:
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)
2173 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2174 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
2178 def getFromOtherPoint( self, otherEndpoint, point ):
2179 'Initialize from other endpoint.'
2180 self.otherEndpoint = otherEndpoint
2187 def __init__(self, z):
2193 'Get the string representation of this loop layer.'
2194 return '%s, %s' % (self.z, self.loops)
2202 self.innerNestedRings = None
2205 'Get the string representation of this nested ring.'
2206 return str(self.__dict__)
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)
2214 def getFromInsideSurroundings(self, inputSurroundingInsides):
2215 'Initialize from inside nested rings.'
2216 transferredSurroundings = getTransferredNestedRings(inputSurroundingInsides, self.boundary)
2217 self.innerNestedRings = getOrderedNestedRings(transferredSurroundings)
2221 class NestedBand(NestedRing):
2222 'A loop that surrounds paths.'
2225 NestedRing.__init__(self)
2227 self.extraLoops = []
2228 self.infillBoundaries = []
2229 self.infillPaths = []
2230 # self.lastExistingFillLoops = None
2231 self.lastFillLoops = None
2233 self.penultimateFillLoops = []
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'
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>)')
2256 addToThreadsFromLoop(extrusionHalfWidth, 'edge', self.loop[:], oldOrderedLocation, skein)
2257 skein.distanceFeedRate.addLine('(</boundaryPerimeter>)')
2258 addToThreadsRemove(extrusionHalfWidth, self.innerNestedRings[:], oldOrderedLocation, skein, threadSequence)
2260 def addToBoundary(self, vector3):
2261 'Add vector3 to boundary.'
2262 self.boundary.append(vector3.dropAxis())
2265 def addToLoop(self, vector3):
2266 'Add vector3 to loop.'
2267 if self.loop == None:
2269 self.loop.append(vector3.dropAxis())
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>)')
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()
2286 if penultimateFillLoops == None:
2287 penultimateFillLoops = self.penultimateFillLoops
2288 if penultimateFillLoops == None:
2289 print('Warning, penultimateFillLoops == None in getFillLoops in NestedBand in euclidean.')
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)
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
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
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
2321 def transferClosestFillLoops(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2322 'Transfer closest fill loops.'
2323 if len( self.extraLoops ) < 1:
2325 remainingFillLoops = self.extraLoops[:]
2326 while len( remainingFillLoops ) > 0:
2327 transferClosestFillLoop(extrusionHalfWidth, oldOrderedLocation, remainingFillLoops, skein)
2329 def transferInfillPaths(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2330 'Transfer the infill paths.'
2331 if len(self.infillBoundaries) == 0 and len(self.infillPaths) == 0:
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>)')
2343 def transferPaths(self, paths):
2345 for nestedRing in self.innerNestedRings:
2346 transferPathsToNestedRings(nestedRing.innerNestedRings, paths)
2347 self.infillPaths = getTransferredPaths(paths, self.boundary)
2351 'Complex path with a z.'
2352 def __init__( self, z ):
2357 'Get the string representation of this path z.'
2358 return '%s, %s' % ( self.z, self.path )
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
2370 'Get the string representation of this ProjectivePlane.'
2371 return '%s, %s, %s' % ( self.basisX, self.basisY, self.basisZ )
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()
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()
2391 def getByBasisZTop(self, basisZ, top):
2392 'Get by basisZ and top.'
2393 return self.getByBasisXZ(top.cross(basisZ), basisZ)
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 )
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)
2411 def getComplexByComplex( self, pointComplex ):
2412 'Get complex by complex point.'
2413 return self.basisX.dropAxis() * pointComplex.real + self.basisY.dropAxis() * pointComplex.imag
2417 return ProjectiveSpace( self.basisX, self.basisY, self.basisZ )
2419 def getDotComplex(self, point):
2420 'Get the dot complex.'
2421 return complex( point.dot(self.basisX), point.dot(self.basisY) )
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))
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:
2434 if dotNext < - 0.999999:
2435 nextSpace.basisX = - nextSpace.basisX
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()
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
2455 def getVector3ByPoint(self, point):
2456 'Get vector3 by point.'
2457 return self.basisX * point.x + self.basisY * point.y + self.basisZ * point.z
2459 def normalize(self):
2461 self.basisX.normalize()
2462 self.basisY.normalize()
2463 self.basisZ.normalize()
2465 def unbuckle( self, maximumUnbuckling, normal ):
2467 unbuckleBasis( self.basisX, maximumUnbuckling, normal )
2468 unbuckleBasis( self.basisY, maximumUnbuckling, normal )
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 ):
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:
2482 return int( self.x > other.x )
2484 def __eq__(self, other):
2485 'Determine whether this XIntersectionIndex is identical to other one.'
2488 if other.__class__ != self.__class__:
2490 return self.index == other.index and self.x == other.x
2492 def __ne__(self, other):
2493 'Determine whether this XIntersectionIndex is not identical to other one.'
2494 return not self.__eq__(other)
2497 'Get the string representation of this x intersection.'
2498 return 'XIntersectionIndex index %s; x %s ' % ( self.index, self.x )