1 """
2 Euclidean is a collection of python utilities for complex numbers, paths, polygons & Vector3s.
3
4 To use euclidean, install python 2.x on your machine, which is avaliable from http://www.python.org/download/
5
6 Then in the folder which euclidean is in, type 'python' in a shell to run the python interpreter. Finally type 'import euclidean' to import these utilities and 'from vector3 import Vector3' to import the Vector3 class.
7
8
9 Below are examples of euclidean use.
10
11 >>> from euclidean import *
12 >>> origin=complex()
13 >>> right=complex(1.0,0.0)
14 >>> back=complex(0.0,1.0)
15 >>> getMaximum(right,back)
16 1.0, 1.0
17 >>> polygon=[origin, right, back]
18 >>> getLoopLength(polygon)
19 3.4142135623730949
20 >>> getAreaLoop(polygon)
21 0.5
22 """
23
24 from fabmetheus_utilities.vector3 import Vector3
25 from fabmetheus_utilities import xml_simple_writer
26 import StringIO
27 import math
28 import random
29
30
31 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
32 __date__ = '$Date: 2008/21/04 $'
33 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
34
35
36 globalGoldenAngle = 3.8832220774509332
37 globalGoldenRatio = 1.6180339887498948482045868
38 globalTau = math.pi + math.pi
39
41 xyTravel = abs(targetPoint.dropAxis())
42 zTravelMultiplied = targetPoint.z * zDistanceRatio
43 timeToNextThread = math.sqrt(xyTravel * xyTravel + zTravelMultiplied * zTravelMultiplied) / feedRateMinute * 60
44 return timeToNextThread * abs(oozeRate) / 60
45
47 'Add an element to the list table.'
48 if key in listDictionary:
49 listDictionary[key].append(element)
50 else:
51 listDictionary[key] = [element]
52
54 'Add the value to the lists.'
55 if key in listDictionary:
56 elements = listDictionary[key]
57 if element not in elements:
58 elements.append(element)
59 else:
60 listDictionary[key] = [element]
61
65
67 'Add an element to the pixel list.'
68 addElementToPixelList(element, pixelDictionary, int(round(point.real)), int(round(point.imag)))
69
71 'Add point if it is within the horizontal bounds.'
72 if center.real >= horizontalEnd and center.real <= horizontalBegin:
73 path.append(center)
74 return
75 if end != None:
76 if center.real > horizontalBegin and end.real <= horizontalBegin:
77 centerMinusEnd = center - end
78 along = (center.real - horizontalBegin) / centerMinusEnd.real
79 path.append(center - along * centerMinusEnd)
80 return
81 if begin != None:
82 if center.real < horizontalEnd and begin.real >= horizontalEnd:
83 centerMinusBegin = center - begin
84 along = (center.real - horizontalEnd) / centerMinusBegin.real
85 path.append(center - along * centerMinusBegin)
86
88 'Add a list to the list table.'
89 if key in listDictionary:
90 listDictionary[key] += elementList
91 else:
92 listDictionary[key] = elementList
93
95 'Add loop to the pixel table.'
96 for pointIndex in xrange(len(loop)):
97 pointBegin = loop[pointIndex]
98 pointEnd = loop[(pointIndex + 1) % len(loop)]
99 addValueSegmentToPixelTable(pointBegin, pointEnd, pixelDictionary, None, width)
100
102 'Add path to the pixel table.'
103 for pointIndex in xrange(len(path) - 1):
104 pointBegin = path[pointIndex]
105 pointEnd = path[pointIndex + 1]
106 addValueSegmentToPixelTable(pointBegin, pointEnd, pixelDictionary, value, width)
107
109 'Add from pixel table to the into pixel table.'
110 for fromPixelTableKey in fromPixelTable.keys():
111 intoPixelTable[ fromPixelTableKey ] = fromPixelTable[ fromPixelTableKey ]
112
114 'Add pixels to the pixel table with steepness.'
115 if isSteep:
116 pixelDictionary[(y, x)] = value
117 else:
118 pixelDictionary[(x, y)] = value
119
127
128 -def addSegmentToPixelTable(beginComplex, endComplex, pixelDictionary, shortenDistanceBegin, shortenDistanceEnd, width):
129 'Add line segment to the pixel table.'
130 if abs(beginComplex - endComplex) <= 0.0:
131 return
132 beginComplex /= width
133 endComplex /= width
134 if shortenDistanceBegin > 0.0:
135 endMinusBeginComplex = endComplex - beginComplex
136 endMinusBeginComplexLength = abs(endMinusBeginComplex)
137 if endMinusBeginComplexLength < shortenDistanceBegin:
138 return
139 beginComplex = beginComplex + endMinusBeginComplex * shortenDistanceBegin / endMinusBeginComplexLength
140 if shortenDistanceEnd > 0.0:
141 beginMinusEndComplex = beginComplex - endComplex
142 beginMinusEndComplexLength = abs(beginMinusEndComplex)
143 if beginMinusEndComplexLength < 0.0:
144 return
145 endComplex = endComplex + beginMinusEndComplex * shortenDistanceEnd / beginMinusEndComplexLength
146 deltaX = endComplex.real - beginComplex.real
147 deltaY = endComplex.imag - beginComplex.imag
148 isSteep = abs(deltaY) > abs(deltaX)
149 if isSteep:
150 beginComplex = complex(beginComplex.imag, beginComplex.real)
151 endComplex = complex(endComplex.imag, endComplex.real)
152 if beginComplex.real > endComplex.real:
153 endComplex, beginComplex = beginComplex, endComplex
154 deltaX = endComplex.real - beginComplex.real
155 deltaY = endComplex.imag - beginComplex.imag
156 if deltaX > 0.0:
157 gradient = deltaY / deltaX
158 else:
159 gradient = 0.0
160 print('This should never happen, deltaX in addSegmentToPixelTable in euclidean is 0.')
161 print(beginComplex)
162 print(endComplex)
163 print(shortenDistanceBegin)
164 print(shortenDistanceEnd)
165 print(width)
166 xBegin = int(round(beginComplex.real))
167 xEnd = int(round(endComplex.real))
168 yIntersection = beginComplex.imag - beginComplex.real * gradient
169 if isSteep:
170 pixelDictionary[( int( round( beginComplex.imag ) ), xBegin)] = None
171 pixelDictionary[( int( round( endComplex.imag ) ), xEnd )] = None
172 for x in xrange( xBegin + 1, xEnd ):
173 y = int( math.floor( yIntersection + x * gradient ) )
174 pixelDictionary[(y, x)] = None
175 pixelDictionary[(y + 1, x)] = None
176 else:
177 pixelDictionary[(xBegin, int( round( beginComplex.imag ) ) )] = None
178 pixelDictionary[(xEnd, int( round( endComplex.imag ) ) )] = None
179 for x in xrange( xBegin + 1, xEnd ):
180 y = int( math.floor( yIntersection + x * gradient ) )
181 pixelDictionary[(x, y)] = None
182 pixelDictionary[(x, y + 1)] = None
183
185 'Add square with two pixels around the center to pixel dictionary.'
186 point /= width
187 x = int(round(point.real))
188 y = int(round(point.imag))
189 for xStep in xrange(x - 2, x + 3):
190 for yStep in xrange(y - 2, y + 3):
191 pixelDictionary[(xStep, yStep)] = value
192
194 'Add surrounding loop beginning to gcode output.'
195 distanceFeedRate.addLine('(<nestedRing>)')
196 distanceFeedRate.addLine('(<boundaryPerimeter>)')
197 for point in loop:
198 pointVector3 = Vector3(point.real, point.imag, z)
199 distanceFeedRate.addLine(distanceFeedRate.getBoundaryLine(pointVector3))
200
202 'Add to threads from the last location from loop.'
203 loop = getLoopStartingNearest(extrusionHalfWidth, oldOrderedLocation.dropAxis(), loop)
204 oldOrderedLocation.x = loop[0].real
205 oldOrderedLocation.y = loop[0].imag
206 gcodeTypeStart = gcodeType
207 if isWiddershins(loop):
208 skein.gcodeCodec.addLine('(<%s> outer )' % gcodeType)
209 else:
210 skein.gcodeCodec.addLine('(<%s> inner )' % gcodeType)
211 nestedRing.addGcodeFromThread(loop + [loop[0]])
212 skein.gcodeCodec.addLine('(</%s>)' % gcodeType)
213
214 -def addToThreadsRemove(extrusionHalfWidth, nestedRings, oldOrderedLocation, threadSequence):
215 'Add to threads from the last location from surrounding loops.'
216
217
218 for nestedRing in nestedRings:
219 nestedRing.addToThreads(extrusionHalfWidth, oldOrderedLocation, threadSequence)
220
222 'Add line segment to the pixel table.'
223 if abs(beginComplex - endComplex) <= 0.0:
224 return
225 beginComplex /= width
226 endComplex /= width
227 deltaX = endComplex.real - beginComplex.real
228 deltaY = endComplex.imag - beginComplex.imag
229 isSteep = abs(deltaY) > abs(deltaX)
230 if isSteep:
231 beginComplex = complex(beginComplex.imag, beginComplex.real)
232 endComplex = complex(endComplex.imag, endComplex.real)
233 if beginComplex.real > endComplex.real:
234 endComplex, beginComplex = beginComplex, endComplex
235 deltaX = endComplex.real - beginComplex.real
236 deltaY = endComplex.imag - beginComplex.imag
237 if deltaX > 0.0:
238 gradient = deltaY / deltaX
239 else:
240 gradient = 0.0
241 print('This should never happen, deltaX in addValueSegmentToPixelTable in euclidean is 0.')
242 print(beginComplex)
243 print(value)
244 print(endComplex)
245 print(width)
246 xBegin = int(round(beginComplex.real))
247 xEnd = int(round(endComplex.real))
248 yIntersection = beginComplex.imag - beginComplex.real * gradient
249 if isSteep:
250 pixelDictionary[(int( round( beginComplex.imag ) ), xBegin)] = value
251 pixelDictionary[(int( round( endComplex.imag ) ), xEnd)] = value
252 for x in xrange( xBegin + 1, xEnd ):
253 y = int( math.floor( yIntersection + x * gradient ) )
254 pixelDictionary[(y, x)] = value
255 pixelDictionary[(y + 1, x)] = value
256 else:
257 pixelDictionary[(xBegin, int( round( beginComplex.imag ) ))] = value
258 pixelDictionary[(xEnd, int( round( endComplex.imag ) ))] = value
259 for x in xrange( xBegin + 1, xEnd ):
260 y = int( math.floor( yIntersection + x * gradient ) )
261 pixelDictionary[(x, y)] = value
262 pixelDictionary[(x, y + 1)] = value
263
265 'Add value to the output.'
266 depthStart = ' ' * depth
267 output.write('%s%s:' % (depthStart, keyInput))
268 if value.__class__ == dict:
269 output.write('\n')
270 keys = value.keys()
271 keys.sort()
272 for key in keys:
273 addValueToOutput(depth + 1, key, output, value[key])
274 return
275 if value.__class__ == list:
276 output.write('\n')
277 for elementIndex, element in enumerate(value):
278 addValueToOutput(depth + 1, elementIndex, output, element)
279 return
280 output.write(' %s\n' % value)
281
283 'Add the x intersection indexes for a loop.'
284 for pointIndex in xrange(len(loop)):
285 pointBegin = loop[pointIndex]
286 pointEnd = loop[(pointIndex + 1) % len(loop)]
287 if pointBegin.imag > pointEnd.imag:
288 pointOriginal = pointBegin
289 pointBegin = pointEnd
290 pointEnd = pointOriginal
291 fillBegin = int(math.ceil(pointBegin.imag / width - frontOverWidth))
292 fillBegin = max(0, fillBegin)
293 fillEnd = int(math.ceil(pointEnd.imag / width - frontOverWidth))
294 fillEnd = min(len(xIntersectionIndexLists), fillEnd)
295 if fillEnd > fillBegin:
296 secondMinusFirstComplex = pointEnd - pointBegin
297 secondMinusFirstImaginaryOverReal = secondMinusFirstComplex.real / secondMinusFirstComplex.imag
298 beginRealMinusImaginary = pointBegin.real - pointBegin.imag * secondMinusFirstImaginaryOverReal
299 for fillLine in xrange(fillBegin, fillEnd):
300 xIntersection = yList[fillLine] * secondMinusFirstImaginaryOverReal + beginRealMinusImaginary
301 xIntersectionIndexList = xIntersectionIndexLists[fillLine]
302 xIntersectionIndexList.append(XIntersectionIndex(solidIndex, xIntersection))
303
305 'Add the x intersection indexes for a loop.'
306 for loop in loops:
307 addXIntersectionIndexesFromLoop(frontOverWidth, loop, solidIndex, xIntersectionIndexLists, width, yList)
308
309
311 'Add the x intersection indexes for the loop lists.'
312 for loopListIndex in xrange(len(loopLists)):
313 loopList = loopLists[ loopListIndex ]
314 addXIntersectionIndexesFromLoopsY(loopList, loopListIndex, xIntersectionIndexList, y)
315
321 'Add the x intersection indexes for a loop.'
322 for pointIndex in xrange(len(loop)):
323 pointFirst = loop[pointIndex]
324 pointSecond = loop[(pointIndex + 1) % len(loop)]
325 xIntersection = getXIntersectionIfExists(pointFirst, pointSecond, y)
326 if xIntersection != None:
327 xIntersectionIndexList.append(XIntersectionIndex(solidIndex, xIntersection))
328
330 'Add the x intersection indexes from the segment.'
331 for endpoint in segment:
332 xIntersectionIndexList.append(XIntersectionIndex(index, endpoint.point.real))
333
338
340 'Add the x intersection indexes from the XIntersections.'
341 for xIntersection in xIntersections:
342 xIntersectionIndexList.append(XIntersectionIndex(index, xIntersection))
343
345 'Add the x intersections for a loop.'
346 for pointIndex in xrange(len(loop)):
347 pointFirst = loop[pointIndex]
348 pointSecond = loop[(pointIndex + 1) % len(loop)]
349 xIntersection = getXIntersectionIfExists(pointFirst, pointSecond, y)
350 if xIntersection != None:
351 xIntersections.append(xIntersection)
352
354 'Add the x intersections for a loop into a table.'
355 for pointIndex in xrange(len(loop)):
356 pointBegin = loop[pointIndex]
357 pointEnd = loop[(pointIndex + 1) % len(loop)]
358 if pointBegin.imag > pointEnd.imag:
359 pointOriginal = pointBegin
360 pointBegin = pointEnd
361 pointEnd = pointOriginal
362 fillBegin = int(math.ceil(pointBegin.imag / width))
363 fillEnd = int(math.ceil(pointEnd.imag / width))
364 if fillEnd > fillBegin:
365 secondMinusFirstComplex = pointEnd - pointBegin
366 secondMinusFirstImaginaryOverReal = secondMinusFirstComplex.real / secondMinusFirstComplex.imag
367 beginRealMinusImaginary = pointBegin.real - pointBegin.imag * secondMinusFirstImaginaryOverReal
368 for fillLine in xrange(fillBegin, fillEnd):
369 y = fillLine * width
370 xIntersection = y * secondMinusFirstImaginaryOverReal + beginRealMinusImaginary
371 addElementToListDictionary(xIntersection, fillLine, xIntersectionsTable)
372
374 'Add the x intersections for the loops.'
375 for loop in loops:
376 addXIntersections(loop, xIntersections, y)
377
382
384 'Get comparison in order to sort endpoints in ascending order of segment length.'
385 if endpoint.segmentLength > otherEndpoint.segmentLength:
386 return 1
387 if endpoint.segmentLength < otherEndpoint.segmentLength:
388 return -1
389 return 0
390
392 'Get connected paths from paths.'
393 bottomSegment = segments[ pathIndex ]
394 path = paths[ pathIndex ]
395 if bottomSegment == None:
396 connectedPaths.append(path)
397 return
398 endpoints = getEndpointsFromSegments(segments[ pathIndex + 1 : ])
399 bottomSegmentEndpoint = bottomSegment[0]
400 nextEndpoint = bottomSegmentEndpoint.getNearestMissCheckEndpointPath(endpoints, bottomSegmentEndpoint.path, pixelDictionary, width)
401 if nextEndpoint == None:
402 bottomSegmentEndpoint = bottomSegment[1]
403 nextEndpoint = bottomSegmentEndpoint.getNearestMissCheckEndpointPath(endpoints, bottomSegmentEndpoint.path, pixelDictionary, width)
404 if nextEndpoint == None:
405 connectedPaths.append(path)
406 return
407 if len(bottomSegmentEndpoint.path) > 0 and len(nextEndpoint.path) > 0:
408 bottomEnd = bottomSegmentEndpoint.path[-1]
409 nextBegin = nextEndpoint.path[-1]
410 nextMinusBottomNormalized = getNormalized(nextBegin - bottomEnd)
411 if len(bottomSegmentEndpoint.path) > 1:
412 bottomPenultimate = bottomSegmentEndpoint.path[-2]
413 if getDotProduct(getNormalized(bottomPenultimate - bottomEnd), nextMinusBottomNormalized) > 0.9:
414 connectedPaths.append(path)
415 return
416 if len(nextEndpoint.path) > 1:
417 nextPenultimate = nextEndpoint.path[-2]
418 if getDotProduct(getNormalized(nextPenultimate - nextBegin), -nextMinusBottomNormalized) > 0.9:
419 connectedPaths.append(path)
420 return
421 nextEndpoint.path.reverse()
422 concatenatedPath = bottomSegmentEndpoint.path + nextEndpoint.path
423 paths[ nextEndpoint.pathIndex ] = concatenatedPath
424 segments[ nextEndpoint.pathIndex ] = getSegmentFromPath(concatenatedPath, nextEndpoint.pathIndex)
425 addValueSegmentToPixelTable(bottomSegmentEndpoint.point, nextEndpoint.point, pixelDictionary, None, width)
426
428 'Get the angle around the Z axis difference between a pair of Vector3s.'
429 subtractVectorMirror = complex(subtractVec3.x , -subtractVec3.y)
430 differenceVector = getRoundZAxisByPlaneAngle(subtractVectorMirror, subtractFromVec3)
431 return math.atan2(differenceVector.y, differenceVector.x)
432
434 'Get the angle between a pair of normalized complexes.'
435 subtractComplexMirror = complex(subtractComplex.real , -subtractComplex.imag)
436 differenceComplex = subtractComplexMirror * subtractFromComplex
437 return math.atan2(differenceComplex.imag, differenceComplex.real)
438
440 'Get the area of a complex polygon.'
441 areaLoopDouble = 0.0
442 for pointIndex, point in enumerate(loop):
443 pointEnd = loop[(pointIndex + 1) % len(loop)]
444 areaLoopDouble += point.real * pointEnd.imag - pointEnd.real * point.imag
445 return 0.5 * areaLoopDouble
446
448 'Get the absolute area of a complex polygon.'
449 return abs(getAreaLoop(loop))
450
452 'Get the area of a list of complex polygons.'
453 areaLoops = 0.0
454 for loop in loops:
455 areaLoops += getAreaLoop(loop)
456 return areaLoops
457
459 'Get the area radius multiplier for the polygon.'
460 return math.sqrt(globalTau / sides / math.sin(globalTau / sides))
461
465
467 'Get an arc around a loop.'
468 aroundLoop = []
469 if end <= begin:
470 end += len(loop)
471 for pointIndex in xrange(begin, end):
472 aroundLoop.append(loop[pointIndex % len(loop)])
473 return aroundLoop
474
476 'Get a path with only the points that are far enough away from each other, except for the last point.'
477 if len(path) < 2:
478 return path
479 lastPoint = path[-1]
480 awayPath = getAwayPoints(path, radius)
481 if len(awayPath) == 0:
482 return [lastPoint]
483 if abs(lastPoint - awayPath[-1]) > 0.001 * radius:
484 awayPath.append(lastPoint)
485 return awayPath
486
488 'Get a path with only the points that are far enough away from each other.'
489 awayPoints = []
490 oneOverOverlapDistance = 1000.0 / radius
491 pixelDictionary = {}
492 for point in points:
493 x = int(point.real * oneOverOverlapDistance)
494 y = int(point.imag * oneOverOverlapDistance)
495 if not getSquareIsOccupied(pixelDictionary, x, y):
496 awayPoints.append(point)
497 pixelDictionary[(x, y)] = None
498 return awayPoints
499
501 'Get the back of the loops.'
502 negativeFloat = -987654321.75342341
503 back = negativeFloat
504 for loop in loops:
505 for point in loop:
506 back = max(back, point.imag)
507 if back == negativeFloat:
508 print('This should never happen, there are no loops for getBackOfLoops in euclidean')
509 return back
510
516
518 'Get boolean from the word.'
519 firstCharacter = str(value).lower().lstrip()[: 1]
520 return firstCharacter == 't' or firstCharacter == '1'
521
528
536
538 'Get a clipped loop path.'
539 if clip <= 0.0:
540 return loopPath
541 loopPathLength = getPathLength(loopPath)
542 clip = min(clip, 0.3 * loopPathLength)
543 lastLength = 0.0
544 pointIndex = 0
545 totalLength = 0.0
546 clippedLength = loopPathLength - clip
547 while totalLength < clippedLength and pointIndex < len(loopPath) - 1:
548 firstPoint = loopPath[pointIndex]
549 secondPoint = loopPath[pointIndex + 1]
550 pointIndex += 1
551 lastLength = totalLength
552 totalLength += abs(firstPoint - secondPoint)
553 remainingLength = clippedLength - lastLength
554 clippedLoopPath = loopPath[ : pointIndex ]
555 ultimateClippedPoint = loopPath[pointIndex]
556 penultimateClippedPoint = clippedLoopPath[-1]
557 segment = ultimateClippedPoint - penultimateClippedPoint
558 segmentLength = abs(segment)
559 if segmentLength <= 0.0:
560 return clippedLoopPath
561 newUltimatePoint = penultimateClippedPoint + segment * remainingLength / segmentLength
562 return clippedLoopPath + [newUltimatePoint]
563
565 'Get a clipped loop path.'
566 if clip <= 0.0:
567 return loopPath
568 loopPathLength = getPathLength(loopPath)
569 clip = min(clip, 0.3 * loopPathLength)
570 lastLength = 0.0
571 pointIndex = 0
572 totalLength = 0.0
573 while totalLength < clip and pointIndex < len(loopPath) - 1:
574 firstPoint = loopPath[pointIndex]
575 secondPoint = loopPath[pointIndex + 1]
576 pointIndex += 1
577 lastLength = totalLength
578 totalLength += abs(firstPoint - secondPoint)
579 remainingLength = clip - lastLength
580 clippedLoopPath = loopPath[pointIndex :]
581 ultimateClippedPoint = clippedLoopPath[0]
582 penultimateClippedPoint = loopPath[pointIndex - 1]
583 segment = ultimateClippedPoint - penultimateClippedPoint
584 segmentLength = abs(segment)
585 loopPath = clippedLoopPath
586 if segmentLength > 0.0:
587 newUltimatePoint = penultimateClippedPoint + segment * remainingLength / segmentLength
588 loopPath = [newUltimatePoint] + loopPath
589 return getClippedAtEndLoopPath(clip, loopPath)
590
594
596 'Get the commaString as a complex.'
597 try:
598 splitLine = valueCommaString.replace(',', ' ').split()
599 return complex(float(splitLine[0]), float(splitLine[1]))
600 except:
601 pass
602 return None
603
605 'Get the value as a complex.'
606 if key in dictionary:
607 return complex(dictionary[key].strip().replace('(', '').replace(')', ''))
608 return defaultComplex
609
615
617 'Get the complex by the first two words.'
618 try:
619 return complex(float(words[wordIndex]), float(words[wordIndex + 1]))
620 except:
621 pass
622 return None
623
625 'Get the complex path from the vector3 path.'
626 complexPath = []
627 for point in vector3Path:
628 complexPath.append(point.dropAxis())
629 return complexPath
630
632 'Get the multiplied complex path.'
633 complexPath = []
634 for point in path:
635 complexPath.append(multiplier * point)
636 return complexPath
637
639 'Get the complex paths from the vector3 paths.'
640 complexPaths = []
641 for vector3Path in vector3Paths:
642 complexPaths.append(getComplexPath(vector3Path))
643 return complexPaths
644
646 'Get the complex polygon.'
647 complexPolygon = []
648 sideAngle = 2.0 * math.pi / float(sides)
649 for side in xrange(abs(sides)):
650 unitPolar = getWiddershinsUnitPolar(startAngle)
651 complexPolygon.append(unitPolar * radius + center)
652 startAngle += sideAngle
653 return complexPolygon
654
656 'Get the complex polygon.'
657 complexPolygon = []
658 sideAngle = 2.0 * math.pi / float(sides)
659 for side in xrange(abs(sides)):
660 unitPolar = getWiddershinsUnitPolar(startAngle)
661 complexPolygon.append(complex(unitPolar.real * radius.real, unitPolar.imag * radius.imag))
662 startAngle += sideAngle
663 return complexPolygon
664
666 'Get the complex polygon by start and end angle.'
667 angleExtent = endAngle - startAngle
668 sideAngle = 2.0 * math.pi / float(sides)
669 sides = int(math.ceil(abs(angleExtent / sideAngle)))
670 sideAngle = angleExtent / float(sides)
671 complexPolygon = []
672 for side in xrange(abs(sides) + 1):
673 unitPolar = getWiddershinsUnitPolar(startAngle)
674 complexPolygon.append(unitPolar * radius)
675 startAngle += sideAngle
676 return getLoopWithoutCloseEnds(0.000001 * radius, complexPolygon)
677
679 'Get the lists as one concatenated list.'
680 concatenatedList = []
681 for originalList in originalLists:
682 concatenatedList += originalList
683 return concatenatedList
684
698
700 'Get z component cross product of a pair of complexes.'
701 return firstComplex.real * secondComplex.imag - firstComplex.imag * secondComplex.real
702
704 'Get decimal places carried by the decimal places of the value plus the extraDecimalPlaces.'
705 return max(0, 1 + int(math.ceil(extraDecimalPlaces - math.log10(value))))
706
708 'Get loop flipped over the dialogonal, in other words with the x and y swapped.'
709 diagonalFlippedLoop = []
710 for point in loop:
711 diagonalFlippedLoop.append(complex(point.imag, point.real))
712 return diagonalFlippedLoop
713
715 'Get loops flipped over the dialogonal, in other words with the x and y swapped.'
716 diagonalFlippedLoops = []
717 for loop in loops:
718 diagonalFlippedLoops.append(getDiagonalFlippedLoop(loop))
719 return diagonalFlippedLoops
720
729
731 'Get the distance from a vector3 point to an infinite line.'
732 pointMinusBegin = point - begin
733 if begin == end:
734 return abs(pointMinusBegin)
735 endMinusBegin = end - begin
736 return abs(endMinusBegin.cross(pointMinusBegin)) / abs(endMinusBegin)
737
739 'Get the maximum distance from a path to an infinite line.'
740 distanceToLine = -987654321.0
741 for point in path:
742 distanceToLine = max(getDistanceToLine(begin, end, point), distanceToLine)
743 return distanceToLine
744
746 'Get the maximum distance from paths to an infinite line.'
747 distanceToLine = -987654321.0
748 for path in paths:
749 distanceToLine = max(getDistanceToLineByPath(begin, end, path), distanceToLine)
750 return distanceToLine
751
753 'Get the distance squared from a point to the x & y components of a segment.'
754 segmentDifference = segmentEnd - segmentBegin
755 pointMinusSegmentBegin = point - segmentBegin
756 beginPlaneDot = getDotProduct(pointMinusSegmentBegin, segmentDifference)
757 if beginPlaneDot <= 0.0:
758 return abs(point - segmentBegin) * abs(point - segmentBegin)
759 differencePlaneDot = getDotProduct(segmentDifference, segmentDifference)
760 if differencePlaneDot <= beginPlaneDot:
761 return abs(point - segmentEnd) * abs(point - segmentEnd)
762 intercept = beginPlaneDot / differencePlaneDot
763 interceptPerpendicular = segmentBegin + segmentDifference * intercept
764 return abs(point - interceptPerpendicular) * abs(point - interceptPerpendicular)
765
767 'Get the dot product of a pair of complexes.'
768 return firstComplex.real * secondComplex.real + firstComplex.imag * secondComplex.imag
769
771 'Get the dot product plus one of the x and y components of a pair of Vector3s.'
772 return 1.0 + getDotProduct(firstComplex, secondComplex)
773
775 'Get the duration string.'
776 secondsRounded = int(round(seconds))
777 durationString = getPluralString(secondsRounded % 60, 'second')
778 if seconds < 60:
779 return durationString
780 durationString = '%s %s' % (getPluralString((secondsRounded / 60) % 60, 'minute'), durationString)
781 if seconds < 3600:
782 return durationString
783 return '%s %s' % (getPluralString(secondsRounded / 3600, 'hour'), durationString)
784
795
797 'Get endpoints from segments.'
798 endpoints = []
799 for segment in segments:
800 for endpoint in segment:
801 endpoints.append(endpoint)
802 return endpoints
803
805 'Get the endpoints from the segment table.'
806 endpoints = []
807 segmentTableKeys = segmentTable.keys()
808 segmentTableKeys.sort()
809 for segmentTableKey in segmentTableKeys:
810 for segment in segmentTable[ segmentTableKey ]:
811 for endpoint in segment:
812 endpoints.append(endpoint)
813 return endpoints
814
820
828
830 'Get enumerator keys, except when there is one argument.'
831 if len(keys) == 0:
832 return range(0, len(enumerator))
833 beginIndex = keys[0]
834 endIndex = keys[1]
835 if len(keys) == 2:
836 if beginIndex == None:
837 beginIndex = 0
838 if endIndex == None:
839 endIndex = len(enumerator)
840 return range(beginIndex, endIndex)
841 step = keys[2]
842 beginIndexDefault = 0
843 endIndexDefault = len(enumerator)
844 if step < 0:
845 beginIndexDefault = endIndexDefault - 1
846 endIndexDefault = -1
847 if beginIndex == None:
848 beginIndex = beginIndexDefault
849 if endIndex == None:
850 endIndex = endIndexDefault
851 return range(beginIndex, endIndex, step)
852
854 'Get extra fill loops of nested rings.'
855 fillOfSurroundings = []
856 for nestedRing in nestedRings:
857 fillOfSurroundings += nestedRing.getFillLoops(penultimateFillLoops)
858 return fillOfSurroundings
859
861 'Get the value as a float.'
862 evaluatedFloat = None
863 if key in dictionary:
864 evaluatedFloat = getFloatFromValue(dictionary[key])
865 if evaluatedFloat == None:
866 return defaultFloat
867 return evaluatedFloat
868
870 'Get the value as a float.'
871 try:
872 return float(value)
873 except:
874 pass
875 return None
876
887
889 'Get the front of the loops.'
890 bigFloat = 987654321.196854654
891 front = bigFloat
892 for loop in loops:
893 for point in loop:
894 front = min(front, point.imag)
895 if front == bigFloat:
896 print('This should never happen, there are no loops for getFrontOfLoops in euclidean')
897 return front
898
900 'Get the front over width and add the x intersection index lists and ylist.'
901 frontOverWidth = getFrontOverWidthAddYList(front, numberOfLines, xIntersectionIndexLists, width, yList)
902 for loopListIndex in xrange(len(loopLists)):
903 loopList = loopLists[ loopListIndex ]
904 addXIntersectionIndexesFromLoops(frontOverWidth, loopList, loopListIndex, xIntersectionIndexLists, width, yList)
905 return frontOverWidth
906
908 'Get the front over width and add the x intersection index lists and ylist.'
909 frontOverWidth = front / width
910 for fillLine in xrange(numberOfLines):
911 yList.append(front + float(fillLine) * width)
912 xIntersectionIndexLists.append([])
913 return frontOverWidth
914
916 'Get the loop with half of the points inside the channel removed.'
917 if len(loop) < 2:
918 return loop
919 channelRadius = radius * .01
920 simplified = []
921 addIndex = 0
922 if remainder == 1:
923 addIndex = len(loop) - 1
924 for pointIndex in xrange(len(loop)):
925 point = loop[pointIndex]
926 if pointIndex % 2 == remainder or pointIndex == addIndex:
927 simplified.append(point)
928 elif not isWithinChannel(channelRadius, pointIndex, loop):
929 simplified.append(point)
930 return simplified
931
933 'Get the path with half of the points inside the channel removed.'
934 if len(path) < 2:
935 return path
936 channelRadius = radius * .01
937 simplified = [path[0]]
938 for pointIndex in xrange(1, len(path) - 1):
939 point = path[pointIndex]
940 if pointIndex % 2 == remainder:
941 simplified.append(point)
942 elif not isWithinChannel(channelRadius, pointIndex, path):
943 simplified.append(point)
944 simplified.append(path[-1])
945 return simplified
946
948 'Get horizontally bounded path.'
949 horizontallyBoundedPath = []
950 for pointIndex, point in enumerate(path):
951 begin = None
952 previousIndex = pointIndex - 1
953 if previousIndex >= 0:
954 begin = path[previousIndex]
955 end = None
956 nextIndex = pointIndex + 1
957 if nextIndex < len(path):
958 end = path[nextIndex]
959 addHorizontallyBoundedPoint(begin, point, end, horizontalBegin, horizontalEnd, horizontallyBoundedPath)
960 return horizontallyBoundedPath
961
963 'Get horizontal segment lists inside loops.'
964 xIntersectionIndexLists = []
965 yList = []
966 frontOverWidth = getFrontOverWidthAddXListYList(front, alreadyFilledArounds, numberOfLines, xIntersectionIndexLists, width, yList)
967 addXIntersectionIndexesFromLoops(frontOverWidth, rotatedFillLoops, -1, xIntersectionIndexLists, width, yList)
968 horizontalSegmentLists = []
969 for xIntersectionIndexListIndex in xrange(len(xIntersectionIndexLists)):
970 xIntersectionIndexList = xIntersectionIndexLists[ xIntersectionIndexListIndex ]
971 lineSegments = getSegmentsFromXIntersectionIndexes(xIntersectionIndexList, yList[ xIntersectionIndexListIndex ])
972 horizontalSegmentLists.append(lineSegments)
973 return horizontalSegmentLists
974
976 'Get the increment from the rank which is 0 at 1 and increases by three every power of ten.'
977 rankZone = int(math.floor(rank / 3))
978 rankModulo = rank % 3
979 powerOfTen = pow(10, rankZone)
980 moduloMultipliers = (1, 2, 5)
981 return float(powerOfTen * moduloMultipliers[ rankModulo ])
982
984 'Add loops to either the insides or outsides.'
985 insides = []
986 for loopIndex in xrange(len(loops)):
987 loop = loops[loopIndex]
988 if isInsideOtherLoops(loopIndex, loops):
989 insides.append(loop)
990 else:
991 outsides.append(loop)
992 return insides
993
997
999 'Get x intersections from surrounding layers.'
1000 xIntersectionList = []
1001 solidTable = {}
1002 solid = False
1003 xIntersectionIndexList.sort()
1004 for xIntersectionIndex in xIntersectionIndexList:
1005 toggleHashtable(solidTable, xIntersectionIndex.index, '')
1006 oldSolid = solid
1007 solid = len(solidTable) >= totalSolidSurfaceThickness
1008 if oldSolid != solid:
1009 xIntersectionList.append(xIntersectionIndex.x)
1010 return xIntersectionList
1011
1013 'Get the intersection of the XIntersections tables.'
1014 if len(xIntersectionsTables) == 0:
1015 return {}
1016 intersectionOfXIntersectionsTables = {}
1017 firstIntersectionTable = xIntersectionsTables[0]
1018 for firstIntersectionTableKey in firstIntersectionTable.keys():
1019 xIntersectionIndexList = []
1020 for xIntersectionsTableIndex in xrange(len(xIntersectionsTables)):
1021 xIntersectionsTable = xIntersectionsTables[xIntersectionsTableIndex]
1022 if firstIntersectionTableKey in xIntersectionsTable:
1023 addXIntersectionIndexesFromXIntersections(xIntersectionsTableIndex, xIntersectionIndexList, xIntersectionsTable[firstIntersectionTableKey])
1024 xIntersections = getIntersectionOfXIntersectionIndexes(len(xIntersectionsTables), xIntersectionIndexList)
1025 if len(xIntersections) > 0:
1026 intersectionOfXIntersectionsTables[firstIntersectionTableKey] = xIntersections
1027 return intersectionOfXIntersectionsTables
1028
1030 'Get the value as an int.'
1031 try:
1032 return int(value)
1033 except:
1034 pass
1035 return None
1036
1040
1042 'Determine if the point of any path is in the filled region of the loops.'
1043 for path in paths:
1044 if len(path) > 0:
1045 if getIsInFilledRegion(loops, path[0]):
1046 return True
1047 return False
1048
1050 'Determine if the firstRadian is close to the secondRadian.'
1051 return abs(math.pi - abs(math.pi - ((firstRadian - secondRadian) % (math.pi + math.pi)))) < 0.000001
1052
1056
1058 'Get joined x intersections from surrounding layers.'
1059 xIntersections = []
1060 solidTable = {}
1061 solid = False
1062 xIntersectionIndexList.sort()
1063 for xIntersectionIndex in xIntersectionIndexList:
1064 toggleHashtable(solidTable, xIntersectionIndex.index, '')
1065 oldSolid = solid
1066 solid = len(solidTable) > 0
1067 if oldSolid != solid:
1068 xIntersections.append(xIntersectionIndex.x)
1069 return xIntersections
1070
1072 'Get largest loop from loops.'
1073 if len(loops) == 1:
1074 return loops[0]
1075 largestArea = -987654321.0
1076 largestLoop = []
1077 for loop in loops:
1078 loopArea = abs(getAreaLoop(loop))
1079 if loopArea > largestArea:
1080 largestArea = loopArea
1081 largestLoop = loop
1082 return largestLoop
1083
1085 'Get the leftmost complex point in the points.'
1086 leftmost = 987654321.0
1087 leftPointComplex = None
1088 for pointComplex in points:
1089 if pointComplex.real < leftmost:
1090 leftmost = pointComplex.real
1091 leftPointComplex = pointComplex
1092 return leftPointComplex
1093
1095 'Get the index of the leftmost complex point in the points.'
1096 if len(points) < 1:
1097 return None
1098 leftPointIndex = 0
1099 for pointIndex in xrange(len(points)):
1100 if points[pointIndex].real < points[ leftPointIndex ].real:
1101 leftPointIndex = pointIndex
1102 return leftPointIndex
1103
1105 'Get all the element in a list table.'
1106 listDictionaryElements = []
1107 for listDictionaryValue in listDictionary.values():
1108 listDictionaryElements += listDictionaryValue
1109 return listDictionaryElements
1110
1112 'Get the area of a complex polygon using http://en.wikipedia.org/wiki/Centroid.'
1113 polygonDoubleArea = 0.0
1114 polygonTorque = 0.0
1115 for pointIndex in xrange(len(polygonComplex)):
1116 pointBegin = polygonComplex[pointIndex]
1117 pointEnd = polygonComplex[ (pointIndex + 1) % len(polygonComplex) ]
1118 doubleArea = pointBegin.real * pointEnd.imag - pointEnd.real * pointBegin.imag
1119 doubleCenter = complex(pointBegin.real + pointEnd.real, pointBegin.imag + pointEnd.imag)
1120 polygonDoubleArea += doubleArea
1121 polygonTorque += doubleArea * doubleCenter
1122 torqueMultiplier = 0.333333333333333333333333 / polygonDoubleArea
1123 return polygonTorque * torqueMultiplier
1124
1126 'Get convex hull of points using gift wrap algorithm.'
1127 loopConvex = []
1128 pointSet = set()
1129 for point in points:
1130 if point not in pointSet:
1131 pointSet.add(point)
1132 loopConvex.append(point)
1133 if len(loopConvex) < 4:
1134 return loopConvex
1135 leftPoint = getLeftPoint(loopConvex)
1136 lastPoint = leftPoint
1137 pointSet.remove(leftPoint)
1138 loopConvex = [leftPoint]
1139 lastSegment = complex(0.0, 1.0)
1140 while True:
1141 greatestDotProduct = -9.9
1142 greatestPoint = None
1143 greatestSegment = None
1144 if len(loopConvex) > 2:
1145 nextSegment = getNormalized(leftPoint - lastPoint)
1146 if abs(nextSegment) > 0.0:
1147 greatestDotProduct = getDotProduct(nextSegment, lastSegment)
1148 for point in pointSet:
1149 nextSegment = getNormalized(point - lastPoint)
1150 if abs(nextSegment) > 0.0:
1151 dotProduct = getDotProduct(nextSegment, lastSegment)
1152 if dotProduct > greatestDotProduct:
1153 greatestDotProduct = dotProduct
1154 greatestPoint = point
1155 greatestSegment = nextSegment
1156 if greatestPoint == None:
1157 return loopConvex
1158 lastPoint = greatestPoint
1159 loopConvex.append(greatestPoint)
1160 pointSet.remove(greatestPoint)
1161 lastSegment = greatestSegment
1162 return loopConvex
1163
1167
1169 'Get a loop that is inside the containing loop.'
1170 for loop in loops:
1171 if loop != containingLoop:
1172 if isPathInsideLoop(containingLoop, loop):
1173 return loop
1174 return None
1175
1177 'Get the length of a polygon perimeter.'
1178 polygonLength = 0.0
1179 for pointIndex in xrange(len(polygon)):
1180 point = polygon[pointIndex]
1181 secondPoint = polygon[ (pointIndex + 1) % len(polygon) ]
1182 polygonLength += abs(point - secondPoint)
1183 return polygonLength
1184
1186 'Add to threads from the last location from loop.'
1187 nearestIndex = getNearestDistanceIndex(location, loop).index
1188 loop = getAroundLoop(nearestIndex, nearestIndex, loop)
1189 nearestPoint = getNearestPointOnSegment(loop[0], loop[1], location)
1190 if abs(nearestPoint - loop[0]) > extrusionHalfWidth and abs(nearestPoint - loop[1]) > extrusionHalfWidth:
1191 loop = [nearestPoint] + loop[1 :] + [loop[0]]
1192 elif abs(nearestPoint - loop[0]) > abs(nearestPoint - loop[1]):
1193 loop = loop[1 :] + [loop[0]]
1194 return loop
1195
1197 'Get loop without close ends.'
1198 if len(loop) < 2:
1199 return loop
1200 if abs(loop[0] - loop[-1]) > close:
1201 return loop
1202 return loop[:-1]
1203
1205 'Get loop without close sequential points.'
1206 if len(loop) < 2:
1207 return loop
1208 lastPoint = loop[-1]
1209 loopWithoutCloseSequentialPoints = []
1210 for point in loop:
1211 if abs(point - lastPoint) > close:
1212 loopWithoutCloseSequentialPoints.append(point)
1213 lastPoint = point
1214 return loopWithoutCloseSequentialPoints
1215
1217 'Get a complex with each component the maximum of the respective components of a pair of complexes.'
1218 return complex(max(firstComplex.real, secondComplex.real), max(firstComplex.imag, secondComplex.imag))
1219
1221 'Get a complex with each component the maximum of the respective components of a complex path.'
1222 maximum = complex(-987654321.0, -987654321.0)
1223 for point in path:
1224 maximum = getMaximum(maximum, point)
1225 return maximum
1226
1228 'Get a complex with each component the maximum of the respective components of complex paths.'
1229 maximum = complex(-987654321.0, -987654321.0)
1230 for path in paths:
1231 for point in path:
1232 maximum = getMaximum(maximum, point)
1233 return maximum
1234
1236 'Get a vector3 with each component the maximum of the respective components of a vector3 path.'
1237 maximum = Vector3(-987654321.0, -987654321.0, -987654321.0)
1238 for point in path:
1239 maximum.maximize(point)
1240 return maximum
1241
1243 'Get a complex with each component the maximum of the respective components of a complex path.'
1244 maximum = Vector3(-987654321.0, -987654321.0, -987654321.0)
1245 for path in paths:
1246 for point in path:
1247 maximum.maximize(point)
1248 return maximum
1249
1254
1256 'Get a complex with each component the minimum of the respective components of a pair of complexes.'
1257 return complex(min(firstComplex.real, secondComplex.real), min(firstComplex.imag, secondComplex.imag))
1258
1260 'Get a complex with each component the minimum of the respective components of a complex path.'
1261 minimum = complex(987654321.0, 987654321.0)
1262 for point in path:
1263 minimum = getMinimum(minimum, point)
1264 return minimum
1265
1267 'Get a complex with each component the minimum of the respective components of complex paths.'
1268 minimum = complex(987654321.0, 987654321.0)
1269 for path in paths:
1270 for point in path:
1271 minimum = getMinimum(minimum, point)
1272 return minimum
1273
1275 'Get a vector3 with each component the minimum of the respective components of a vector3 path.'
1276 minimum = Vector3(987654321.0, 987654321.0, 987654321.0)
1277 for point in path:
1278 minimum.minimize(point)
1279 return minimum
1280
1282 'Get a complex with each component the minimum of the respective components of a complex path.'
1283 minimum = Vector3(987654321.0, 987654321.0, 987654321.0)
1284 for path in paths:
1285 for point in path:
1286 minimum.minimize(point)
1287 return minimum
1288
1290 "Get mirror path."
1291 close = 0.001 * getPathLength(path)
1292 for pointIndex in xrange(len(path) - 1, -1, -1):
1293 point = path[pointIndex]
1294 flipPoint = complex(-point.real, point.imag)
1295 if abs(flipPoint - path[-1]) > close:
1296 path.append(flipPoint)
1297 return path
1298
1300 'Get the distance squared to the nearest segment of the loop and index of that segment.'
1301 smallestDistance = 987654321987654321.0
1302 nearestDistanceIndex = None
1303 for pointIndex in xrange(len(loop)):
1304 segmentBegin = loop[pointIndex]
1305 segmentEnd = loop[(pointIndex + 1) % len(loop)]
1306 distance = getDistanceToPlaneSegment(segmentBegin, segmentEnd, point)
1307 if distance < smallestDistance:
1308 smallestDistance = distance
1309 nearestDistanceIndex = DistanceIndex(distance, pointIndex)
1310 return nearestDistanceIndex
1311
1313 'Get the nearest point on the segment.'
1314 segmentDifference = segmentEnd - segmentBegin
1315 if abs(segmentDifference) <= 0.0:
1316 return segmentBegin
1317 pointMinusSegmentBegin = point - segmentBegin
1318 beginPlaneDot = getDotProduct(pointMinusSegmentBegin, segmentDifference)
1319 differencePlaneDot = getDotProduct(segmentDifference, segmentDifference)
1320 intercept = beginPlaneDot / differencePlaneDot
1321 intercept = max(intercept, 0.0)
1322 intercept = min(intercept, 1.0)
1323 return segmentBegin + segmentDifference * intercept
1324
1326 'Get normal.'
1327 centerMinusBegin = (center - begin).getNormalized()
1328 endMinusCenter = (end - center).getNormalized()
1329 return centerMinusBegin.cross(endMinusCenter)
1330
1332 'Get normal by path.'
1333 totalNormal = Vector3()
1334 for pointIndex, point in enumerate(path):
1335 center = path[(pointIndex + 1) % len(path)]
1336 end = path[(pointIndex + 2) % len(path)]
1337 totalNormal += getNormalWeighted(point, center, end)
1338 return totalNormal.getNormalized()
1339
1341 'Get the normalized complex.'
1342 complexNumberLength = abs(complexNumber)
1343 if complexNumberLength > 0.0:
1344 return complexNumber / complexNumberLength
1345 return complexNumber
1346
1348 'Get weighted normal.'
1349 return (center - begin).cross(end - center)
1350
1352 'Get the number of intersections through the loop for the line going left.'
1353 numberOfIntersectionsToLeft = 0
1354
1355 for pointIndex in xrange(len(loop)):
1356 firstPointComplex = loop[pointIndex]
1357 secondPointComplex = loop[(pointIndex + 1) % len(loop)]
1358 xIntersection = getXIntersectionIfExists(firstPointComplex, secondPointComplex, point.imag)
1359 if xIntersection != None:
1360 if xIntersection < point.real:
1361 numberOfIntersectionsToLeft += 1
1362 return numberOfIntersectionsToLeft
1363
1365 'Get the number of intersections through the loop for the line starting from the left point and going left.'
1366 totalNumberOfIntersectionsToLeft = 0
1367 for loop in loops:
1368 totalNumberOfIntersectionsToLeft += getNumberOfIntersectionsToLeft(loop, point)
1369 return totalNumberOfIntersectionsToLeft
1370
1372 'Get ordered nestedRings from nestedRings.'
1373 insides = []
1374 orderedNestedRings = []
1375 for loopIndex in xrange(len(nestedRings)):
1376 nestedRing = nestedRings[loopIndex]
1377 otherLoops = []
1378 for beforeIndex in xrange(loopIndex):
1379 otherLoops.append(nestedRings[beforeIndex].boundary)
1380 for afterIndex in xrange(loopIndex + 1, len(nestedRings)):
1381 otherLoops.append(nestedRings[afterIndex].boundary)
1382 if isPathEntirelyInsideLoops(otherLoops, nestedRing.boundary):
1383 insides.append(nestedRing)
1384 else:
1385 orderedNestedRings.append(nestedRing)
1386 for outside in orderedNestedRings:
1387 outside.getFromInsideSurroundings(insides)
1388 return orderedNestedRings
1389
1391 'Get path copy.'
1392 pathCopy = []
1393 for point in path:
1394 pathCopy.append(point.copy())
1395 return pathCopy
1396
1398 'Get the length of a path ( an open polyline ).'
1399 pathLength = 0.0
1400 for pointIndex in xrange(len(path) - 1):
1401 firstPoint = path[pointIndex]
1402 secondPoint = path[pointIndex + 1]
1403 pathLength += abs(firstPoint - secondPoint)
1404 return pathLength
1405
1407 'Get paths from endpoints.'
1408 if len(endpoints) < 2:
1409 return []
1410 endpoints = endpoints[:]
1411 for beginningEndpoint in endpoints[: : 2]:
1412 beginningPoint = beginningEndpoint.point
1413 addSegmentToPixelTable(beginningPoint, beginningEndpoint.otherEndpoint.point, pixelDictionary, 0, 0, width)
1414 endpointFirst = endpoints[0]
1415 endpoints.remove(endpointFirst)
1416 otherEndpoint = endpointFirst.otherEndpoint
1417 endpoints.remove(otherEndpoint)
1418 nextEndpoint = None
1419 path = []
1420 paths = [path]
1421 if len(endpoints) > 1:
1422 nextEndpoint = otherEndpoint.getNearestMiss(endpoints, path, pixelDictionary, width)
1423 if nextEndpoint != None:
1424 if abs(nextEndpoint.point - endpointFirst.point) < abs(nextEndpoint.point - otherEndpoint.point):
1425 endpointFirst = endpointFirst.otherEndpoint
1426 otherEndpoint = endpointFirst.otherEndpoint
1427 addPointToPath(path, pixelDictionary, endpointFirst.point, None, width)
1428 addPointToPath(path, pixelDictionary, otherEndpoint.point, len(paths) - 1, width)
1429 oneOverEndpointWidth = 1.0 / maximumConnectionLength
1430 endpointTable = {}
1431 for endpoint in endpoints:
1432 addElementToPixelListFromPoint(endpoint, endpointTable, endpoint.point * oneOverEndpointWidth)
1433 while len(endpointTable) > 0:
1434 if len(endpointTable) == 1:
1435 if len(endpointTable.values()[0]) < 2:
1436 return []
1437 endpoints = getSquareValuesFromPoint(endpointTable, otherEndpoint.point * oneOverEndpointWidth)
1438 nextEndpoint = otherEndpoint.getNearestMiss(endpoints, path, pixelDictionary, width)
1439 if nextEndpoint == None:
1440 path = []
1441 paths.append(path)
1442 endpoints = getListTableElements(endpointTable)
1443 nextEndpoint = otherEndpoint.getNearestEndpoint(endpoints)
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454 addPointToPath(path, pixelDictionary, nextEndpoint.point, len(paths) - 1, width)
1455 removeElementFromPixelListFromPoint(nextEndpoint, endpointTable, nextEndpoint.point * oneOverEndpointWidth)
1456 otherEndpoint = nextEndpoint.otherEndpoint
1457 addPointToPath(path, pixelDictionary, otherEndpoint.point, len(paths) - 1, width)
1458 removeElementFromPixelListFromPoint(otherEndpoint, endpointTable, otherEndpoint.point * oneOverEndpointWidth)
1459 return paths
1460
1462 'Get the dot product of the x and y components of a pair of Vector3s.'
1463 return vec3First.x * vec3Second.x + vec3First.y * vec3Second.y
1464
1466 'Get the plural string.'
1467 if number == 1:
1468 return '1 %s' % suffix
1469 return '%s %ss' % (number, suffix)
1470
1472 'Get point plus a segment scaled to a given length.'
1473 return segment * length / abs(segment) + point
1475 'Get points from the horizontalXIntersectionsDictionary.'
1476 points = []
1477 xIntersectionsDictionaryKeys = xIntersectionsDictionary.keys()
1478 xIntersectionsDictionaryKeys.sort()
1479 for xIntersectionsDictionaryKey in xIntersectionsDictionaryKeys:
1480 for xIntersection in xIntersectionsDictionary[xIntersectionsDictionaryKey]:
1481 points.append(complex(xIntersection, xIntersectionsDictionaryKey * width))
1482 return points
1483
1485 'Get points from the verticalXIntersectionsDictionary.'
1486 points = []
1487 xIntersectionsDictionaryKeys = xIntersectionsDictionary.keys()
1488 xIntersectionsDictionaryKeys.sort()
1489 for xIntersectionsDictionaryKey in xIntersectionsDictionaryKeys:
1490 for xIntersection in xIntersectionsDictionary[xIntersectionsDictionaryKey]:
1491 points.append(complex(xIntersectionsDictionaryKey * width, xIntersection))
1492 return points
1493
1495 'Get the radius multiplier for a polygon of equal area.'
1496 return math.sqrt(globalTau / sides / math.sin(globalTau / sides))
1497
1499 'Get points rotated by the plane angle'
1500 planeArray = []
1501 for point in points:
1502 planeArray.append(planeAngle * point)
1503 return planeArray
1504
1506 'Get point plus a segment scaled to a given length.'
1507 return segment * length / abs(segment) + point
1508
1510 'Get random complex.'
1511 endMinusBegin = end - begin
1512 return begin + complex(random.random() * endMinusBegin.real, random.random() * endMinusBegin.imag)
1513
1515 'Get the rank which is 0 at 1 and increases by three every power of ten.'
1516 return int(math.floor(3.0 * math.log10(width)))
1518 'Get points rotated by the plane angle'
1519 rotatedComplexes = []
1520 for point in points:
1521 rotatedComplexes.append(planeAngle * point)
1522 return rotatedComplexes
1523
1525 'Get point lists rotated by the plane angle'
1526 rotatedComplexLists = []
1527 for pointList in pointLists:
1528 rotatedComplexLists.append(getRotatedComplexes(planeAngle, pointList))
1529 return rotatedComplexLists
1530
1534
1536 'Get point with each component rounded.'
1537 return Vector3(round(point.x), round(point.y), round(point.z))
1538
1540 'Get number rounded to a number of decimal places.'
1541 decimalPlacesRounded = max(1, int(round(decimalPlaces)))
1542 return round(number, decimalPlacesRounded)
1543
1545 'Get number rounded to a number of decimal places as a string.'
1546 return str(getRoundedToPlaces(decimalPlaces, number))
1547
1549 'Get number rounded to three places as a string.'
1550 return str(round(number, 3))
1551
1555
1557 'Get endpoint segment from a path.'
1558 if len(path) < 2:
1559 return None
1560 begin = path[-1]
1561 end = path[-2]
1562 forwardEndpoint = getEndpointFromPath(path, pathIndex)
1563 reversePath = path[:]
1564 reversePath.reverse()
1565 reverseEndpoint = getEndpointFromPath(reversePath, pathIndex)
1566 return (forwardEndpoint, reverseEndpoint)
1567
1569 'Get endpoint segment from a pair of points.'
1570 endpointFirst = Endpoint()
1571 endpointSecond = Endpoint().getFromOtherPoint(endpointFirst, end)
1572 endpointFirst.getFromOtherPoint(endpointSecond, begin)
1573 return (endpointFirst, endpointSecond)
1574
1580 'Get endpoint segments from the x intersections.'
1581 segments = []
1582 end = len(xIntersections)
1583 if len(xIntersections) % 2 == 1:
1584 end -= 1
1585 for xIntersectionIndex in xrange(0, end, 2):
1586 firstX = xIntersections[ xIntersectionIndex ]
1587 secondX = xIntersections[ xIntersectionIndex + 1 ]
1588 if firstX != secondX:
1589 segments.append(getSegmentFromPoints(complex(firstX, y), complex(secondX, y)))
1590 return segments
1591
1592
1594 'Get loop with points inside the channel removed.'
1595 if len(loop) < 2:
1596 return loop
1597 simplificationMultiplication = 256
1598 simplificationRadius = radius / float(simplificationMultiplication)
1599 maximumIndex = len(loop) * simplificationMultiplication
1600 pointIndex = 1
1601 while pointIndex < maximumIndex:
1602 oldLoopLength = len(loop)
1603 loop = getHalfSimplifiedLoop(loop, simplificationRadius, 0)
1604 loop = getHalfSimplifiedLoop(loop, simplificationRadius, 1)
1605 simplificationRadius += simplificationRadius
1606 if oldLoopLength == len(loop):
1607 if simplificationRadius > radius:
1608 return getAwayPoints(loop, radius)
1609 else:
1610 simplificationRadius *= 1.5
1611 simplificationRadius = min(simplificationRadius, radius)
1612 pointIndex += pointIndex
1613 return getAwayPoints(loop, radius)
1614
1616 'Get the simplified loops.'
1617 simplifiedLoops = []
1618 for loop in loops:
1619 simplifiedLoops.append(getSimplifiedLoop(loop, radius))
1620 return simplifiedLoops
1621
1623 'Get path with points inside the channel removed.'
1624 if len(path) < 2:
1625 return path
1626 simplificationMultiplication = 256
1627 simplificationRadius = radius / float(simplificationMultiplication)
1628 maximumIndex = len(path) * simplificationMultiplication
1629 pointIndex = 1
1630 while pointIndex < maximumIndex:
1631 oldPathLength = len(path)
1632 path = getHalfSimplifiedPath(path, simplificationRadius, 0)
1633 path = getHalfSimplifiedPath(path, simplificationRadius, 1)
1634 simplificationRadius += simplificationRadius
1635 if oldPathLength == len(path):
1636 if simplificationRadius > radius:
1637 return getAwayPath(path, radius)
1638 else:
1639 simplificationRadius *= 1.5
1640 simplificationRadius = min(simplificationRadius, radius)
1641 pointIndex += pointIndex
1642 return getAwayPath(path, radius)
1643
1645 'Determine if a square around the x and y pixel coordinates is occupied.'
1646 squareValues = []
1647 for xStep in xrange(x - 1, x + 2):
1648 for yStep in xrange(y - 1, y + 2):
1649 if (xStep, yStep) in pixelDictionary:
1650 return True
1651 return False
1652
1654 'Get a square loop from the beginning to the end and back.'
1655 loop = [beginComplex, complex(endComplex.real, beginComplex.imag), endComplex]
1656 loop.append(complex(beginComplex.real, endComplex.imag))
1657 return loop
1658
1660 'Get a list of the values in a square around the x and y pixel coordinates.'
1661 squareValues = []
1662 for xStep in xrange(x - 1, x + 2):
1663 for yStep in xrange(y - 1, y + 2):
1664 stepKey = (xStep, yStep)
1665 if stepKey in pixelDictionary:
1666 squareValues += pixelDictionary[ stepKey ]
1667 return squareValues
1668
1670 'Get a list of the values in a square around the point.'
1671 return getSquareValues(pixelDictionary, int(round(point.real)), int(round(point.imag)))
1672
1674 'Get step key for the point.'
1675 return (int(round(point.real)), int(round(point.imag)))
1676
1685
1687 'Get the top of the path.'
1688 top = -987654321.0
1689 for point in path:
1690 top = max(top, point.z)
1691 return top
1692
1694 'Get the top of the paths.'
1695 top = -987654321.0
1696 for path in paths:
1697 for point in path:
1698 top = max(top, point.z)
1699 return top
1700
1702 'Get and transfer the closest remaining surrounding loop.'
1703 if len(nestedRings) > 0:
1704 oldOrderedLocation.z = nestedRings[0].z
1705 closestDistance = 987654321987654321.0
1706 closestNestedRing = None
1707 for nestedRing in nestedRings:
1708 distance = getNearestDistanceIndex(oldOrderedLocation.dropAxis(), nestedRing.getXYBoundaries()).distance
1709 if distance < closestDistance:
1710 closestDistance = distance
1711 closestNestedRing = nestedRing
1712 print "closestNestedRing",closestNestedRing
1713
1714
1715 closestNestedRing.addToThreads(extrusionHalfWidth, oldOrderedLocation, threadSequence)
1716 return closestNestedRing
1717
1719 'Get transferred paths from inside paths.'
1720 transferredPaths = []
1721 for insideIndex in xrange(len(insides) - 1, -1, -1):
1722 inside = insides[ insideIndex ]
1723 if isPathInsideLoop(loop, inside):
1724 transferredPaths.append(inside)
1725 del insides[ insideIndex ]
1726 return transferredPaths
1727
1729 'Get transferred paths from inside surrounding loops.'
1730 transferredSurroundings = []
1731 for insideIndex in xrange(len(insides) - 1, -1, -1):
1732 insideSurrounding = insides[ insideIndex ]
1733 if isPathInsideLoop(loop, insideSurrounding.boundary):
1734 transferredSurroundings.append(insideSurrounding)
1735 del insides[ insideIndex ]
1736 return transferredSurroundings
1737
1739 'Get the translated complex path.'
1740 translatedComplexPath = []
1741 for point in path:
1742 translatedComplexPath.append(point + translateComplex)
1743 return translatedComplexPath
1744
1746 'Get the vector3 path from the complex path.'
1747 vector3Path = []
1748 for complexPoint in complexPath:
1749 vector3Path.append(Vector3(complexPoint.real, complexPoint.imag, z))
1750 return vector3Path
1751
1753 'Get the vector3 paths from the complex paths.'
1754 vector3Paths = []
1755 for complexPath in complexPaths:
1756 vector3Paths.append(getVector3Path(complexPath, z))
1757 return vector3Paths
1758
1760 'Get polar complex from counterclockwise angle from 1, 0.'
1761 return complex(math.cos(angle), math.sin(angle))
1762
1764 'Get the x intersection if it exists.'
1765 if (y > beginComplex.imag) == (y > endComplex.imag):
1766 return None
1767 endMinusBeginComplex = endComplex - beginComplex
1768 return (y - beginComplex.imag) / endMinusBeginComplex.imag * endMinusBeginComplex.real + beginComplex.real
1769
1771 'Get x intersections from the x intersection index list, in other words subtract non negative intersections from negatives.'
1772 xIntersections = []
1773 fill = False
1774 solid = False
1775 solidTable = {}
1776 xIntersectionIndexList.sort()
1777 for solidX in xIntersectionIndexList:
1778 if solidX.index >= 0:
1779 toggleHashtable(solidTable, solidX.index, '')
1780 else:
1781 fill = not fill
1782 oldSolid = solid
1783 solid = (len(solidTable) == 0 and fill)
1784 if oldSolid != solid:
1785 xIntersections.append(solidX.x)
1786 return xIntersections
1787
1789 'Get an xy complex from a vector3 if it exists, otherwise return None.'
1790 if vector3 == None:
1791 return None
1792 return vector3.dropAxis()
1793
1795 'Get the y intersection if it exists.'
1796 if (x > beginComplex.real) == (x > endComplex.real):
1797 return None
1798 endMinusBeginComplex = endComplex - beginComplex
1799 return (x - beginComplex.real) / endMinusBeginComplex.real * endMinusBeginComplex.imag + beginComplex.imag
1800
1802 'Get z component cross product of a pair of Vector3s.'
1803 return vec3First.x * vec3Second.y - vec3First.y * vec3Second.x
1804
1806 'Determine if a loop in a list is inside another loop in that list.'
1807 return isPathInsideLoops(loops[ : loopIndex ] + loops[loopIndex + 1 :], loops[loopIndex])
1808
1810 'Determine if the line is crossing inside the x segment.'
1811 xIntersection = getXIntersectionIfExists(beginComplex, endComplex, y)
1812 if xIntersection == None:
1813 return False
1814 if xIntersection < min(segmentFirstX, segmentSecondX):
1815 return False
1816 return xIntersection <= max(segmentFirstX, segmentSecondX)
1817
1819 'Determine if the line is intersecting loops.'
1820 normalizedSegment = pointEnd - pointBegin
1821 normalizedSegmentLength = abs(normalizedSegment)
1822 if normalizedSegmentLength > 0.0:
1823 normalizedSegment /= normalizedSegmentLength
1824 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
1825 pointBeginRotated = segmentYMirror * pointBegin
1826 pointEndRotated = segmentYMirror * pointEnd
1827 if isLoopIntersectingInsideXSegment(loop, pointBeginRotated.real, pointEndRotated.real, segmentYMirror, pointBeginRotated.imag):
1828 return True
1829 return False
1830
1832 'Determine if the line is intersecting loops.'
1833 normalizedSegment = pointEnd - pointBegin
1834 normalizedSegmentLength = abs(normalizedSegment)
1835 if normalizedSegmentLength > 0.0:
1836 normalizedSegment /= normalizedSegmentLength
1837 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
1838 pointBeginRotated = segmentYMirror * pointBegin
1839 pointEndRotated = segmentYMirror * pointEnd
1840 if isLoopListIntersectingInsideXSegment(loops, pointBeginRotated.real, pointEndRotated.real, segmentYMirror, pointBeginRotated.imag):
1841 return True
1842 return False
1843
1845 'Determine if the loop is intersecting inside the x segment.'
1846 rotatedLoop = getRotatedComplexes( segmentYMirror, loop )
1847
1848 for pointIndex in xrange(len(rotatedLoop)):
1849 pointFirst = rotatedLoop[pointIndex]
1850 pointSecond = rotatedLoop[ (pointIndex + 1) % len(rotatedLoop) ]
1851 if isLineIntersectingInsideXSegment(pointFirst, pointSecond, segmentFirstX, segmentSecondX, y):
1852 return True
1853 return False
1854
1856 'Determine if the loop is intersecting the other loop.'
1857 for pointIndex in xrange(len(loop)):
1858 pointBegin = loop[pointIndex]
1859 pointEnd = loop[(pointIndex + 1) % len(loop)]
1860 if isLineIntersectingLoop(otherLoop, pointBegin, pointEnd):
1861 return True
1862 return False
1863
1865 'Determine if the loop is intersecting other loops.'
1866 for pointIndex in xrange(len(loop)):
1867 pointBegin = loop[pointIndex]
1868 pointEnd = loop[(pointIndex + 1) % len(loop)]
1869 if isLineIntersectingLoops(otherLoops, pointBegin, pointEnd):
1870 return True
1871 return False
1872
1874 'Determine if the loop list is crossing inside the x segment.'
1875 for alreadyFilledLoop in loopList:
1876 if isLoopIntersectingInsideXSegment(alreadyFilledLoop, segmentFirstX, segmentSecondX, segmentYMirror, y):
1877 return True
1878 return False
1879
1881 'Determine if a loop in the list is intersecting the other loops.'
1882 for loopIndex in xrange(len(loops) - 1):
1883 loop = loops[loopIndex]
1884 if isLoopIntersectingLoops(loop, loops[loopIndex + 1 :]):
1885 return True
1886 return False
1887
1889 'Determine if a path is entirely inside another loop.'
1890 for point in path:
1891 if not isPointInsideLoop(loop, point):
1892 return False
1893 return True
1894
1896 'Determine if a path is entirely inside another loop in a list.'
1897 for loop in loops:
1898 if isPathEntirelyInsideLoop(loop, path):
1899 return True
1900 return False
1901
1902
1904 'Returns loops within which the path is entirely contained.'
1905 enclosingLoops = []
1906 for loop in loops:
1907 if isPathEntirelyInsideLoop(loop, path):
1908 enclosingLoops.append(loop)
1909 return enclosingLoops
1910
1912 'Returns closest loop within which the path is entirely contained.'
1913 enclosingLoop = (None,None)
1914 for loop in loops:
1915 if isPathEntirelyInsideLoop(loop, path):
1916 absArea = abs(getAreaLoop(loop))
1917 if enclosingLoop == (None,None):
1918 enclosingLoop = (absArea, loop)
1919 else:
1920 if absArea < enclosingLoop[0]:
1921 enclosingLoop = (absArea, loop)
1922
1923 return enclosingLoop[1]
1924
1928
1930 'Determine if a path is inside another loop in a list.'
1931 for loop in loops:
1932 if isPathInsideLoop(loop, path):
1933 return True
1934 return False
1935
1937 'Add path to the pixel table.'
1938 littleTableKeys = littleTable.keys()
1939 for littleTableKey in littleTableKeys:
1940 if littleTableKey not in maskTable:
1941 if littleTableKey in bigTable:
1942 return True
1943 return False
1944
1948
1950 'Determine if the segment overlaps within x.'
1951 segmentFirstX = segment[0].point.real
1952 segmentSecondX = segment[1].point.real
1953 if max(segmentFirstX, segmentSecondX) > max(xFirst, xSecond):
1954 return False
1955 return min(segmentFirstX, segmentSecondX) >= min(xFirst, xSecond)
1956
1958 'Determine if the complex polygon goes round in the widdershins direction.'
1959 return getAreaLoop(polygonComplex) > 0.0
1960
1962 'Determine if the the point is within the channel between two adjacent points.'
1963 point = loop[pointIndex]
1964 behindSegmentComplex = loop[(pointIndex + len(loop) - 1) % len(loop)] - point
1965 behindSegmentComplexLength = abs(behindSegmentComplex)
1966 if behindSegmentComplexLength < channelRadius:
1967 return True
1968 aheadSegmentComplex = loop[(pointIndex + 1) % len(loop)] - point
1969 aheadSegmentComplexLength = abs(aheadSegmentComplex)
1970 if aheadSegmentComplexLength < channelRadius:
1971 return True
1972 behindSegmentComplex /= behindSegmentComplexLength
1973 aheadSegmentComplex /= aheadSegmentComplexLength
1974 absoluteZ = getDotProductPlusOne(aheadSegmentComplex, behindSegmentComplex)
1975 if behindSegmentComplexLength * absoluteZ < channelRadius:
1976 return True
1977 return aheadSegmentComplexLength * absoluteZ < channelRadius
1978
1980 'Determine if a path is crossing inside the x segment.'
1981 rotatedPath = getRotatedComplexes( segmentYMirror, path )
1982 for pointIndex in xrange(len(rotatedPath) - 1):
1983 pointFirst = rotatedPath[pointIndex]
1984 pointSecond = rotatedPath[pointIndex + 1]
1985 if isLineIntersectingInsideXSegment(pointFirst, pointSecond, segmentFirstX, segmentSecondX, y):
1986 return True
1987 return False
1988
1990 'Determine if a path list is crossing inside the x segment.'
1991 for path in paths:
1992 if isXSegmentIntersectingPath(path, segmentFirstX, segmentSecondX, segmentYMirror, y):
1993 return True
1994 return False
1995
1997 'Join both segment tables and put the join into the intoTable.'
1998 intoTableKeys = intoTable.keys()
1999 fromTableKeys = fromTable.keys()
2000 joinedKeyTable = {}
2001 concatenatedTableKeys = intoTableKeys + fromTableKeys
2002 for concatenatedTableKey in concatenatedTableKeys:
2003 joinedKeyTable[ concatenatedTableKey ] = None
2004 joinedKeys = joinedKeyTable.keys()
2005 joinedKeys.sort()
2006 for joinedKey in joinedKeys:
2007 xIntersectionIndexList = []
2008 if joinedKey in intoTable:
2009 addXIntersectionIndexesFromSegments(0, intoTable[ joinedKey ], xIntersectionIndexList)
2010 if joinedKey in fromTable:
2011 addXIntersectionIndexesFromSegments(1, fromTable[ joinedKey ], xIntersectionIndexList)
2012 xIntersections = getJoinOfXIntersectionIndexes(xIntersectionIndexList)
2013 lineSegments = getSegmentsFromXIntersections(xIntersections, joinedKey)
2014 if len(lineSegments) > 0:
2015 intoTable[ joinedKey ] = lineSegments
2016 else:
2017 print('This should never happen, there are no line segments in joinSegments in euclidean')
2018
2020 'Join both XIntersections tables and put the join into the intoTable.'
2021 joinedKeyTable = {}
2022 concatenatedTableKeys = fromTable.keys() + intoTable.keys()
2023 for concatenatedTableKey in concatenatedTableKeys:
2024 joinedKeyTable[ concatenatedTableKey ] = None
2025 for joinedKey in joinedKeyTable.keys():
2026 xIntersectionIndexList = []
2027 if joinedKey in intoTable:
2028 addXIntersectionIndexesFromXIntersections(0, xIntersectionIndexList, intoTable[ joinedKey ])
2029 if joinedKey in fromTable:
2030 addXIntersectionIndexesFromXIntersections(1, xIntersectionIndexList, fromTable[ joinedKey ])
2031 xIntersections = getJoinOfXIntersectionIndexes(xIntersectionIndexList)
2032 if len(xIntersections) > 0:
2033 intoTable[ joinedKey ] = xIntersections
2034 else:
2035 print('This should never happen, there are no line segments in joinSegments in euclidean')
2036
2038 'Overwrite the dictionary.'
2039 for key in keys:
2040 if key in fromDictionary:
2041 toDictionary[key] = fromDictionary[key]
2042
2047
2049 'Remove an element from the list table.'
2050 if key not in listDictionary:
2051 return
2052 elementList = listDictionary[key]
2053 if len(elementList) < 2:
2054 del listDictionary[key]
2055 return
2056 if element in elementList:
2057 elementList.remove(element)
2058
2063
2068
2070 'Remove the attributes starting with the prefix from the dictionary.'
2071 for key in dictionary.keys():
2072 if key.startswith(prefix):
2073 del dictionary[key]
2074
2078
2084
2089
2091 'Subtract the subtractTable from the subtractFromTable.'
2092 subtractFromTableKeys = subtractFromTable.keys()
2093 subtractFromTableKeys.sort()
2094 for subtractFromTableKey in subtractFromTableKeys:
2095 xIntersectionIndexList = []
2096 addXIntersectionIndexesFromXIntersections(-1, xIntersectionIndexList, subtractFromTable[ subtractFromTableKey ])
2097 if subtractFromTableKey in subtractTable:
2098 addXIntersectionIndexesFromXIntersections(0, xIntersectionIndexList, subtractTable[ subtractFromTableKey ])
2099 xIntersections = getXIntersectionsFromIntersections(xIntersectionIndexList)
2100 if len(xIntersections) > 0:
2101 subtractFromTable[ subtractFromTableKey ] = xIntersections
2102 else:
2103 del subtractFromTable[ subtractFromTableKey ]
2104
2105 -def swapList(elements, indexBegin, indexEnd):
2106 'Swap the list elements.'
2107 elements[ indexBegin ], elements[ indexEnd ] = elements[ indexEnd ], elements[ indexBegin ]
2108
2110 'Toggle a hashtable between having and not having a key.'
2111 if key in hashtable:
2112 del hashtable[key]
2113 else:
2114 hashtable[key] = value
2115
2117 'Transfer the closest remaining fill loop.'
2118 closestDistance = 987654321987654321.0
2119 closestFillLoop = None
2120 for remainingFillLoop in remainingFillLoops:
2121 distance = getNearestDistanceIndex(oldOrderedLocation.dropAxis(), remainingFillLoop).distance
2122 if distance < closestDistance:
2123 closestDistance = distance
2124 closestFillLoop = remainingFillLoop
2125 newClosestFillLoop = getLoopInsideContainingLoop(closestFillLoop, remainingFillLoops)
2126 while newClosestFillLoop != None:
2127 closestFillLoop = newClosestFillLoop
2128 newClosestFillLoop = getLoopInsideContainingLoop(closestFillLoop, remainingFillLoops)
2129 remainingFillLoops.remove(closestFillLoop)
2130 addToThreadsFromLoop(extrusionHalfWidth, 'loop', closestFillLoop[:], oldOrderedLocation, nestedRing)
2131
2133 'Transfer the closest remaining path.'
2134 closestDistance = 987654321987654321.0
2135 closestPath = None
2136 oldOrderedLocationComplex = oldOrderedLocation.dropAxis()
2137 for remainingPath in remainingPaths:
2138 distance = min(abs(oldOrderedLocationComplex - remainingPath[0]), abs(oldOrderedLocationComplex - remainingPath[-1]))
2139 if distance < closestDistance:
2140 closestDistance = distance
2141 closestPath = remainingPath
2142 remainingPaths.remove(closestPath)
2143 nestedRing.addInfillGcodeFromThread(closestPath)
2144 oldOrderedLocation.x = closestPath[-1].real
2145 oldOrderedLocation.y = closestPath[-1].imag
2146
2148 'Transfer the closest remaining paths.'
2149 while len(remainingPaths) > 0:
2150 transferClosestPath(oldOrderedLocation, remainingPaths, nestedRing)
2151
2153 'Transfer paths to surrounding loops.'
2154 for nestedRing in nestedRings:
2155 nestedRing.transferPaths(paths)
2156
2158 'Translate the vector3 path.'
2159 for point in path:
2160 point.setToVector3(point + translateVector3)
2161
2166
2168 'Unbuckle space.'
2169 normalDot = basis.dot(normal)
2170 dotComplement = math.sqrt(1.0 - normalDot * normalDot)
2171 unbuckling = maximumUnbuckling
2172 if dotComplement > 0.0:
2173 unbuckling = min(1.0 / dotComplement, maximumUnbuckling)
2174 basis.setToVector3(basis * unbuckling)
2175
2176
2178 'A class to hold the distance and the index of the loop.'
2182
2184 'Get the string representation of this distance index.'
2185 return '%s, %s' % (self.distance, self.index)
2186
2187
2189 'The endpoint of a segment.'
2191 'Get the string representation of this Endpoint.'
2192 return 'Endpoint %s, %s' % (self.point, self.otherEndpoint.point)
2193
2195 'Initialize from other endpoint.'
2196 self.otherEndpoint = otherEndpoint
2197 self.point = point
2198 return self
2199
2201 'Get nearest endpoint.'
2202 smallestDistance = 987654321987654321.0
2203 nearestEndpoint = None
2204 for endpoint in endpoints:
2205 distance = abs(self.point - endpoint.point)
2206 if distance < smallestDistance:
2207 smallestDistance = distance
2208 nearestEndpoint = endpoint
2209 return nearestEndpoint
2210
2212 'Get the nearest endpoint which the segment to that endpoint misses the other extrusions.'
2213 pathMaskTable = {}
2214 smallestDistance = 987654321.0
2215 penultimateMinusPoint = complex(0.0, 0.0)
2216 if len(path) > 1:
2217 penultimatePoint = path[-2]
2218 addSegmentToPixelTable(penultimatePoint, self.point, pathMaskTable, 0, 0, width)
2219 penultimateMinusPoint = penultimatePoint - self.point
2220 if abs(penultimateMinusPoint) > 0.0:
2221 penultimateMinusPoint /= abs(penultimateMinusPoint)
2222 for endpoint in endpoints:
2223 endpoint.segment = endpoint.point - self.point
2224 endpoint.segmentLength = abs(endpoint.segment)
2225 if endpoint.segmentLength <= 0.0:
2226
2227
2228
2229 return endpoint
2230 endpoints.sort(compareSegmentLength)
2231 for endpoint in endpoints[: 15]:
2232 normalizedSegment = endpoint.segment / endpoint.segmentLength
2233 isOverlappingSelf = getDotProduct(penultimateMinusPoint, normalizedSegment) > 0.9
2234 if not isOverlappingSelf:
2235 if len(path) > 2:
2236 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2237 pointRotated = segmentYMirror * self.point
2238 endpointPointRotated = segmentYMirror * endpoint.point
2239 if isXSegmentIntersectingPath(path[max(0, len(path) - 21) :-1], pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2240 isOverlappingSelf = True
2241 if not isOverlappingSelf:
2242 totalMaskTable = pathMaskTable.copy()
2243 addSegmentToPixelTable(endpoint.point, endpoint.otherEndpoint.point, totalMaskTable, 0, 0, width)
2244 segmentTable = {}
2245 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2246 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
2247 return endpoint
2248 return None
2249
2251 'Get the nearest endpoint which the segment to that endpoint misses the other extrusions, also checking the path of the endpoint.'
2252 pathMaskTable = {}
2253 smallestDistance = 987654321.0
2254 penultimateMinusPoint = complex(0.0, 0.0)
2255 if len(path) > 1:
2256 penultimatePoint = path[-2]
2257 addSegmentToPixelTable(penultimatePoint, self.point, pathMaskTable, 0, 0, width)
2258 penultimateMinusPoint = penultimatePoint - self.point
2259 if abs(penultimateMinusPoint) > 0.0:
2260 penultimateMinusPoint /= abs(penultimateMinusPoint)
2261 for endpoint in endpoints:
2262 endpoint.segment = endpoint.point - self.point
2263 endpoint.segmentLength = abs(endpoint.segment)
2264 if endpoint.segmentLength <= 0.0:
2265
2266
2267
2268 return endpoint
2269 endpoints.sort(compareSegmentLength)
2270 for endpoint in endpoints[ : 15 ]:
2271 normalizedSegment = endpoint.segment / endpoint.segmentLength
2272 isOverlappingSelf = getDotProduct(penultimateMinusPoint, normalizedSegment) > 0.9
2273 if not isOverlappingSelf:
2274 if len(path) > 2:
2275 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2276 pointRotated = segmentYMirror * self.point
2277 endpointPointRotated = segmentYMirror * endpoint.point
2278 if isXSegmentIntersectingPath(path[ max(0, len(path) - 21) :-1 ], pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2279 isOverlappingSelf = True
2280 endpointPath = endpoint.path
2281 if len(endpointPath) > 2:
2282 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
2283 pointRotated = segmentYMirror * self.point
2284 endpointPointRotated = segmentYMirror * endpoint.point
2285 if isXSegmentIntersectingPath(endpointPath, pointRotated.real, endpointPointRotated.real, segmentYMirror, pointRotated.imag):
2286 isOverlappingSelf = True
2287 if not isOverlappingSelf:
2288 totalMaskTable = pathMaskTable.copy()
2289 addSegmentToPixelTable(endpoint.point, endpoint.otherEndpoint.point, totalMaskTable, 0, 0, width)
2290 segmentTable = {}
2291 addSegmentToPixelTable(self.point, endpoint.point, segmentTable, 0, 0, width)
2292 if not isPixelTableIntersecting(pixelDictionary, segmentTable, totalMaskTable):
2293 return endpoint
2294 return None
2295
2296
2298 'Loops with a z.'
2300 self.loops = []
2301 self.z = z
2302
2304 'Get the string representation of this loop layer.'
2305 return '%s, %s' % (self.z, self.loops)
2306
2307
2309 'A nested ring.'
2311 'Initialize.'
2312 self.boundary = []
2313 self.innerNestedRings = None
2314
2316 'Get the string representation of this nested ring.'
2317 return str(self.__dict__)
2318
2320 'Add flattened nested rings.'
2321 flattenedNestedRings.append(self)
2322 for innerNestedRing in self.innerNestedRings:
2323 flattenedNestedRings += getFlattenedNestedRings(innerNestedRing.innerNestedRings)
2324
2330
2331
2333 'A loop that surrounds paths.'
2335 'Initialize.'
2336 NestedRing.__init__(self)
2337 self.extraLoops = []
2338 self.infillPaths = []
2339
2340 self.lastFillLoops = None
2341 self.loop = None
2342 self.penultimateFillLoops = []
2343 self.perimeterPaths = []
2344 self.z = None
2345
2347 'Get the string representation of this surrounding loop.'
2348 stringRepresentation = 'boundary\n%s\n' % self.boundary
2349 stringRepresentation += 'loop\n%s\n' % self.loop
2350 stringRepresentation += 'inner nested rings\n%s\n' % self.innerNestedRings
2351 stringRepresentation += 'infillPaths\n'
2352 for infillPath in self.infillPaths:
2353 stringRepresentation += 'infillPath\n%s\n' % infillPath
2354 stringRepresentation += 'perimeterPaths\n'
2355 for perimeterPath in self.perimeterPaths:
2356 stringRepresentation += 'perimeterPath\n%s\n' % perimeterPath
2357 return stringRepresentation + '\n'
2358
2363
2365 'Add vector3 to loop.'
2366 if self.loop == None:
2367 self.loop = []
2368 self.loop.append(vector3.dropAxis())
2369 self.z = vector3.z
2370
2371 - def addPerimeterInner(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2372 'Add to the perimeter and the inner island.'
2373 if self.loop == None:
2374 skein.gcodeCodec.addLine('(<perimeterPath>)')
2375 transferClosestPaths(oldOrderedLocation, self.perimeterPaths[:], skein)
2376 skein.gcodeCodec.addLine('(</perimeterPath>)')
2377 else:
2378 addToThreadsFromLoop(extrusionHalfWidth, 'perimeter', self.loop[:], oldOrderedLocation, skein)
2379 skein.gcodeCodec.addLine('(</boundaryPerimeter>)')
2380 addToThreadsRemove(extrusionHalfWidth, self.innerNestedRings[:], oldOrderedLocation, skein, threadSequence)
2381
2382 - def addToThreads(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2383 'Add to paths from the last location. perimeter>inner >fill>paths or fill> perimeter>inner >paths'
2384 addSurroundingLoopBeginning(skein.gcodeCodec, self.boundary, self.z)
2385 threadFunctionDictionary = {
2386 'infill' : self.transferInfillPaths, 'loops' : self.transferClosestFillLoops, 'perimeter' : self.addPerimeterInner}
2387 for threadType in threadSequence:
2388 threadFunctionDictionary[threadType](extrusionHalfWidth, oldOrderedLocation, skein, threadSequence)
2389 skein.gcodeCodec.addLine('(</nestedRing>)')
2390
2392 'Get last fill loops from the outside loop and the loops inside the inside loops.'
2393 fillLoops = self.getLoopsToBeFilled()[:]
2394 surroundingBoundaries = self.getSurroundingBoundaries()
2395 withinLoops = []
2396 if penultimateFillLoops == None:
2397 penultimateFillLoops = self.penultimateFillLoops
2398 for penultimateFillLoop in penultimateFillLoops:
2399 if len(penultimateFillLoop) > 2:
2400 if getIsInFilledRegion(surroundingBoundaries, penultimateFillLoop[0]):
2401 withinLoops.append(penultimateFillLoop)
2402 if not getIsInFilledRegionByPaths(self.penultimateFillLoops, fillLoops):
2403 fillLoops += self.penultimateFillLoops
2404 for nestedRing in self.innerNestedRings:
2405 fillLoops += getFillOfSurroundings(nestedRing.innerNestedRings, penultimateFillLoops)
2406 return fillLoops
2407
2408
2409
2410
2411
2412
2413
2414
2416 'Get last fill loops from the outside loop and the loops inside the inside loops.'
2417 if self.lastFillLoops == None:
2418 return self.getSurroundingBoundaries()
2419 return self.lastFillLoops
2420
2422 'Get the boundary of the surronding loop plus any boundaries of the innerNestedRings.'
2423 surroundingBoundaries = [self.boundary]
2424 for nestedRing in self.innerNestedRings:
2425 surroundingBoundaries.append(nestedRing.boundary)
2426
2427 return surroundingBoundaries
2428
2430 'Transfer closest fill loops.'
2431 if len(self.extraLoops) < 1:
2432 return
2433 remainingFillLoops = self.extraLoops[:]
2434 while len(remainingFillLoops) > 0:
2435 transferClosestFillLoop(extrusionHalfWidth, oldOrderedLocation, remainingFillLoops, skein)
2436
2437 - def transferInfillPaths(self, extrusionHalfWidth, oldOrderedLocation, skein, threadSequence):
2438 'Transfer the infill paths.'
2439 transferClosestPaths(oldOrderedLocation, self.infillPaths[:], skein)
2440
2447
2448
2450 'Complex path with a z.'
2452 self.path = []
2453 self.z = z
2454
2456 'Get the string representation of this path z.'
2457 return '%s, %s' % (self.z, self.path)
2458
2459
2461 'Class to define a projective space.'
2463 'Initialize the basis vectors.'
2464 self.basisX = basisX
2465 self.basisY = basisY
2466 self.basisZ = basisZ
2467
2469 'Get the string representation of this ProjectivePlane.'
2470 return '%s, %s, %s' % (self.basisX, self.basisY, self.basisZ)
2471
2473 'Get by x basis x and y basis.'
2474 self.basisX = basisX
2475 self.basisZ = basisZ
2476 self.basisX.normalize()
2477 self.basisY = basisZ.cross(self.basisX)
2478 self.basisY.normalize()
2479 return self
2480
2482 'Get by basisZ and first.'
2483 self.basisZ = basisZ
2484 self.basisY = basisZ.cross(firstVector3)
2485 self.basisY.normalize()
2486 self.basisX = self.basisY.cross(self.basisZ)
2487 self.basisX.normalize()
2488 return self
2489
2491 'Get by basisZ and top.'
2492 return self.getByBasisXZ(top.cross(basisZ), basisZ)
2493
2495 'Get by latitude and longitude.'
2496 longitudeComplex = getWiddershinsUnitPolar(math.radians(90.0 - viewpointLongitude))
2497 viewpointLatitudeRatio = getWiddershinsUnitPolar(math.radians(viewpointLatitude))
2498 basisZ = Vector3(viewpointLatitudeRatio.imag * longitudeComplex.real, viewpointLatitudeRatio.imag * longitudeComplex.imag, viewpointLatitudeRatio.real)
2499 return self.getByBasisXZ(Vector3(-longitudeComplex.imag, longitudeComplex.real, 0.0), basisZ)
2500
2502 'Get by latitude and longitude.'
2503 xPlaneAngle = getWiddershinsUnitPolar(tilt.real)
2504 self.basisX = Vector3(xPlaneAngle.real, 0.0, xPlaneAngle.imag)
2505 yPlaneAngle = getWiddershinsUnitPolar(tilt.imag)
2506 self.basisY = Vector3(0.0, yPlaneAngle.real, yPlaneAngle.imag)
2507 self.basisZ = self.basisX.cross(self.basisY)
2508 return self
2509
2511 'Get complex by complex point.'
2512 return self.basisX.dropAxis() * pointComplex.real + self.basisY.dropAxis() * pointComplex.imag
2513
2515 'Get copy.'
2516 return ProjectiveSpace(self.basisX, self.basisY, self.basisZ)
2517
2519 'Get the dot complex.'
2520 return complex(point.dot(self.basisX), point.dot(self.basisY))
2521
2523 'Get the dot vector3.'
2524 return Vector3(point.dot(self.basisX), point.dot(self.basisY), point.dot(self.basisZ))
2525
2544
2546 'Get space by angle and scale.'
2547 spaceByXYScaleRotation = ProjectiveSpace()
2548 planeAngle = getWiddershinsUnitPolar(angle)
2549 spaceByXYScaleRotation.basisX = self.basisX * scale.real * planeAngle.real + self.basisY * scale.imag * planeAngle.imag
2550 spaceByXYScaleRotation.basisY = -self.basisX * scale.real * planeAngle.imag + self.basisY * scale.imag * planeAngle.real
2551 spaceByXYScaleRotation.basisZ = self.basisZ
2552 return spaceByXYScaleRotation
2553
2555 'Get vector3 by point.'
2556 return self.basisX * point.x + self.basisY * point.y + self.basisZ * point.z
2557
2563
2564 - def unbuckle(self, maximumUnbuckling, normal):
2565 'Unbuckle space.'
2566 unbuckleBasis(self.basisX, maximumUnbuckling, normal)
2567 unbuckleBasis(self.basisY, maximumUnbuckling, normal)
2568
2569
2571 'A rotated layer.'
2573 self.loops = []
2574 self.rotation = None
2575 self.z = z
2576
2578 'Get the string representation of this rotated loop layer.'
2579 return '%s, %s, %s' % (self.z, self.rotation, self.loops)
2580
2581 - def addXML(self, depth, output):
2582 'Add the xml for this object.'
2583 if len(self.loops) < 1:
2584 return
2585 if len(self.loops) == 1:
2586 xml_simple_writer.addXMLFromLoopComplexZ({}, depth, self.loops[0], output, self.z)
2587 return
2588 xml_simple_writer.addBeginXMLTag({}, depth, 'group', output)
2589 for loop in self.loops:
2590 xml_simple_writer.addXMLFromLoopComplexZ({}, depth + 1, loop, output, self.z)
2591 xml_simple_writer.addEndXMLTag(depth, 'group', output)
2592
2594 'Get a raised copy.'
2595 raisedRotatedLoopLayer = RotatedLoopLayer(z)
2596 for loop in self.loops:
2597 raisedRotatedLoopLayer.loops.append(loop[:])
2598 raisedRotatedLoopLayer.rotation = self.rotation
2599 return raisedRotatedLoopLayer
2600
2602 'Get flattened nested rings.'
2603 flattenedNestedRings = []
2604 for nestedRing in nestedRings:
2605 nestedRing.addFlattenedNestedRings(flattenedNestedRings)
2606 return flattenedNestedRings
2607
2608
2610 'A class to hold the x intersection position and the index of the loop which intersected.'
2612 'Initialize.'
2613 self.index = index
2614 self.x = x
2615
2617 'Get comparison in order to sort x intersections in ascending order of x.'
2618 if self.x < other.x:
2619 return -1
2620 return int(self.x > other.x)
2621
2623 'Determine whether this XIntersectionIndex is identical to other one.'
2624 if other == None:
2625 return False
2626 if other.__class__ != self.__class__:
2627 return False
2628 return self.index == other.index and self.x == other.x
2629
2631 'Determine whether this XIntersectionIndex is not identical to other one.'
2632 return not self.__eq__(other)
2633
2635 'Get the string representation of this x intersection.'
2636 return 'XIntersectionIndex index %s; x %s ' % (self.index, self.x)
2637