2 Intercircle is a collection of utilities for intersecting circles, used to get smooth loops around a collection of points and inset & outset loops.
6 from __future__ import absolute_import
12 #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.
15 from fabmetheus_utilities.vector3 import Vector3
16 from fabmetheus_utilities import euclidean
20 __author__ = 'Enrique Perez (perez_enrique@yahoo.com)'
21 __date__ = '$Date: 2008/21/04 $'
22 __license__ = 'GNU Affero General Public License http://www.gnu.org/licenses/agpl.html'
25 globalDecreasingRadiusMultipliers = [1.0, 0.55, 0.35, 0.2]
26 globalIntercircleMultiplier = 1.04 # 1.02 is enough to stop known intersection
29 def addCircleIntersectionLoop(circleIntersectionLoop, circleIntersections):
30 'Add a circle intersection loop.'
31 firstCircleIntersection = circleIntersectionLoop[0]
32 circleIntersectionAhead = firstCircleIntersection
33 for circleIntersectionIndex in xrange(len(circleIntersections) + 1):
34 circleIntersectionAhead = circleIntersectionAhead.getCircleIntersectionAhead()
35 if circleIntersectionAhead == firstCircleIntersection or circleIntersectionAhead == None:
36 firstCircleIntersection.steppedOn = True
38 circleIntersectionAhead.addToList(circleIntersectionLoop)
39 firstCircleIntersection.steppedOn = True
40 print('Warning, addCircleIntersectionLoop would have gone into an endless loop.')
41 print('circleIntersectionLoop')
42 for circleIntersection in circleIntersectionLoop:
43 print(circleIntersection)
44 print(circleIntersection.circleNodeAhead)
45 print(circleIntersection.circleNodeBehind)
46 print('firstCircleIntersection')
47 print(firstCircleIntersection)
48 print('circleIntersections')
49 for circleIntersection in circleIntersections:
50 print(circleIntersection)
52 def addEndCap(begin, end, points, radius):
53 'Get circular end cap.'
54 beginMinusEnd = begin - end
55 beginMinusEndLength = abs(beginMinusEnd)
56 if beginMinusEndLength <= 0.0:
59 beginMinusEnd *= radius / beginMinusEndLength
60 perpendicular = complex(-beginMinusEnd.imag, beginMinusEnd.real)
61 numberOfSides = 20 # to end up with close to unit length corners, 5 * 4
62 numberOfPositiveSides = numberOfSides / 2
64 angle = euclidean.globalTau / float(numberOfSides)
65 # dotProductMultiplier to compensate for the corner outset in addInsetPointFromClockwiseTriple
66 dotProductMultiplier = 2.0 - 1.0 / math.cos(0.5 * angle)
67 for sideIndex in xrange(numberOfPositiveSides + 1):
68 circumferentialPoint = math.sin(totalAngle) * beginMinusEnd + math.cos(totalAngle) * perpendicular
69 points.append(begin + circumferentialPoint * dotProductMultiplier)
72 def addHalfPath(path, points, radius, thresholdRatio=0.9):
73 'Add the points from every point on a half path and between points.'
74 lessThanRadius = 0.75 * radius
75 for pointIndex in xrange(len(path) - 1):
76 begin = path[pointIndex]
77 center = path[pointIndex + 1]
78 centerBegin = getWiddershinsByLength(begin, center, radius)
79 if centerBegin != None:
80 addPointsFromSegment(begin + centerBegin, center + centerBegin, points, lessThanRadius, thresholdRatio)
81 endIndex = pointIndex + 2
82 if endIndex < len(path):
84 centerEnd = getWiddershinsByLength(center, end, radius)
85 if centerBegin != None and centerEnd != None:
86 centerPerpendicular = 0.5 * (centerBegin + centerEnd)
87 points.append(center + centerPerpendicular)
88 if euclidean.getCrossProduct(centerBegin, centerEnd) < 0.0:
89 points.append(center + centerBegin)
90 points.append(center + centerEnd)
93 addEndCap(path[0], path[1], points, radius)
95 def addInsetPointFromClockwiseTriple(begin, center, end, loop, radius):
96 'Get inset point with possible intersection from clockwise triple, out from widdershins loop.'
97 centerMinusBegin = center - begin
98 centerMinusBeginLength = abs(centerMinusBegin)
99 centerMinusBeginClockwise = None
100 if centerMinusBeginLength > 0.0:
101 centerMinusBeginClockwise = complex(centerMinusBegin.imag, -centerMinusBegin.real) / centerMinusBeginLength
102 endMinusCenter = end - center
103 endMinusCenterLength = abs(endMinusCenter)
104 endMinusCenterClockwise = None
105 if endMinusCenterLength > 0.0:
106 endMinusCenterClockwise = complex(endMinusCenter.imag, -endMinusCenter.real) / endMinusCenterLength
107 if centerMinusBeginClockwise == None and endMinusCenterClockwise == None:
109 if centerMinusBeginClockwise == None:
110 loop.append(center + endMinusCenterClockwise * radius)
112 if endMinusCenterClockwise == None:
113 loop.append(center + centerMinusBeginClockwise * radius)
115 centerClockwise = 0.5 * (centerMinusBeginClockwise + endMinusCenterClockwise)
116 dotProduct = euclidean.getDotProduct(centerMinusBeginClockwise, centerClockwise)
117 loop.append(center + centerClockwise * radius / max(0.4, abs(dotProduct))) # 0.4 to avoid pointy corners
119 def addOrbits( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z ):
120 'Add orbits with the extruder off.'
122 while timeInOrbit < temperatureChangeTime:
124 distanceFeedRate.addGcodeMovementZWithFeedRate( 60.0 * orbitalFeedRatePerSecond, point, z )
125 timeInOrbit += euclidean.getLoopLength(loop) / orbitalFeedRatePerSecond
127 def addOrbitsIfLarge( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z ):
128 'Add orbits with the extruder off if the orbits are large enough.'
129 if orbitsAreLarge( loop, temperatureChangeTime ):
130 addOrbits( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z )
132 def addPointsFromSegment( pointBegin, pointEnd, points, radius, thresholdRatio=0.9 ):
133 'Add point complexes between the endpoints of a segment.'
135 print('This should never happen, radius should never be zero or less in addPointsFromSegment in intercircle.')
136 thresholdRadius = radius * thresholdRatio # a higher number would be faster but would leave bigger dangling loops and extra dangling loops.
137 thresholdDiameter = thresholdRadius + thresholdRadius
138 segment = pointEnd - pointBegin
139 segmentLength = abs(segment)
140 extraCircles = int( math.floor( segmentLength / thresholdDiameter ) )
143 if segmentLength == 0.0:
144 print('Warning, segmentLength = 0.0 in intercircle.')
150 lengthIncrement = segmentLength / ( float(extraCircles) + 1.0 )
151 segment *= lengthIncrement / segmentLength
152 pointBegin += segment
154 pointBegin += segment * thresholdDiameter / segmentLength
155 remainingLength = segmentLength - thresholdDiameter - thresholdDiameter
156 lengthIncrement = remainingLength / ( float(extraCircles) - 1.0 )
157 segment *= lengthIncrement / segmentLength
158 for circleIndex in xrange(extraCircles):
159 points.append( pointBegin )
160 pointBegin += segment
162 def directLoop(isWiddershins, loop):
164 if euclidean.isWiddershins(loop) != isWiddershins:
167 def directLoopLists(isWiddershins, loopLists):
168 'Direct the loop lists.'
169 for loopList in loopLists:
170 directLoops(isWiddershins, loopList)
172 def directLoops(isWiddershins, loops):
175 directLoop(isWiddershins, loop)
177 def getAroundsFromLoop(loop, radius, thresholdRatio=0.9):
178 'Get the arounds from the loop.'
179 return getAroundsFromPoints(getPointsFromLoop(loop, radius, thresholdRatio), radius)
181 def getAroundsFromLoops( loops, radius, thresholdRatio=0.9 ):
182 'Get the arounds from the loops.'
183 return getAroundsFromPoints(getPointsFromLoops(loops, radius, thresholdRatio), radius)
185 def getAroundsFromPath(path, radius, thresholdRatio=0.9):
186 'Get the arounds from the path.'
188 points = getPointsFromPath(path, radius, thresholdRatio)
189 return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
191 def getAroundsFromPathPoints(points, radius, thresholdRatio=0.9):
192 'Get the arounds from the path.'
193 centers = getCentersFromPoints(points, 0.8 * radius)
195 for center in centers:
196 if euclidean.isWiddershins(center):
197 arounds.append(euclidean.getSimplifiedPath(center, radius))
200 def getAroundsFromPaths(paths, radius, thresholdRatio=0.9):
201 'Get the arounds from the path.'
205 points += getPointsFromPath(path, radius, thresholdRatio)
206 return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
208 def getAroundsFromPoints( points, radius ):
209 'Get the arounds from the points.'
212 centers = getCentersFromPoints(points, globalIntercircleMultiplier * radius)
213 for center in centers:
214 inset = getSimplifiedInsetFromClockwiseLoop(center, radius)
215 if isLargeSameDirection(inset, center, radius):
216 arounds.append(inset)
219 def getCentersFromCircleNodes( circleNodes, radius ):
220 'Get the complex centers of the circle intersection loops from circle nodes.'
221 if len( circleNodes ) < 2:
223 circleIntersections = getCircleIntersectionsFromCircleNodes( circleNodes )
224 circleIntersectionLoops = getCircleIntersectionLoops( circleIntersections )
225 return getCentersFromIntersectionLoops( circleIntersectionLoops, radius )
227 def getCentersFromIntersectionLoop(circleIntersectionLoop, radius):
228 'Get the centers from the intersection loop.'
230 for circleIntersection in circleIntersectionLoop:
231 loop.append(circleIntersection.circleNodeAhead.actualPoint)
234 def getCentersFromIntersectionLoops( circleIntersectionLoops, radius ):
235 'Get the centers from the intersection loops.'
237 for circleIntersectionLoop in circleIntersectionLoops:
238 centers.append( getCentersFromIntersectionLoop( circleIntersectionLoop, radius ) )
241 def getCentersFromLoop( loop, radius ):
242 'Get the centers of the loop.'
243 circleNodes = getCircleNodesFromLoop( loop, radius )
244 return getCentersFromCircleNodes( circleNodes, radius )
246 def getCentersFromLoopDirection( isWiddershins, loop, radius ):
247 'Get the centers of the loop which go around in the given direction.'
248 centers = getCentersFromLoop( loop, radius )
249 return getLoopsFromLoopsDirection( isWiddershins, centers )
251 def getCentersFromPoints(points, radius):
252 'Get the centers from the points.'
253 circleNodes = getCircleNodesFromPoints(points, abs(radius))
254 return getCentersFromCircleNodes(circleNodes, abs(radius))
256 def getCircleIntersectionLoops( circleIntersections ):
257 'Get all the loops going through the circle intersections.'
258 circleIntersectionLoops = []
259 for circleIntersection in circleIntersections:
260 if not circleIntersection.steppedOn:
261 circleIntersectionLoop = [ circleIntersection ]
262 circleIntersectionLoops.append( circleIntersectionLoop )
263 addCircleIntersectionLoop( circleIntersectionLoop, circleIntersections )
264 return circleIntersectionLoops
266 def getCircleIntersectionsFromCircleNodes(circleNodes):
267 'Get all the circle intersections which exist between all the circle nodes.'
268 if len( circleNodes ) < 1:
270 circleIntersections = []
273 for circleNode in circleNodes:
274 euclidean.addElementToPixelListFromPoint(circleNode, pixelTable, circleNode.dividedPoint)
275 accumulatedCircleNodeTable = {}
276 for circleNodeIndex in xrange(len(circleNodes)):
277 circleNodeBehind = circleNodes[circleNodeIndex]
278 circleNodeIndexMinusOne = circleNodeIndex - 1
279 if circleNodeIndexMinusOne >= 0:
280 circleNodeAdditional = circleNodes[circleNodeIndexMinusOne]
281 euclidean.addElementToPixelListFromPoint(circleNodeAdditional, accumulatedCircleNodeTable, 0.5 * circleNodeAdditional.dividedPoint)
282 withinNodes = circleNodeBehind.getWithinNodes(accumulatedCircleNodeTable)
283 for circleNodeAhead in withinNodes:
284 circleIntersectionForward = CircleIntersection(circleNodeAhead, index, circleNodeBehind)
285 if not circleIntersectionForward.isWithinCircles(pixelTable):
286 circleIntersections.append(circleIntersectionForward)
287 circleNodeBehind.circleIntersections.append(circleIntersectionForward)
289 circleIntersectionBackward = CircleIntersection(circleNodeBehind, index, circleNodeAhead)
290 if not circleIntersectionBackward.isWithinCircles(pixelTable):
291 circleIntersections.append(circleIntersectionBackward)
292 circleNodeAhead.circleIntersections.append(circleIntersectionBackward)
294 return circleIntersections
296 def getCircleNodesFromLoop(loop, radius, thresholdRatio=0.9):
297 'Get the circle nodes from every point on a loop and between points.'
299 points = getPointsFromLoop( loop, radius, thresholdRatio )
300 return getCircleNodesFromPoints( points, radius )
302 def getCircleNodesFromPoints(points, radius):
303 'Get the circle nodes from a path.'
305 print('Warning, radius is 0 in getCircleNodesFromPoints in intercircle.')
309 oneOverRadius = 1.000001 / radius # to avoid problem of accidentally integral radius
310 points = euclidean.getAwayPoints(points, radius)
312 circleNodes.append(CircleNode(oneOverRadius, point))
315 def getInsetLoopsFromLoop(loop, radius, thresholdRatio=0.9):
316 'Get the inset loops, which might overlap.'
321 isLoopWiddershins = euclidean.isWiddershins(loop)
322 arounds = getAroundsFromLoop(loop, radius, thresholdRatio)
323 for around in arounds:
324 leftPoint = euclidean.getLeftPoint(around)
325 shouldBeWithin = (isInset == isLoopWiddershins)
326 if euclidean.isPointInsideLoop(loop, leftPoint) == shouldBeWithin:
327 if isLoopWiddershins != euclidean.isWiddershins(around):
329 insetLoops.append(around)
332 def getInsetLoopsFromLoops(loops, radius):
333 'Get the inset loops, which might overlap.'
336 insetLoops += getInsetLoopsFromLoop(loop, radius)
339 def getInsetLoopsFromVector3Loop(loop, radius, thresholdRatio=0.9):
340 'Get the inset loops from vector3 loop, which might overlap.'
343 loopComplex = euclidean.getComplexPath(loop)
344 loopComplexes = getInsetLoopsFromLoop(loopComplex, radius)
345 return euclidean.getVector3Paths(loopComplexes, loop[0].z)
347 def getInsetSeparateLoopsFromLoops(loops, radius, thresholdRatio=0.9):
348 'Get the separate inset loops.'
352 insetSeparateLoops = []
353 arounds = getAroundsFromLoops(loops, abs(radius), thresholdRatio)
354 for around in arounds:
355 if isInset == euclidean.getIsInFilledRegion(loops, around[0]):
358 insetSeparateLoops.append(around)
359 return insetSeparateLoops
361 def getInsetSeparateLoopsFromAroundLoops(loops, radius, radiusAround, thresholdRatio=0.9):
362 'Get the separate inset loops.'
366 insetSeparateLoops = []
368 radiusAround = max(abs(radiusAround), radius)
369 points = getPointsFromLoops(loops, radiusAround, thresholdRatio)
370 centers = getCentersFromPoints(points, globalIntercircleMultiplier * radiusAround)
371 for center in centers:
372 inset = getSimplifiedInsetFromClockwiseLoop(center, radius)
373 if isLargeSameDirection(inset, center, radius):
374 if isInset == euclidean.getIsInFilledRegion(loops, inset[0]):
377 insetSeparateLoops.append(inset)
378 return insetSeparateLoops
380 def getIsLarge(loop, radius):
381 'Determine if the loop is large enough.'
382 return euclidean.getMaximumSpan(loop) > 2.01 * abs(radius)
384 def getLargestCenterOutsetLoopFromLoop(loop, radius, thresholdRatio=0.9):
385 'Get the largest circle outset loop from the loop.'
389 points = getPointsFromLoop(loop, radius, thresholdRatio)
390 centers = getCentersFromPoints(points, globalIntercircleMultiplier * radius)
391 largestCenterOutset = None
392 largestOutsetArea = -987654321.0
393 for center in centers:
394 outset = getSimplifiedInsetFromClockwiseLoop(center, radius)
395 if isLargeSameDirection(outset, center, radius):
396 if euclidean.isPathInsideLoop(loop, outset) != euclidean.isWiddershins(loop):
397 centerOutset = CenterOutset(center, outset)
398 outsetArea = abs(euclidean.getAreaLoop(outset))
399 if outsetArea > largestOutsetArea:
400 largestOutsetArea = outsetArea
401 largestCenterOutset = centerOutset
402 if largestCenterOutset == None:
404 largestCenterOutset.center = euclidean.getSimplifiedLoop(largestCenterOutset.center, radius)
405 return largestCenterOutset
407 def getLargestCenterOutsetLoopFromLoopRegardless(loop, radius):
408 'Get the largest circle outset loop from the loop, even if the radius has to be shrunk and even if there is still no outset loop.'
409 global globalDecreasingRadiusMultipliers
410 for decreasingRadiusMultiplier in globalDecreasingRadiusMultipliers:
411 decreasingRadius = radius * decreasingRadiusMultiplier
412 largestCenterOutsetLoop = getLargestCenterOutsetLoopFromLoop(loop, decreasingRadius)
413 if largestCenterOutsetLoop != None:
414 return largestCenterOutsetLoop
415 return CenterOutset(loop, loop)
417 def getLargestInsetLoopFromLoop(loop, radius):
418 'Get the largest inset loop from the loop.'
419 loops = getInsetLoopsFromLoop(loop, radius)
420 return euclidean.getLargestLoop(loops)
422 def getLargestInsetLoopFromLoopRegardless( loop, radius ):
423 'Get the largest inset loop from the loop, even if the radius has to be shrunk and even if there is still no inset loop.'
424 global globalDecreasingRadiusMultipliers
425 for decreasingRadiusMultiplier in globalDecreasingRadiusMultipliers:
426 decreasingRadius = radius * decreasingRadiusMultiplier
427 largestInsetLoop = getLargestInsetLoopFromLoop( loop, decreasingRadius )
428 if len( largestInsetLoop ) > 0:
429 return largestInsetLoop
430 print('Warning, there should always be a largestInsetLoop in getLargestInsetLoopFromLoopRegardless in intercircle.')
434 def getLoopsFromLoopsDirection( isWiddershins, loops ):
435 'Get the loops going round in a given direction.'
436 directionalLoops = []
438 if euclidean.isWiddershins(loop) == isWiddershins:
439 directionalLoops.append(loop)
440 return directionalLoops
442 def getPointsFromLoop(loop, radius, thresholdRatio=0.9):
443 'Get the points from every point on a loop and between points.'
445 print('Warning, radius is 0 in getPointsFromLoop in intercircle.')
450 for pointIndex in xrange(len(loop)):
451 pointBegin = loop[pointIndex]
452 pointEnd = loop[(pointIndex + 1) % len(loop)]
453 points.append( pointBegin )
454 addPointsFromSegment( pointBegin, pointEnd, points, radius, thresholdRatio )
457 def getPointsFromLoops(loops, radius, thresholdRatio=0.9):
458 'Get the points from every point on a loop and between points.'
461 points += getPointsFromLoop(loop, radius, thresholdRatio)
464 def getPointsFromPath(path, radius, thresholdRatio=0.9):
465 'Get the points from every point on a path and between points.'
472 addHalfPath(path, points, radius, thresholdRatio)
473 addHalfPath(path[: : -1], points, radius, thresholdRatio)
476 def getSimplifiedInsetFromClockwiseLoop(loop, radius):
477 'Get loop inset from clockwise loop, out from widdershins loop.'
479 for pointIndex, begin in enumerate(loop):
480 center = loop[(pointIndex + 1) % len(loop)]
481 end = loop[(pointIndex + 2) % len(loop)]
482 addInsetPointFromClockwiseTriple(begin, center, end, inset, radius)
483 return getWithoutIntersections(euclidean.getSimplifiedLoop(inset, radius))
485 def getWiddershinsByLength(begin, end, length):
486 'Get the widdershins by length.'
487 endMinusBegin = end - begin
488 endMinusBeginLength = abs(endMinusBegin)
489 if endMinusBeginLength <= 0.0:
491 endMinusBegin *= length / endMinusBeginLength
492 return complex(-endMinusBegin.imag, endMinusBegin.real)
494 def getWithoutIntersections( loop ):
495 'Get loop without intersections.'
496 lastLoopLength = len( loop )
497 while lastLoopLength > 3:
498 removeIntersection( loop )
499 if len( loop ) == lastLoopLength:
501 lastLoopLength = len( loop )
504 def isLargeSameDirection(inset, loop, radius):
505 'Determine if the inset is in the same direction as the loop and it is large enough.'
506 if euclidean.isWiddershins(inset) != euclidean.isWiddershins(loop):
508 return getIsLarge(inset, radius) and len(inset) > 2
510 def isLoopIntersectingLoop( anotherLoop, loop ):
511 'Determine if the a loop is intersecting another loop.'
512 for pointIndex in xrange(len(loop)):
513 pointFirst = loop[pointIndex]
514 pointSecond = loop[(pointIndex + 1) % len(loop)]
515 segment = pointFirst - pointSecond
516 normalizedSegment = euclidean.getNormalized(segment)
517 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
518 segmentFirstPoint = segmentYMirror * pointFirst
519 segmentSecondPoint = segmentYMirror * pointSecond
520 if euclidean.isLoopIntersectingInsideXSegment( anotherLoop, segmentFirstPoint.real, segmentSecondPoint.real, segmentYMirror, segmentFirstPoint.imag ):
524 def orbitsAreLarge( loop, temperatureChangeTime ):
525 'Determine if the orbits are large enough.'
527 print('Zero length loop which was skipped over, this should never happen.')
529 return temperatureChangeTime > 1.5
531 def removeIntersection( loop ):
532 'Get loop without the first intersection.'
533 for pointIndex, ahead in enumerate(loop):
534 behind = loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ]
535 behindEnd = loop[ ( pointIndex + len( loop ) - 2 ) % len( loop ) ]
536 behindMidpoint = 0.5 * ( behind + behindEnd )
537 aheadEnd = loop[ (pointIndex + 1) % len( loop ) ]
538 aheadMidpoint = 0.5 * ( ahead + aheadEnd )
539 normalizedSegment = behind - behindMidpoint
540 normalizedSegmentLength = abs( normalizedSegment )
541 if normalizedSegmentLength > 0.0:
542 normalizedSegment /= normalizedSegmentLength
543 segmentYMirror = complex(normalizedSegment.real, -normalizedSegment.imag)
544 behindRotated = segmentYMirror * behind
545 behindMidpointRotated = segmentYMirror * behindMidpoint
546 aheadRotated = segmentYMirror * ahead
547 aheadMidpointRotated = segmentYMirror * aheadMidpoint
548 y = behindRotated.imag
549 xIntersection = euclidean.getXIntersectionIfExists( aheadRotated, aheadMidpointRotated, y )
550 if xIntersection != None:
551 if xIntersection > min( behindMidpointRotated.real, behindRotated.real ) and xIntersection < max( behindMidpointRotated.real, behindRotated.real ):
552 intersectionPoint = normalizedSegment * complex( xIntersection, y )
553 loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ] = intersectionPoint
559 'A class to hold a bounding loop composed of a minimum complex, a maximum complex and an outset loop.'
560 def __eq__(self, other):
561 'Determine whether this bounding loop is identical to other one.'
564 return self.minimum == other.minimum and self.maximum == other.maximum and self.loop == other.loop
567 'Get the string representation of this bounding loop.'
568 return '%s, %s, %s' % ( self.minimum, self.maximum, self.loop )
570 def getFromLoop( self, loop ):
571 'Get the bounding loop from a path.'
573 self.maximum = euclidean.getMaximumByComplexPath(loop)
574 self.minimum = euclidean.getMinimumByComplexPath(loop)
577 def getOutsetBoundingLoop( self, outsetDistance ):
578 'Outset the bounding rectangle and loop by a distance.'
579 outsetBoundingLoop = BoundingLoop()
580 outsetBoundingLoop.maximum = self.maximum + complex( outsetDistance, outsetDistance )
581 outsetBoundingLoop.minimum = self.minimum - complex( outsetDistance, outsetDistance )
582 greaterThanOutsetDistance = 1.1 * outsetDistance
583 centers = getCentersFromLoopDirection( True, self.loop, greaterThanOutsetDistance )
584 outsetBoundingLoop.loop = getSimplifiedInsetFromClockwiseLoop( centers[0], outsetDistance )
585 return outsetBoundingLoop
587 def isEntirelyInsideAnother( self, anotherBoundingLoop ):
588 'Determine if this bounding loop is entirely inside another bounding loop.'
589 if self.minimum.imag < anotherBoundingLoop.minimum.imag or self.minimum.real < anotherBoundingLoop.minimum.real:
591 if self.maximum.imag > anotherBoundingLoop.maximum.imag or self.maximum.real > anotherBoundingLoop.maximum.real:
593 for point in self.loop:
594 if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 0:
596 return not isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
598 def isOverlappingAnother( self, anotherBoundingLoop ):
599 'Determine if this bounding loop is intersecting another bounding loop.'
600 if self.isRectangleMissingAnother( anotherBoundingLoop ):
602 for point in self.loop:
603 if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 1:
605 for point in anotherBoundingLoop.loop:
606 if euclidean.getNumberOfIntersectionsToLeft( self.loop, point ) % 2 == 1:
608 return isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
610 def isOverlappingAnotherInList( self, boundingLoops ):
611 'Determine if this bounding loop is intersecting another bounding loop in a list.'
612 for boundingLoop in boundingLoops:
613 if self.isOverlappingAnother( boundingLoop ):
617 def isRectangleMissingAnother( self, anotherBoundingLoop ):
618 'Determine if the rectangle of this bounding loop is missing the rectangle of another bounding loop.'
619 if self.maximum.imag < anotherBoundingLoop.minimum.imag or self.maximum.real < anotherBoundingLoop.minimum.real:
621 return self.minimum.imag > anotherBoundingLoop.maximum.imag or self.minimum.real > anotherBoundingLoop.maximum.real
625 'A class to hold a center and an outset.'
626 def __init__(self, center, outset):
627 'Set the center and outset.'
632 'Get the string representation of this CenterOutset.'
633 return '%s\n%s' % (self.center, self.outset)
636 class CircleIntersection:
637 'An intersection of two complex circles.'
638 def __init__( self, circleNodeAhead, index, circleNodeBehind ):
639 self.aheadMinusBehind = 0.5 * ( circleNodeAhead.dividedPoint - circleNodeBehind.dividedPoint )
640 self.circleNodeAhead = circleNodeAhead
641 self.circleNodeBehind = circleNodeBehind
643 self.steppedOn = False
644 demichordWidth = math.sqrt( 1.0 - self.aheadMinusBehind.real * self.aheadMinusBehind.real - self.aheadMinusBehind.imag * self.aheadMinusBehind.imag )
645 rotatedClockwiseQuarter = complex( self.aheadMinusBehind.imag, - self.aheadMinusBehind.real )
646 rotatedClockwiseQuarterLength = abs( rotatedClockwiseQuarter )
647 if rotatedClockwiseQuarterLength == 0:
648 print('Warning, rotatedClockwiseQuarter in getDemichord in intercircle is 0')
649 print(circleNodeAhead.dividedPoint)
650 print(circleNodeBehind.dividedPoint)
653 self.demichord = rotatedClockwiseQuarter * demichordWidth / rotatedClockwiseQuarterLength
654 self.positionRelativeToBehind = self.aheadMinusBehind + self.demichord
657 'Get the string representation of this CircleIntersection.'
658 return '%s, %s, %s, %s' % (self.index, self.getAbsolutePosition(), self.circleNodeBehind, self.circleNodeAhead)
660 def addToList( self, circleIntersectionPath ):
661 'Add this to the circle intersection path, setting stepped on to be true.'
662 self.steppedOn = True
663 circleIntersectionPath.append(self)
665 def getAbsolutePosition(self):
666 'Get the absolute position.'
667 return self.positionRelativeToBehind + self.circleNodeBehind.dividedPoint
669 def getCircleIntersectionAhead(self):
670 'Get the first circle intersection on the circle node ahead.'
671 circleIntersections = self.circleNodeAhead.circleIntersections
672 circleIntersectionAhead = None
673 largestDot = -912345678.0
674 for circleIntersection in circleIntersections:
675 if not circleIntersection.steppedOn:
676 circleIntersectionRelativeToMidpoint = euclidean.getNormalized(circleIntersection.positionRelativeToBehind + self.aheadMinusBehind)
677 dot = euclidean.getDotProduct(self.demichord, circleIntersectionRelativeToMidpoint)
680 circleIntersectionAhead = circleIntersection
681 if circleIntersectionAhead == None:
682 print('Warning, circleIntersectionAhead in getCircleIntersectionAhead in intercircle is None for:')
683 print(self.circleNodeAhead.dividedPoint)
684 print('circleIntersectionsAhead')
685 for circleIntersection in circleIntersections:
686 print(circleIntersection.circleNodeAhead.dividedPoint)
687 print('circleIntersectionsBehind')
688 for circleIntersection in self.circleNodeBehind.circleIntersections:
689 print(circleIntersection.circleNodeAhead.dividedPoint)
690 print('This may lead to a loop not being sliced.')
691 print('If this is a problem, you may as well send a bug report, even though I probably can not fix this particular problem.')
692 return circleIntersectionAhead
694 def isWithinCircles(self, pixelTable):
695 'Determine if this circle intersection is within the circle node circles.'
696 absolutePosition = self.getAbsolutePosition()
697 squareValues = euclidean.getSquareValuesFromPoint(pixelTable, absolutePosition)
698 for squareValue in squareValues:
699 if abs(squareValue.dividedPoint - absolutePosition) < 1.0:
700 if squareValue != self.circleNodeAhead and squareValue != self.circleNodeBehind:
706 'A complex node of complex circle intersections.'
707 def __init__(self, oneOverRadius, point):
708 self.actualPoint = point
709 self.circleIntersections = []
710 self.dividedPoint = point * oneOverRadius
711 # self.index = index # when debugging bring back index
714 'Get the string representation of this CircleNode.'
715 # return '%s, %s, %s' % (self.index, self.dividedPoint, len(self.circleIntersections)) # when debugging bring back index
716 return '%s, %s' % (self.dividedPoint, len(self.circleIntersections))
718 def getWithinNodes(self, pixelTable):
719 'Get the nodes this circle node is within.'
721 squareValues = euclidean.getSquareValuesFromPoint(pixelTable, 0.5 * self.dividedPoint)
722 for squareValue in squareValues:
723 if abs(self.dividedPoint - squareValue.dividedPoint) < 2.0:
724 withinNodes.append(squareValue)