chiark / gitweb /
Move SF into its own directory, to seperate SF and Cura. Rename newui to gui.
[cura.git] / Cura / cura_sf / fabmetheus_utilities / intercircle.py
1 """
2 Intercircle is a collection of utilities for intersecting circles, used to get smooth loops around a collection of points and inset & outset loops.
3
4 """
5
6 from __future__ import absolute_import
7 try:
8         import psyco
9         psyco.full()
10 except:
11         pass
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.
13 import __init__
14
15 from fabmetheus_utilities.vector3 import Vector3
16 from fabmetheus_utilities import euclidean
17 import math
18
19
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'
23
24
25 globalDecreasingRadiusMultipliers = [1.0, 0.55, 0.35, 0.2]
26 globalIntercircleMultiplier = 1.04 # 1.02 is enough to stop known intersection
27
28
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
37                         return
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)
51
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:
57                 points.append(begin)
58                 return
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
63         totalAngle = 0.0
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)
70                 totalAngle += angle
71
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):
83                         end = path[endIndex]
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)
91                         else:
92                                 points.append(center)
93         addEndCap(path[0], path[1], points, radius)
94
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:
108                 return
109         if centerMinusBeginClockwise == None:
110                 loop.append(center + endMinusCenterClockwise * radius)
111                 return
112         if endMinusCenterClockwise == None:
113                 loop.append(center + centerMinusBeginClockwise * radius)
114                 return
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
118
119 def addOrbits( distanceFeedRate, loop, orbitalFeedRatePerSecond, temperatureChangeTime, z ):
120         'Add orbits with the extruder off.'
121         timeInOrbit = 0.0
122         while timeInOrbit < temperatureChangeTime:
123                 for point in loop:
124                         distanceFeedRate.addGcodeMovementZWithFeedRate( 60.0 * orbitalFeedRatePerSecond, point, z )
125                 timeInOrbit += euclidean.getLoopLength(loop) / orbitalFeedRatePerSecond
126
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 )
131
132 def addPointsFromSegment( pointBegin, pointEnd, points, radius, thresholdRatio=0.9 ):
133         'Add point complexes between the endpoints of a segment.'
134         if radius <= 0.0:
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 ) )
141         if extraCircles < 1:
142                 return
143         if segmentLength == 0.0:
144                 print('Warning, segmentLength = 0.0 in intercircle.')
145                 print('pointBegin')
146                 print(pointBegin)
147                 print(pointEnd)
148                 return
149         if extraCircles < 2:
150                 lengthIncrement = segmentLength / ( float(extraCircles) + 1.0 )
151                 segment *= lengthIncrement / segmentLength
152                 pointBegin += segment
153         else:
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
161
162 def directLoop(isWiddershins, loop):
163         'Direct the loop.'
164         if euclidean.isWiddershins(loop) != isWiddershins:
165                 loop.reverse()
166
167 def directLoopLists(isWiddershins, loopLists):
168         'Direct the loop lists.'
169         for loopList in loopLists:
170                 directLoops(isWiddershins, loopList)
171
172 def directLoops(isWiddershins, loops):
173         'Direct the loops.'
174         for loop in loops:
175                 directLoop(isWiddershins, loop)
176
177 def getAroundsFromLoop(loop, radius, thresholdRatio=0.9):
178         'Get the arounds from the loop.'
179         return getAroundsFromPoints(getPointsFromLoop(loop, radius, thresholdRatio), radius)
180
181 def getAroundsFromLoops( loops, radius, thresholdRatio=0.9 ):
182         'Get the arounds from the loops.'
183         return getAroundsFromPoints(getPointsFromLoops(loops, radius, thresholdRatio), radius)
184
185 def getAroundsFromPath(path, radius, thresholdRatio=0.9):
186         'Get the arounds from the path.'
187         radius = abs(radius)
188         points = getPointsFromPath(path, radius, thresholdRatio)
189         return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
190
191 def getAroundsFromPathPoints(points, radius, thresholdRatio=0.9):
192         'Get the arounds from the path.'
193         centers = getCentersFromPoints(points, 0.8 * radius)
194         arounds = []
195         for center in centers:
196                 if euclidean.isWiddershins(center):
197                         arounds.append(euclidean.getSimplifiedPath(center, radius))
198         return arounds
199
200 def getAroundsFromPaths(paths, radius, thresholdRatio=0.9):
201         'Get the arounds from the path.'
202         radius = abs(radius)
203         points = []
204         for path in paths:
205                 points += getPointsFromPath(path, radius, thresholdRatio)
206         return getAroundsFromPathPoints(points, radius, thresholdRatio=0.9)
207
208 def getAroundsFromPoints( points, radius ):
209         'Get the arounds from the points.'
210         arounds = []
211         radius = abs(radius)
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)
217         return arounds
218
219 def getCentersFromCircleNodes( circleNodes, radius ):
220         'Get the complex centers of the circle intersection loops from circle nodes.'
221         if len( circleNodes ) < 2:
222                 return []
223         circleIntersections = getCircleIntersectionsFromCircleNodes( circleNodes )
224         circleIntersectionLoops = getCircleIntersectionLoops( circleIntersections )
225         return getCentersFromIntersectionLoops( circleIntersectionLoops, radius )
226
227 def getCentersFromIntersectionLoop(circleIntersectionLoop, radius):
228         'Get the centers from the intersection loop.'
229         loop = []
230         for circleIntersection in circleIntersectionLoop:
231                 loop.append(circleIntersection.circleNodeAhead.actualPoint)
232         return loop
233
234 def getCentersFromIntersectionLoops( circleIntersectionLoops, radius ):
235         'Get the centers from the intersection loops.'
236         centers = []
237         for circleIntersectionLoop in circleIntersectionLoops:
238                 centers.append( getCentersFromIntersectionLoop( circleIntersectionLoop, radius ) )
239         return centers
240
241 def getCentersFromLoop( loop, radius ):
242         'Get the centers of the loop.'
243         circleNodes = getCircleNodesFromLoop( loop, radius )
244         return getCentersFromCircleNodes( circleNodes, radius )
245
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 )
250
251 def getCentersFromPoints(points, radius):
252         'Get the centers from the points.'
253         circleNodes = getCircleNodesFromPoints(points, abs(radius))
254         return getCentersFromCircleNodes(circleNodes, abs(radius))
255
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
265
266 def getCircleIntersectionsFromCircleNodes(circleNodes):
267         'Get all the circle intersections which exist between all the circle nodes.'
268         if len( circleNodes ) < 1:
269                 return []
270         circleIntersections = []
271         index = 0
272         pixelTable = {}
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)
288                                 index += 1
289                         circleIntersectionBackward = CircleIntersection(circleNodeBehind, index, circleNodeAhead)
290                         if not circleIntersectionBackward.isWithinCircles(pixelTable):
291                                 circleIntersections.append(circleIntersectionBackward)
292                                 circleNodeAhead.circleIntersections.append(circleIntersectionBackward)
293                                 index += 1
294         return circleIntersections
295
296 def getCircleNodesFromLoop(loop, radius, thresholdRatio=0.9):
297         'Get the circle nodes from every point on a loop and between points.'
298         radius = abs(radius)
299         points = getPointsFromLoop( loop, radius, thresholdRatio )
300         return getCircleNodesFromPoints( points, radius )
301
302 def getCircleNodesFromPoints(points, radius):
303         'Get the circle nodes from a path.'
304         if radius == 0.0:
305                 print('Warning, radius is 0 in getCircleNodesFromPoints in intercircle.')
306                 print(points)
307                 return []
308         circleNodes = []
309         oneOverRadius = 1.000001 / radius # to avoid problem of accidentally integral radius
310         points = euclidean.getAwayPoints(points, radius)
311         for point in points:
312                 circleNodes.append(CircleNode(oneOverRadius, point))
313         return circleNodes
314
315 def getInsetLoopsFromLoop(loop, radius, thresholdRatio=0.9):
316         'Get the inset loops, which might overlap.'
317         if radius == 0.0:
318                 return [loop]
319         isInset = radius > 0
320         insetLoops = []
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):
328                                 around.reverse()
329                         insetLoops.append(around)
330         return insetLoops
331
332 def getInsetLoopsFromLoops(loops, radius):
333         'Get the inset loops, which might overlap.'
334         insetLoops = []
335         for loop in loops:
336                 insetLoops += getInsetLoopsFromLoop(loop, radius)
337         return insetLoops
338
339 def getInsetLoopsFromVector3Loop(loop, radius, thresholdRatio=0.9):
340         'Get the inset loops from vector3 loop, which might overlap.'
341         if len(loop) < 2:
342                 return [loop]
343         loopComplex = euclidean.getComplexPath(loop)
344         loopComplexes = getInsetLoopsFromLoop(loopComplex, radius)
345         return euclidean.getVector3Paths(loopComplexes, loop[0].z)
346
347 def getInsetSeparateLoopsFromLoops(loops, radius, thresholdRatio=0.9):
348         'Get the separate inset loops.'
349         if radius == 0.0:
350                 return loops
351         isInset = radius > 0
352         insetSeparateLoops = []
353         arounds = getAroundsFromLoops(loops, abs(radius), thresholdRatio)
354         for around in arounds:
355                 if isInset == euclidean.getIsInFilledRegion(loops, around[0]):
356                         if isInset:
357                                 around.reverse()
358                         insetSeparateLoops.append(around)
359         return insetSeparateLoops
360
361 def getInsetSeparateLoopsFromAroundLoops(loops, radius, radiusAround, thresholdRatio=0.9):
362         'Get the separate inset loops.'
363         if radius == 0.0:
364                 return loops
365         isInset = radius > 0
366         insetSeparateLoops = []
367         radius = abs(radius)
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]):
375                                 if isInset:
376                                         inset.reverse()
377                                 insetSeparateLoops.append(inset)
378         return insetSeparateLoops
379
380 def getIsLarge(loop, radius):
381         'Determine if the loop is large enough.'
382         return euclidean.getMaximumSpan(loop) > 2.01 * abs(radius)
383
384 def getLargestCenterOutsetLoopFromLoop(loop, radius, thresholdRatio=0.9):
385         'Get the largest circle outset loop from the loop.'
386         if radius == 0.0:
387                 return loop
388         radius = abs(radius)
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:
403                 return None
404         largestCenterOutset.center = euclidean.getSimplifiedLoop(largestCenterOutset.center, radius)
405         return largestCenterOutset
406
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)
416
417 def getLargestInsetLoopFromLoop(loop, radius):
418         'Get the largest inset loop from the loop.'
419         loops = getInsetLoopsFromLoop(loop, radius)
420         return euclidean.getLargestLoop(loops)
421
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.')
431         print(loop)
432         return loop
433
434 def getLoopsFromLoopsDirection( isWiddershins, loops ):
435         'Get the loops going round in a given direction.'
436         directionalLoops = []
437         for loop in loops:
438                 if euclidean.isWiddershins(loop) == isWiddershins:
439                         directionalLoops.append(loop)
440         return directionalLoops
441
442 def getPointsFromLoop(loop, radius, thresholdRatio=0.9):
443         'Get the points from every point on a loop and between points.'
444         if radius == 0.0:
445                 print('Warning, radius is 0 in getPointsFromLoop in intercircle.')
446                 print(loop)
447                 return loop
448         radius = abs(radius)
449         points = []
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 )
455         return points
456
457 def getPointsFromLoops(loops, radius, thresholdRatio=0.9):
458         'Get the points from every point on a loop and between points.'
459         points = []
460         for loop in loops:
461                 points += getPointsFromLoop(loop, radius, thresholdRatio)
462         return points
463
464 def getPointsFromPath(path, radius, thresholdRatio=0.9):
465         'Get the points from every point on a path and between points.'
466         if len(path) < 1:
467                 return []
468         if len(path) < 2:
469                 return path
470         radius = abs(radius)
471         points = []
472         addHalfPath(path, points, radius, thresholdRatio)
473         addHalfPath(path[: : -1], points, radius, thresholdRatio)
474         return points
475
476 def getSimplifiedInsetFromClockwiseLoop(loop, radius):
477         'Get loop inset from clockwise loop, out from widdershins loop.'
478         inset = []
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))
484
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:
490                 return None
491         endMinusBegin *= length / endMinusBeginLength
492         return complex(-endMinusBegin.imag, endMinusBegin.real)
493
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:
500                         return loop
501                 lastLoopLength = len( loop )
502         return loop
503
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):
507                 return False
508         return getIsLarge(inset, radius) and len(inset) > 2
509
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 ):
521                         return True
522         return False
523
524 def orbitsAreLarge( loop, temperatureChangeTime ):
525         'Determine if the orbits are large enough.'
526         if len(loop) < 1:
527                 print('Zero length loop which was skipped over, this should never happen.')
528                 return False
529         return temperatureChangeTime > 1.5
530
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
554                                         del loop[pointIndex]
555                                         return
556
557
558 class BoundingLoop:
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.'
562                 if other == None:
563                         return False
564                 return self.minimum == other.minimum and self.maximum == other.maximum and self.loop == other.loop
565
566         def __repr__(self):
567                 'Get the string representation of this bounding loop.'
568                 return '%s, %s, %s' % ( self.minimum, self.maximum, self.loop )
569
570         def getFromLoop( self, loop ):
571                 'Get the bounding loop from a path.'
572                 self.loop = loop
573                 self.maximum = euclidean.getMaximumByComplexPath(loop)
574                 self.minimum = euclidean.getMinimumByComplexPath(loop)
575                 return self
576
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
586
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:
590                         return False
591                 if self.maximum.imag > anotherBoundingLoop.maximum.imag or self.maximum.real > anotherBoundingLoop.maximum.real:
592                         return False
593                 for point in self.loop:
594                         if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 0:
595                                 return False
596                 return not isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
597
598         def isOverlappingAnother( self, anotherBoundingLoop ):
599                 'Determine if this bounding loop is intersecting another bounding loop.'
600                 if self.isRectangleMissingAnother( anotherBoundingLoop ):
601                         return False
602                 for point in self.loop:
603                         if euclidean.getNumberOfIntersectionsToLeft( anotherBoundingLoop.loop, point ) % 2 == 1:
604                                 return True
605                 for point in anotherBoundingLoop.loop:
606                         if euclidean.getNumberOfIntersectionsToLeft( self.loop, point ) % 2 == 1:
607                                 return True
608                 return isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles
609
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 ):
614                                 return True
615                 return False
616
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:
620                         return True
621                 return self.minimum.imag > anotherBoundingLoop.maximum.imag or self.minimum.real > anotherBoundingLoop.maximum.real
622
623
624 class CenterOutset:
625         'A class to hold a center and an outset.'
626         def __init__(self, center, outset):
627                 'Set the center and outset.'
628                 self.center = center
629                 self.outset = outset
630
631         def __repr__(self):
632                 'Get the string representation of this CenterOutset.'
633                 return '%s\n%s' % (self.center, self.outset)
634
635
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
642                 self.index = index
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)
651                         self.demichord = 0.0
652                 else:
653                         self.demichord = rotatedClockwiseQuarter * demichordWidth / rotatedClockwiseQuarterLength
654                 self.positionRelativeToBehind = self.aheadMinusBehind + self.demichord
655
656         def __repr__(self):
657                 'Get the string representation of this CircleIntersection.'
658                 return '%s, %s, %s, %s' % (self.index, self.getAbsolutePosition(), self.circleNodeBehind, self.circleNodeAhead)
659
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)
664
665         def getAbsolutePosition(self):
666                 'Get the absolute position.'
667                 return self.positionRelativeToBehind + self.circleNodeBehind.dividedPoint
668
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)
678                                 if dot > largestDot:
679                                         largestDot = dot
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
693
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:
701                                         return True
702                 return False
703
704
705 class CircleNode:
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
712
713         def __repr__(self):
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))
717
718         def getWithinNodes(self, pixelTable):
719                 'Get the nodes this circle node is within.'
720                 withinNodes = []
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)
725                 return withinNodes