```"""
Intercircle is a collection of utilities for intersecting circles, used to get smooth loops around a collection of points and inset & outset loops.

"""

from __future__ import absolute_import
try:
import psyco
psyco.full()
except:
pass
#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.
import __init__

from skeinforge_tools.skeinforge_utilities.vector3 import Vector3
from skeinforge_tools.skeinforge_utilities import euclidean
import math

__author__ = "Enrique Perez (perez_enrique@yahoo.com)"
__date__ = "\$Date: 2008/21/04 \$"

firstCircleIntersection = circleIntersectionPathComplexes[ 0 ]
for circleIntersectionIndex in xrange( len( circleIntersections ) + 1 ):
firstCircleIntersection.steppedOn = True
return
print( 'circleIntersectionAhead.steppedOn == True in intercircle.' )
firstCircleIntersection.steppedOn = True
print( "addCircleIntersectionLoop would have gone into an endless loop, this should never happen." )
print( "circleIntersectionPathComplexes" )
for circleIntersectionComplex in circleIntersectionPathComplexes:
print( circleIntersectionComplex )
print( circleIntersectionComplex.circleNodeBehind )
print( "firstCircleIntersection" )
print( firstCircleIntersection )
print( "circleIntersections" )
for circleIntersectionComplex in circleIntersections:
print( circleIntersectionComplex )

def addOperatingOrbits( boundaryLoops, pointComplex, skein, temperatureChangeTime, z ):
"Add the orbits before the operating layers."
if len( boundaryLoops ) < 1:
return
largestLength = - 999999999.0
largestLoop = None
perimeterOutset = 0.4 * skein.extrusionPerimeterWidth
greaterThanPerimeterOutset = 1.1 * perimeterOutset
for boundaryLoop in boundaryLoops:
centers = getCentersFromLoopDirection( True, boundaryLoop, greaterThanPerimeterOutset )
for center in centers:
outset = getSimplifiedInsetFromClockwiseLoop( center, perimeterOutset )
if euclidean.isLargeSameDirection( outset, center, perimeterOutset ):
loopLength = euclidean.getPolygonLength( outset )
if loopLength > largestLength:
largestLength = loopLength
largestLoop = outset
if largestLoop == None:
return
if pointComplex != None:
largestLoop = euclidean.getLoopStartingNearest( skein.extrusionPerimeterWidth, pointComplex, largestLoop )
addOrbits( largestLoop, skein, temperatureChangeTime, z )

def addOrbits( loop, skein, temperatureChangeTime, z ):
"Add orbits with the extruder off."
if len( loop ) < 1:
print( 'Zero length loop which was skipped over, this should never happen.' )
if temperatureChangeTime < 1.5:
return
timeInOrbit = 0.0
while timeInOrbit < temperatureChangeTime:
for point in loop:
skein.addGcodeFromFeedrateMovementZ( 60.0 * skein.orbitalFeedratePerSecond, point, z )
timeInOrbit += euclidean.getPolygonLength( loop ) / skein.orbitalFeedratePerSecond

"Add point complexes between the endpoints of a segment."
print( 'This should never happen, radius should never be zero or less in addPointsFromSegment in intercircle.' )
thresholdRadius = radius * thresholdRatio # a higher number would be faster but would leave bigger dangling loops.
segmentComplex = pointEndComplex - pointBeginComplex
segmentComplexLength = abs( segmentComplex )
extraCircles = int( math.floor( segmentComplexLength / thresholdDiameter ) )
lengthIncrement = segmentComplexLength / ( float( extraCircles ) + 1.0 )
if segmentComplexLength == 0.0:
print( 'This should never happen, segmentComplexLength = 0.0 in intercircle.' )
print( 'pointBeginComplex' )
print( pointBeginComplex )
print( pointEndComplex )
return
segmentComplex *= lengthIncrement / segmentComplexLength
nextCircleCenterComplex = pointBeginComplex + segmentComplex
for circleIndex in xrange( extraCircles ):
pointComplexes.append( nextCircleCenterComplex )
nextCircleCenterComplex += segmentComplex

def getCentersFromCircleNodes( circleNodesComplex ):
"Get the complex centers of the circle intersection loops from circle nodes."
if len( circleNodesComplex ) < 2:
return []
circleIntersections = getCircleIntersectionsFromCircleNodes( circleNodesComplex )
circleIntersectionLoopComplexes = getCircleIntersectionLoops( circleIntersections )
return getCentersFromIntersectionLoops( circleIntersectionLoopComplexes )

def getCentersFromIntersectionLoop( circleIntersectionLoopComplex ):
"Get the centers from the intersection loop."
loop = []
for circleIntersectionComplex in circleIntersectionLoopComplex:
return loop

def getCentersFromIntersectionLoops( circleIntersectionLoopComplexes ):
"Get the centers from the intersection loops."
centers = []
for circleIntersectionLoopComplex in circleIntersectionLoopComplexes:
centers.append( getCentersFromIntersectionLoop( circleIntersectionLoopComplex ) )
return centers

def getCentersFromLoopDirection( isWiddershins, loop, radius ):
"Get the centers of the circle intersection loops which go around in the given direction."
circleNodes = getCircleNodesFromLoop( loop, radius )
centers = getCentersFromCircleNodes( circleNodes )
return getLoopsFromLoopsDirection( isWiddershins, centers )

def getCircleIntersectionsFromCircleNodes( circleNodesComplex ):
"Get all the circle intersections which exist between all the circle nodes."
if len( circleNodesComplex ) < 1:
return
circleIntersections = []
index = 0
pixelTable = {}
for circleNode in circleNodesComplex:
x = int( round( circleOverWidth.real ) )
y = int( round( circleOverWidth.imag ) )
euclidean.addElementToPixelList( circleNode, pixelTable, x, y )
accumulatedCircleNodeTable = {}
for circleNodeIndex in xrange( len( circleNodesComplex ) ):
circleNodeBehind = circleNodesComplex[ circleNodeIndex ]
circleNodeIndexMinusOne = circleNodeIndex - 1
if circleNodeIndexMinusOne >= 0:
x = int( round( circleOverSlightlyGreaterThanDiameter.real ) )
y = int( round( circleOverSlightlyGreaterThanDiameter.imag ) )
withinNodes = circleNodeBehind.getWithinNodes( accumulatedCircleNodeTable, slightlyGreaterThanDiameter )
circleIntersectionForward = CircleIntersection( circleNodeAhead, index, circleNodeBehind )
if not circleIntersectionForward.isWithinCircles( pixelTable, slightlyGreaterThanRadius ):
circleIntersections.append( circleIntersectionForward )
circleNodeBehind.circleIntersections.append( circleIntersectionForward )
index += 1
circleIntersectionBackward = CircleIntersection( circleNodeBehind, index, circleNodeAhead )
if not circleIntersectionBackward.isWithinCircles( pixelTable, slightlyGreaterThanRadius ):
circleIntersections.append( circleIntersectionBackward )
index += 1
return circleIntersections

def getCircleIntersectionLoops( circleIntersections ):
"Get all the loops going through the circle intersections."
circleIntersectionLoopComplexes = []
for circleIntersectionComplex in circleIntersections:
if not circleIntersectionComplex.steppedOn:
circleIntersectionLoopComplex = [ circleIntersectionComplex ]
circleIntersectionLoopComplexes.append( circleIntersectionLoopComplex )
return circleIntersectionLoopComplexes

"Get the circle nodes from every point on a loop and between points."
pointComplexes = []
for pointComplexIndex in xrange( len( loop ) ):
pointComplex = loop[ pointComplexIndex ]
pointComplexSecond = loop[ ( pointComplexIndex + 1 ) % len( loop ) ]
pointComplexes.append( pointComplex )

"Get the circle nodes from a path."
circleNodesComplex = []
pointComplexes = euclidean.getAwayPoints( pointComplexes, 0.001 * radius )
for pointComplex in pointComplexes:
circleNodesComplex.append( CircleNode( pointComplex, len( circleNodesComplex ), radius ) )
return circleNodesComplex

"Get loop inset from clockwise triple, out from widdershins loop."
originalCenterMinusBehindComplex = euclidean.getNormalized( centerComplex - behindAbsoluteComplex )
reverseRoundZAngle = complex( originalCenterMinusBehindComplex.real, - originalCenterMinusBehindComplex.imag )
behindAbsoluteComplex *= reverseRoundZAngle
centerComplex *= reverseRoundZAngle
behindIntersectionComplex = getIntersectionAtInset( centerComplex, behindAbsoluteComplex, radius )
between = 0.5 * ( aheadIntersectionComplex + behindIntersectionComplex )
return originalCenterMinusBehindComplex * between
return originalCenterMinusBehindComplex * complex( x, behindIntersectionComplex.imag )

"Get loop inset from clockwise loop, out from widdershins loop."
insetLoopComplex = []
for pointComplexIndex in xrange( len( loop ) ):
behindAbsoluteComplex = loop[ ( pointComplexIndex + len( loop ) - 1 ) % len( loop ) ]
centerComplex = loop[ pointComplexIndex ]
aheadAbsoluteComplex = loop[ ( pointComplexIndex + 1 ) % len( loop ) ]
return insetLoopComplex

def getInsetLoops( inset, loops ):
"Get the inset loops."
insetLoops = []
for loop in loops:
insetLoops += getInsetLoopsFromLoop( inset, loop )
return insetLoops

def getInsetLoopsFromLoop( inset, loop ):
"Get the inset loops from a loop."
absoluteInset = abs( inset )
insetLoops = []
slightlyGreaterThanInset = 1.1 * absoluteInset
muchGreaterThanLayerInset = 2.5 * absoluteInset
isInInsetDirection = euclidean.isWiddershins( loop )
if inset < 0.0:
isInInsetDirection = not isInInsetDirection
centers = getCentersFromLoopDirection( not isInInsetDirection, loop, slightlyGreaterThanInset )
for center in centers:
insetLoop = getSimplifiedInsetFromClockwiseLoop( center, absoluteInset )
if euclidean.isLargeSameDirection( insetLoop, center, muchGreaterThanLayerInset ):
if euclidean.isPathInsideLoop( loop, insetLoop ) == isInInsetDirection:
if inset > 0.0:
insetLoop.reverse()
insetLoops.append( insetLoop )
return insetLoops

def getIntersectionAtInset( aheadComplex, behindComplex, inset ):
"Get circle intersection loop at inset from segment."
rotatedClockwiseQuarter *= inset / abs( rotatedClockwiseQuarter )
return aheadComplexMinusBehindComplex + behindComplex + rotatedClockwiseQuarter

def getLoopsFromLoopsDirection( isWiddershins, loops ):
"Get the loops going round in a given direction."
directionalLoopComplexes = []
for loop in loops:
if euclidean.isWiddershins( loop ) == isWiddershins:
directionalLoopComplexes.append( loop )
return directionalLoopComplexes

"Get loop inset from clockwise loop, out from widdershins loop."

def getWithoutIntersections( loop ):
"Get loop without intersections."
lastLoopLength = len( loop )
while lastLoopLength > 3:
removeIntersection( loop )
if len( loop ) == lastLoopLength:
return loop
lastLoopLength = len( loop )
return loop

def isLoopIntersectingLoop( anotherLoop, loop ):
"Determine if the a loop is intersecting another loop."
for pointIndex in xrange( len( loop ) ):
pointFirst = loop[ pointIndex ]
pointSecond = loop[ ( pointIndex + 1 ) % len( loop ) ]
segment = pointFirst - pointSecond
normalizedSegment = euclidean.getNormalized( segment )
segmentYMirror = complex( normalizedSegment.real, - normalizedSegment.imag )
segmentFirstPoint = segmentYMirror * pointFirst
segmentSecondPoint = segmentYMirror * pointSecond
if euclidean.isLoopIntersectingInsideXSegment( anotherLoop, segmentFirstPoint.real, segmentSecondPoint.real, segmentYMirror, segmentFirstPoint.imag ):
return True
return False

def removeIntersection( loop ):
"Get loop without the first intersection."
withoutIntersection = []
for pointIndex in xrange( len( loop ) ):
behindComplex = loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ]
behindEndComplex = loop[ ( pointIndex + len( loop ) - 2 ) % len( loop ) ]
behindMidpointComplex = 0.5 * ( behindComplex + behindEndComplex )
aheadEndComplex = loop[ ( pointIndex + 1 ) % len( loop ) ]
normalizedSegment = behindComplex - behindMidpointComplex
normalizedSegmentLength = abs( normalizedSegment )
if normalizedSegmentLength > 0.0:
normalizedSegment /= normalizedSegmentLength
segmentYMirror = complex( normalizedSegment.real, - normalizedSegment.imag )
behindRotated = segmentYMirror * behindComplex
behindMidpointRotated = segmentYMirror * behindMidpointComplex
y = behindRotated.imag
if isYAboveFirst != isYAboveSecond:
if xIntersection > min( behindMidpointRotated.real, behindRotated.real ) and xIntersection < max( behindMidpointRotated.real, behindRotated.real ):
intersectionPoint = normalizedSegment * complex( xIntersection, y )
loop[ ( pointIndex + len( loop ) - 1 ) % len( loop ) ] = intersectionPoint
del loop[ pointIndex ]
return

class BoundingLoop:
"A class to hold a bounding loop composed of a minimum complex, a maximum complex and an outset loop."
def __cmp__( self, other ):
"Get comparison in order to sort bounding loops in descending order of area."
if self.area < other.area:
return 1
if self.area > other.area:
return - 1
return 0

def __repr__( self ):
"Get the string representation of this bounding loop."
return '%s, %s, %s' % ( self.minimum, self.maximum, self.loop )

def getFromLoop( self, loop ):
"Get the bounding loop from a path."
self.loop = loop
self.maximum = euclidean.getMaximumFromPoints( loop )
self.minimum = euclidean.getMaximumFromPoints( loop )
return self

def getOutsetBoundingLoop( self, outsetDistance ):
"Outset the bounding rectangle and loop by a distance."
outsetBoundingLoop = BoundingLoop()
outsetBoundingLoop.maximum = self.maximum + complex( outsetDistance, outsetDistance )
outsetBoundingLoop.minimum = self.minimum - complex( outsetDistance, outsetDistance )
greaterThanOutsetDistance = 1.1 * outsetDistance
centers = getCentersFromLoopDirection( True, self.loop, greaterThanOutsetDistance )
outsetBoundingLoop.loop = getSimplifiedInsetFromClockwiseLoop( centers[ 0 ], outsetDistance )
return outsetBoundingLoop

def isEntirelyInsideAnother( self, anotherBoundingLoop ):
"Determine if this bounding loop is entirely inside another bounding loop."
if self.minimum.imag < anotherBoundingLoop.minimum.imag or self.minimum.real < anotherBoundingLoop.minimum.real:
return False
if self.maximum.imag > anotherBoundingLoop.maximum.imag or self.maximum.real > anotherBoundingLoop.maximum.real:
return False
for point in self.loop:
if euclidean.getNumberOfIntersectionsToLeft( point, anotherBoundingLoop.loop ) % 2 == 0:
return False
return not isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles

def isOverlappingAnother( self, anotherBoundingLoop ):
"Determine if this bounding loop is intersecting another bounding loop."
if self.isRectangleMissingAnother( anotherBoundingLoop ):
return False
for point in self.loop:
if euclidean.getNumberOfIntersectionsToLeft( point, anotherBoundingLoop.loop ) % 2 == 1:
return True
for point in anotherBoundingLoop.loop:
if euclidean.getNumberOfIntersectionsToLeft( point, self.loop ) % 2 == 1:
return True
return isLoopIntersectingLoop( anotherBoundingLoop.loop, self.loop ) #later check for intersection on only acute angles

def isRectangleMissingAnother( self, anotherBoundingLoop ):
"Determine if the rectangle of this bounding loop is missing the rectangle of another bounding loop."
if self.maximum.imag < anotherBoundingLoop.minimum.imag or self.maximum.real < anotherBoundingLoop.minimum.real:
return True
return self.minimum.imag > anotherBoundingLoop.maximum.imag or self.minimum.real > anotherBoundingLoop.maximum.real

class CircleIntersection:
"An intersection of two complex circles."
def __init__( self, circleNodeAhead, index, circleNodeBehind ):
self.circleNodeBehind = circleNodeBehind
self.index = index
self.steppedOn = False

def __repr__( self ):
"Get the string representation of this CircleIntersection."
return '%s, %s, %s, %s, %s' % ( self.index, self.getAbsolutePosition(), self.circleNodeBehind.index, self.circleNodeAhead.index, self.getCircleIntersectionAhead().index )

self.steppedOn = True
circleIntersectionPath.append( self )

def getAbsolutePosition( self ):
return self.getPositionRelativeToBehind() + self.circleNodeBehind.circle

smallestWiddershinsDot = 999999999.0
for circleIntersection in circleIntersections:
if not circleIntersection.steppedOn:
circleIntersectionRelative = circleIntersection.getPositionRelativeToBehind()
circleIntersectionRelative = euclidean.getNormalized( circleIntersectionRelative )
widdershinsDot = euclidean.getWiddershinsDotGiven( positionRelativeToAhead, circleIntersectionRelative )
if widdershinsDot < smallestWiddershinsDot:
smallestWiddershinsDot = widdershinsDot
print( 'this should never happen, circleIntersectionAhead in intercircle is None' )
for circleIntersection in circleIntersections:

def getPositionRelativeToBehind( self ):
if abs( rotatedClockwiseQuarter ) == 0:
print( self.circleNodeBehind.circle )
return aheadMinusBehind + rotatedClockwiseQuarter * ( halfChordWidth / abs( rotatedClockwiseQuarter ) )

def isWithinCircles( self, pixelTable, width ):
absolutePosition = self.getAbsolutePosition()
absolutePositionOverWidth = absolutePosition / width
x = int( round( absolutePositionOverWidth.real ) )
y = int( round( absolutePositionOverWidth.imag ) )
squareValues = euclidean.getSquareValues( pixelTable, x, y )
for squareValue in squareValues:
if squareValue != self.circleNodeAhead and squareValue != self.circleNodeBehind:
return True
return False

class CircleNode:
"A complex node of complex circle intersections."
def __init__( self, circle, index, radius ):
self.circle = circle
self.circleIntersections = []
self.index = index

def __repr__( self ):
"Get the string representation of this CircleNode."
return '%s, %s' % ( self.index, self.circle )

def getWithinNodes( self, pixelTable, width ):
circleOverWidth = self.circle / width
x = int( round( circleOverWidth.real ) )
y = int( round( circleOverWidth.imag ) )
withinNodes = []
squareValues = euclidean.getSquareValues( pixelTable, x, y )
for squareValue in squareValues:
if abs( self.circle - squareValue.circle ) < self.diameter:
withinNodes.append( squareValue )
return withinNodes

```