#
# Copyright (c) 2003, 2004, 2006 Art Haas
#
# This file is part of PythonCAD.
#
# PythonCAD is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# PythonCAD is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with PythonCAD; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#
# functions for splitting entities in a drawing

import math

from PythonCAD.Generic.layer import Layer
from PythonCAD.Generic.point import Point
from PythonCAD.Generic.segment import Segment
from PythonCAD.Generic.circle import Circle
from PythonCAD.Generic.arc import Arc
from PythonCAD.Generic.polyline import Polyline
from PythonCAD.Generic import util
from PythonCAD.Generic import intersections

_rtd = (180.0/math.pi)

def _most_used(plist):
    _pmax = plist.pop()
    _max = _pmax.countUsers()
    for _pt in plist:
        _count = _pt.countUsers()
        if _count > _max:
            _max = _count
            _pmax = _pt
    return _pmax

def _get_point(l, x, y):
    _pts = l.find('point', x, y)
    if len(_pts) == 0:
        _lp = Point(x, y)
        l.setAutosplit(False)
        l.addObject(_lp)
    else:
        _lp = _most_used(_pts)
    return _lp
    
def split_segment_at(seg, x, y):
    if not isinstance(seg, Segment):
        raise TypeError, "Invalid Segment: " + `type(seg)`
    _x = util.get_float(x)
    _y = util.get_float(y)
    _layer = seg.getParent()
    if _layer is None:
        return None
    _p = seg.getProjection(_x, _y)
    if _p is None:
        return None
    _px, _py = _p
    if abs(_px - _x) > 1e-10 or abs(_py - _y) > 1e-10:
        return None
    _lp = _get_point(_layer, _px, _py)
    _p1, _p2 = seg.getEndpoints()
    if _lp == _p1 or _lp == _p2:
        return None
    _s = seg.getStyle()
    _l = seg.getLinetype()
    _c = seg.getColor()
    _t = seg.getThickness()
    _s1 = Segment(_p1, _lp, _s, _l, _c, _t)
    _s2 = Segment(_lp, _p2, _s, _l, _c, _t)
    return _s1, _s2

def split_circle_at(circ, x, y):
    if not isinstance(circ, Circle):
        raise TypeError, "Invalid Circle: " + `type(circ)`
    _x = util.get_float(x)
    _y = util.get_float(y)
    _layer = circ.getParent()
    if _layer is None:
        return None
    _p = circ.mapCoords(_x, _y)
    if _p is None:
        return None
    _px, _py = _p
    if abs(_px - _x) > 1e-10 or abs(_py - _y) > 1e-10:
        return None
    _lp = _get_point(_layer, _px, _py)
    _s = circ.getStyle()
    _cp = circ.getCenter()
    _angle = _rtd * math.atan2((_lp.y - _cp.y),(_lp.x - _cp.x))
    _l = circ.getLinetype()
    _c = circ.getColor()
    _t = circ.getThickness()
    _arc = Arc(_cp, circ.getRadius(), _angle, _angle, _s, _l, _c, _t)
    return _arc

def split_arc_at(arc, x, y):
    if not isinstance(arc, Arc):
        raise TypeError, "Invalid Arc: " + `type(arc)`
    _x = util.get_float(x)
    _y = util.get_float(y)
    _layer = arc.getParent()
    if _layer is None:
        return None
    _p = arc.mapCoords(_x, _y)
    if _p is None:
        return None
    _px, _py = _p
    if abs(_px - _x) > 1e-10 or abs(_py - _y) > 1e-10:
        return None
    _lp = _get_point(_layer, _px, _py)
    _s = arc.getStyle()
    _cp = arc.getCenter()
    _r = arc.getRadius()
    _sa = arc.getStartAngle()
    _ea = arc.getEndAngle()
    _angle = _rtd * math.atan2((_lp.y - _cp.y),(_lp.x - _cp.x))
    _l = arc.getLinetype()
    _c = arc.getColor()
    _t = arc.getThickness()
    _a1 = Arc(_cp, _r, _sa, _angle, _s, _l, _c, _t)
    _a2 = Arc(_cp, _r, _angle, _ea, _s, _l, _c, _t)
    return _a1, _a2

def split_polyline_at(pl, x, y):
    if not isinstance(pl, Polyline):
        raise TypeError, "Invalid Polyline: " + `type(pl)`
    _x = util.get_float(x)
    _y = util.get_float(y)
    _layer = pl.getParent()
    if _layer is None:
        return False
    _pts = pl.getPoints()
    for _i in range(len(_pts) - 1):
        _p1x, _p1y = _pts[_i].getCoords()
        _p2x, _p2y = _pts[_i + 1].getCoords()
        _p = util.map_coords(_x, _y, _p1x, _p1y, _p2x, _p2y)
        if _p is None:
            continue
        _px, _py = _p
        if ((abs(_px - _p1x) < 1e-10 and abs(_py - _p1y) < 1e-10) or
            (abs(_px - _p2x) < 1e-10 and abs(_py - _p2y) < 1e-10)):
            continue
        _lp = _get_point(_layer, _px, _py)
        pl.addPoint((_i + 1), _lp)
        return True
    return False

def split_segment(seg, pt):
    """Split a segment into two segments at a point.

split_segment(seg, pt)

seg: The segment to split
pt: The point used to split the segment.

There is presently no check to test that the point lies
on the segment.
    """
    if not isinstance(seg, Segment):
        raise TypeError, "Invalid Segment: " + `type(seg)`
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + `type(pt)`
    _sp = seg.getParent()
    _pp = pt.getParent()
    if _sp is not None and _pp is not None and _sp is not _pp:
        raise RuntimeError, "Invalid Point for Segment splitting."
    _p1, _p2 = seg.getEndpoints()
    _s = seg.getStyle()
    _l = seg.getLinetype()
    _c = seg.getColor()
    _t = seg.getThickness()
    _s1 = Segment(_p1, pt, _s, _l, _c, _t)
    _s2 = Segment(pt, _p2, _s, _l, _c, _t)
    return _s1, _s2

def split_circle(circle, pt):
    """Split a circle into a single arc.

split_circle(circle, pt)

circle: The circle to split
pt: The point used to determine the start/end angles of the arc.
    """
    if not isinstance(circle, Circle):
        raise TypeError, "Invalid Circle: " + `type(circle)`
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + `type(pt)`
    _cp = circle.getParent()
    _pp = pt.getParent()
    if _cp is not None and _pp is not None and _cp is not _pp:
        raise RuntimeError, "Invalid Point for Circle splitting."
    _cp = circle.getCenter()
    _rad = circle.getRadius()
    _cx, _cy = _cp.getCoords()
    _px, _py = pt.getCoords()
    _angle = _rtd * math.atan2((_py - _cy), (_px - _cx))
    if _angle < 0.0:
        _angle = _angle + 360.0
    return Arc(_cp, _rad, _angle, _angle,
                           circle.getStyle(), circle.getLinetype(),
                           circle.getColor(), circle.getThickness())

def split_arc(arc, pt):
    """Split an arc into two connected arcs.

split_arc(arc, pt)

arc: The arc to split.
pt: The point used to determine the angle at which to split the arc.
    """
    if not isinstance(arc, Arc):
        raise TypeError, "Invalid Arc: " + `type(arc)`
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + `type(pt)`
    _ap = arc.getParent()
    _pp = pt.getParent()
    if _ap is not None and _pp is not None and _ap is not _pp:
        raise RuntimeError, "Invalid Point for Arc splitting."
    _cp = arc.getCenter()
    _cx, _cy = _cp.getCoords()
    _px, _py = pt.getCoords()
    _angle = _rtd * math.atan2((_py - _cy), (_px - _cx))
    if _angle < 0.0:
        _angle = _angle + 360.0
    if not arc.throughAngle(_angle):
        raise ValueError, "Arc does not exist at angle %g" % _angle
    _rad = arc.getRadius()
    _sa = arc.getStartAngle()
    _ea = arc.getEndAngle()
    _style = arc.getStyle()
    _linetype = arc.getLinetype()
    _color = arc.getColor()
    _thickness = arc.getThickness()
    _arc1 = Arc(_cp, _rad, _sa, _angle,
                            _style, _linetype, _color, _thickness)
    _arc2 = Arc(_cp, _rad, _angle, _ea,
                            _style, _linetype, _color, _thickness)
    return _arc1, _arc2

def split_polyline(polyline, pt):
    if not isinstance(polyline, Polyline):
        raise TypeError, "Invalid Polyline: " + `type(polyline)`
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + `type(pt)`
    _plp = polyline.getParent()
    _pp = pt.getParent()
    if _plp is not None and _pp is not None and _plp is not _pp:
        raise RuntimeError, "Invalid Point for Polyline splitting."
    _px, _py = pt.getCoords()
    _count = len(polyline)
    for _i in range(_count - 1):
        _hit = False
        _p1x, _p1y = polyline.getPoint(_i).getCoords()
        _p2x, _p2y = polyline.getPoint(_i + 1).getCoords()
        if abs(_p2x - _p1x) < 1e-10: # vertical
            if (abs(_p2x - _px) < 1e-10 and
                min(_p1y, _p2y) < _py < max(_p1y, _p2y)):
                _hit = True
        elif abs(_p2y - _p1y) < 1e-10: # horizontal
            if (abs(_p2y - _py) < 1e-10 and
                min(_p1x, _p2x) < _px < max(_p1x, _p2x)):
                _hit = True
        else:
            _slope = (_p2y - _p1y)/(_p2x - _p1x)
            _yint = _p2y - (_slope * _p2x)
            _ytest = (_slope * _px) + _yint
            if abs(_ytest - _py) < 1e-10:
                _hit = True
        if _hit:
            polyline.addPoint((_i + 1), pt)
            break

class SplitManager(object):
    def __init__(self, layer):
        if not isinstance(layer, Layer):
            raise TypeError, "Invalid Layer: " + `type(layer)`
        self.__layer = layer
        self.__segs = []
        self.__circs = []
        self.__arcs = []
        self.__plines = []
        self.__rects = {}

    def segBounds(s):
        if not isinstance(s, Segment):
            raise TypeError, "Invalid Segment: " + `type(s)`
        _p1, _p2 = s.getEndpoints()
        _x, _y = _p1.getCoords()
        _xmin = _xmax = _x
        _ymin = _ymax = _y
        _x, _y = _p2.getCoords()
        if _x < _xmin:
            _xmin = _x
        if _y < _ymin:
            _ymin = _y
        if _x > _xmax:
            _xmax = _x
        if _y > _ymax:
            _ymax = _y
        return _xmin, _ymin, _xmax, _ymax

    segBounds = staticmethod(segBounds)

    def circBounds(c):
        if not isinstance(c, Circle):
            raise TypeError, "Invalid Circle: " + `type(c)`
        _x, _y = c.getCenter().getCoords()
        _r = c.getRadius()
        return ((_x - _r), (_y - _r), (_x + _r), (_y + _r))

    circBounds = staticmethod(circBounds)

    def canIntersect(r1, r2):
        if not isinstance(r1, tuple):
            raise TypeError, "Invalid R1 tuple: " + `type(r1)`
        if len(r1) != 4:
            raise ValueError, "R1 length error: " + str(r1)
        if not isinstance(r2, tuple):
            raise TypeError, "Invalid R2 tuple: " + `type(r2)`
        if len(r2) != 4:
            raise ValueError, "R2 length error: " + str(r2)
        return not ((r1[2] < r2[0]) or # r1 xmax < r2 xmin
                    (r1[0] > r2[2]) or # r1 xmin > r2 xmax
                    (r1[3] < r2[1]) or # r1 ymax < r2 ymin
                    (r1[1] > r2[3])) # r1 ymin > r2 ymax

    canIntersect = staticmethod(canIntersect)

    def splitSegTwoPts(seg, pt1, pt2):
        _p1, _p2 = seg.getEndpoints()
        _s = seg.getStyle()
        _l = seg.getLinetype()
        _c = seg.getColor()
        _t = seg.getThickness()
        _s1 = Segment(_p1, pt1, _s, _l, _c, _t)
        _s2 = Segment(pt1, pt2, _s, _l, _c, _t)
        _s3 = Segment(pt2, _p2, _s, _l, _c, _t)
        return _s1, _s2, _s3

    splitSegTwoPts = staticmethod(splitSegTwoPts)

    def splitCircTwoPts(circ, p1, p2):
        _cp = circ.getCenter()
        _r = circ.getRadius()
        _cx, _cy = _cp.getCoords()
        _px, _py = p1.getCoords()
        _a1 = _rtd * math.atan2((_py - _cy),(_px - _cx))
        if _a1 < 0.0:
            _a1 = _a1 + 360.0
        _px, _py = p2.getCoords()
        _a2 = _rtd * math.atan2((_py - _cy),(_px - _cx))
        if _a2 < 0.0:
            _a2 = _a2 + 360.0
        _s = circ.getStyle()
        _c = circ.getColor()
        _l = circ.getLinetype()
        _t = circ.getThickness()
        _arc1 = Arc(_cp, _r, _a1, _a2, _s, _l, _c, _t)
        _arc2 = Arc(_cp, _r, _a2, _a1, _s, _l, _c, _t)
        return _arc1, _arc2

    splitCircTwoPts = staticmethod(splitCircTwoPts)

    def splitArcTwoPts(arc, p1, p2):
        _cp = arc.getCenter()
        _r = arc.getRadius()
        _sa = arc.getStartAngle()
        _ea = arc.getEndAngle()
        _cx, _cy = _cp.getCoords()
        _px, _py = p1.getCoords()
        _ap1 = _rtd * math.atan2((_py - _cy), (_px - _cx))
        if _ap1 < 0.0:
            _ap1 = _ap1 + 360.0
        _px, _py = p2.getCoords()
        _ap2 = _rtd * math.atan2((_py - _cy), (_px - _cx))
        if _ap2 < 0.0:
            _ap2 = _ap2 + 360.0
        if _sa < _ea:
            _a1 = min(_ap1, _ap2)
            _a2 = max(_ap1, _ap2)
        else:
            _d1 = _ap1 - _sa
            if _d1 < 0.0:
                _d1 = _ap1 + _sa
            _d2 = _ap2 - _sa
            if _d2 < 0.0:
                _d2 = _ap2 + _sa
            if _d1 < _d2:
                _a1 = _ap1
                _a2 = _ap2
            else:
                _a1 = _ap2
                _a2 = _ap1
        _s = arc.getStyle()
        _l = arc.getLinetype()
        _c = arc.getColor()
        _t = arc.getThickness()
        _arc1 = Arc(_cp, _r, _sa, _a1, _s, _l, _c, _t)
        _arc2 = Arc(_cp, _r, _a1, _a2, _s, _l, _c, _t)
        _arc3 = Arc(_cp, _r, _a2, _ea, _s, _l, _c, _t)
        return _arc1, _arc2, _arc3

    splitArcTwoPts = staticmethod(splitArcTwoPts)
    
    def addObject(self, obj):
        if obj.getParent() is not self.__layer:
            raise ValueError, "Invalid object parent: " + `obj`
        _olist = None
        if isinstance(obj, Segment):
            _olist = self.__segs
        elif isinstance(obj, Circle):
            _olist = self.__circs
        elif isinstance(obj, Arc):
            _olist = self.__arcs
        elif isinstance(obj, Polyline):
            _olist = self.__plines
        else:
            raise TypeError, "Unexpected object: " + `type(obj)`
        _seen = False
        for _obj in _olist:
            if _obj is obj:
                _seen = True
                break
        if _seen:
            raise RuntimeError, "Object already stored: " + `obj`
        _olist.append(obj)

    def delObject(self, obj):
        _olist = None
        if isinstance(obj, Segment):
            _olist = self.__segs
        elif isinstance(obj, Circle):
            _olist = self.__circs
        elif isinstance(obj, Arc):
            _olist = self.__arcs
        elif isinstance(obj, Polyline):
            _olist= self.__plines
        else:
            raise TypeError, "Unexpected object: " + `type(obj)`
        for _i in range(len(_olist)):
            if _olist[_i] is obj:
                del _olist[_i]
                break

    def getSegments(self):
        return self.__segs

    def getCircles(self):
        return self.__circs

    def getArcs(self):
        return self.__arcs

    def getPolylines(self):
        return self.__plines

    def splitObjects(self):
        if len(self.__segs):
            self.__splitSegSeg()
            if len(self.__circs):
                self.__splitSegCircle()
            if len(self.__arcs):
                self.__splitSegArc()
            if len(self.__plines):
                self.__splitSegPolyline()
        if len(self.__circs):
            self.__splitCircCirc()
        if len(self.__circs) and len(self.__arcs):
            self.__splitCircArc()
        if len(self.__circs) and len(self.__plines):
            self.__splitCircPolyline()
        if len(self.__arcs):
            self.__splitArcArc()
            if len(self.__plines):
                self.__splitArcPolyline()
        if len(self.__plines):
            self.__splitPolyPoly()

    def __getPoint(self, x, y):
        _layer = self.__layer
        _pts = _layer.find('point', x, y)
        if len(_pts) == 0:
            _ip = Point(x, y)
            _layer.setAutosplit(False)
            _layer.addObject(_ip)
        else:
            _ip = _most_used(_pts)
        return _ip

    def __splitSegSeg(self):
        _layer = self.__layer
        _segs = self.__segs
        _rects = self.__rects
        _slist = []
        _sdict = {}
        while len(_segs):
            _seg = _segs.pop()
            _slist.append(_seg)
            _segid = id(_seg)
            if _segid in _sdict and not _sdict[_segid]:
                continue
            _p1, _p2 = _seg.getEndpoints()
            if (_p1.getParent() is not _layer or
                _p2.getParent() is not _layer):
                raise RuntimeError, "Invalid Segment endpoints: " + `_seg`
            _sdict[_segid] = True
            _rseg = _rects.get(_segid)
            if _rseg is None:
                _rseg = SplitManager.segBounds(_seg)
                _rects[_segid] = _rseg
            for _s in _segs:
                _sid = id(_s)
                if _sid in _sdict and not _sdict[_sid]:
                    continue
                _p3, _p4 = _s.getEndpoints()
                if (_p3.getParent() is not _layer or
                    _p4.getParent() is not _layer):
                    raise RuntimeError, "Invalid Segment endpoints: " + `_s`
                if _p1 == _p3 or _p1 == _p4 or _p2 == _p3 or _p2 == _p4:
                    continue
                _rs = _rects.get(_sid)
                if _rs is None:
                    _rs = SplitManager.segBounds(_s)
                    _rects[_sid] = _rs
                if not SplitManager.canIntersect(_rseg, _rs):
                    continue
                _ipts = intersections.find_intersections(_s, _seg)
                if len(_ipts):
                    _x, _y = _ipts[0]
                    _ip = self.__getPoint(_x, _y)
                    if _ip != _p3 and _ip != _p4:
                        _s1, _s2 = split_segment(_s, _ip)
                        _segs.append(_s1)
                        _segs.append(_s2)
                        _sdict[_sid] = False
                    if _ip != _p1 and _ip != _p2:
                        _s1, _s2 = split_segment(_seg, _ip)
                        _segs.append(_s1)
                        _segs.append(_s2)
                        _sdict[_segid] = False
                        break
        _nseg = []
        _dseg = []
        for _seg in _slist:
            _status = _sdict.get(id(_seg))
            if _status is None:
                raise RuntimeError, "No status for Segment: " + `_seg`
            elif _status:
                _nseg.append(_seg)
            else:
                _dseg.append(_seg)
        for _seg in _dseg:
            del self.__rects[id(_seg)]
            if _seg.getParent() is not None:
                _layer.delObject(_seg)
            else:
                _seg.finish()
        for _seg in _nseg:
            if _seg.getParent() is None:
                _layer.addObject(_seg)
        self.__segs = _nseg

    def __splitSegCircle(self):
        _segs = self.__segs
        _circs = self.__circs
        _layer = self.__layer
        _rects = self.__rects
        _slist = []
        _alist = []
        _odict = {}
        while len(_segs):
            _seg = _segs.pop()
            _slist.append(_seg)
            _sid = id(_seg)
            if _sid in _odict and not _odict[_sid]:
                continue
            _p1, _p2 = _seg.getEndpoints()
            if (_p1.getParent() is not _layer or
                _p2.getParent() is not _layer):
                raise RuntimeError, "Invalid Segment endpoints: " + `_seg`
            _odict[_sid] = True
            _rs = _rects.get(_sid)
            if _rs is None:
                _rs = SplitManager.segBounds(_seg)
                _rects[_sid] = _rs
            for _circ in _circs:
                _cid = id(_circ)
                if _cid in _odict and not _odict[_cid]:
                    continue
                _odict[_cid] = True
                _rc = _rects.get(_cid)
                if _rc is None:
                    _rc = SplitManager.circBounds(_circ)
                    _rects[_cid] = _rc
                if not SplitManager.canIntersect(_rs, _rc):
                    continue
                _ipts = intersections.find_intersections(_seg, _circ)
                if len(_ipts):
                    _s1 = _s2 = _s3 = _a1 = _a2 = None
                    _p1, _p2 = _seg.getEndpoints()
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _ip = self.__getPoint(_x, _y)
                        _a1 = split_circle(_circ, _ip)
                        if _ip != _p1 and _ip != _p2:
                            _s1, _s2 = split_segment(_seg, _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _ip1 = self.__getPoint(_x, _y)
                        _x, _y = _ipts[1]
                        _ip2 = self.__getPoint(_x, _y)
                        _a1, _a2 = SplitManager.splitCircTwoPts(_circ, _ip1, _ip2)
                        if (_ip1 != _p1 and
                            _ip1 != _p2 and
                            _ip2 != _p1 and
                            _ip2 != _p2):
                            if ((_p1 - _ip1) < (_p1 - _ip2)):
                                _m1 = _ip1
                                _m2 = _ip2
                            else:
                                _m1 = _ip2
                                _m2 = _ip1
                            _s1, _s2, _s3 = SplitManager.splitSegTwoPts(_seg, _m1, _m2)
                        elif ((_ip1 == _p1 or _ip1 == _p2) and
                              (_ip2 != _p1 and _ip2 != _p2)):
                            _s1, _s2 = split_segment(_seg, _ip2)
                        elif ((_ip2 == _p1 or _ip2 == _p2) and
                              (_ip1 != _p1 and _ip1 != _p2)):
                            _s1, _s2 = split_segment(_seg, _ip1)
                        else:
                            pass
                    else:
                        raise ValueError, "Unexpected count: %d" % _count
                    #
                    # if _a1 is not None the circle was split
                    #
                    if _a1 is not None:
                        _odict[_cid] = False
                        _alist.append(_a1)
                        if _a2 is not None:
                            _alist.append(_a2)
                    #
                    # if _s1 is not None the segment was split
                    #
                    if _s1 is not None:
                        _odict[_sid] = False
                        _segs.append(_s1)
                        if _s2 is not None:
                            _segs.append(_s2)
                        if _s3 is not None:
                            _segs.append(_s3)
                        break
        #
        # handle circles
        #
        _dcirc = []
        for _obj in _circs:
            _oid = id(_obj)
            _status = _odict.get(_oid)
            if _status is None:
                raise RuntimeError, "No status for Circle: " + `_obj`
            else:
                if not _status:
                    _dcirc.append(_obj)
        for _obj in _dcirc:
            self.delObject(_obj)
            del self.__rects[id(_obj)]
            _layer.delObject(_obj)
        #
        # handle arcs
        #
        for _obj in _alist:
            _layer.addObject(_obj)
            self.addObject(_obj)
        #
        # handle segments
        #
        _nseg = []
        _dseg = []
        for _obj in _slist:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Segment: " + `_obj`
            elif _status:
                _nseg.append(_obj)
            else:
                _dseg.append(_obj)
        for _obj in _dseg:
            del self.__rects[id(_obj)]
            if _obj.getParent() is not None:
                _layer.delObject(_obj)
            else:
                _obj.finish()
        for _obj in _nseg:
            if _obj.getParent() is None:
                _layer.addObject(_obj)
        self.__segs = _nseg

    def __splitSegArc(self):
        _segs = self.__segs
        _arcs = self.__arcs
        _layer = self.__layer
        _rects = self.__rects
        _slist = []
        _odict = {}
        while len(_segs):
            _seg = _segs.pop()
            _slist.append(_seg)
            _sid = id(_seg)
            if _sid in _odict and not _odict[_sid]:
                continue
            _p1, _p2 = _seg.getEndpoints()
            if (_p1.getParent() is not _layer or
                _p2.getParent() is not _layer):
                raise RuntimeError, "Invalid Segment endpoints: " + `_seg`
            _odict[_sid] = True
            _rs = _rects.get(_sid)
            if _rs is None:
                _rs = SplitManager.segBounds(_seg)
                _rects[_sid] = _rs
            for _arc in _arcs:
                _aid = id(_arc)
                if _aid in _odict and not _odict[_aid]:
                    continue
                _odict[_aid] = True
                _ra = _rects.get(_aid)
                if _ra is None:
                    _ra = _arc.getBounds()
                    _rects[_aid] = _ra
                if not SplitManager.canIntersect(_rs, _ra):
                    continue
                _ipts = intersections.find_intersections(_seg, _arc)
                if len(_ipts):
                    _s1 = _s2 = _s3 = _a1 = _a2 = _a3 = None
                    _p1, _p2 = _seg.getEndpoints()
                    _ep1, _ep2 = _arc.getEndpoints()
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _ip = self.__getPoint(_x, _y)
                        if _ip != _ep1 and _ip != _ep2:
                            _a1, _a2 = split_arc(_arc, _ip)
                        if _ip != _p1 and _ip != _p2:
                            _s1, _s2 = split_segment(_seg, _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _ip1 = self.__getPoint(_x, _y)
                        _x, _y = _ipts[1]
                        _ip2 = self.__getPoint(_x, _y)
                        if (_ip1 != _ep1 and
                            _ip1 != _ep2 and
                            _ip2 != _ep1 and
                            _ip2 != _ep2):
                            _a1, _a2, _a3 = SplitManager.splitArcTwoPts(_arc, _ip1, _ip2)
                        elif ((_ip1 == _ep1 or _ip1 == _ep2) and
                              (_ip2 != _ep1 and _ip2 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip2)
                        elif ((_ip2 == _ep1 or _ip2 == _ep2) and
                              (_ip1 != _ep1 and _ip1 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip1)
                        else:
                            pass
                        if (_ip1 != _p1 and
                            _ip1 != _p2 and
                            _ip2 != _p1 and
                            _ip2 != _p2):
                            if ((_p1 - _ip1) < (_p1 - _ip2)):
                                _m1 = _ip1
                                _m2 = _ip2
                            else:
                                _m1 = _ip2
                                _m2 = _ip1
                            _s1, _s2, _s3 = SplitManager.splitSegTwoPts(_seg, _m1, _m2)
                        elif ((_ip1 == _p1 or _ip1 == _p2) and
                              (_ip2 != _p1 and _ip2 != _p2)):
                            _s1, _s2 = split_segment(_seg, _ip2)
                        elif ((_ip2 == _p1 or _ip2 == _p2) and
                              (_ip1 != _p1 and _ip1 != _p2)):
                            _s1, _s2 = split_segment(_seg, _ip1)
                        else:
                            pass
                    else:
                        raise ValueError, "Unexpected count: %d" % _count
                    #
                    # if _a1 is not None the arc was split
                    #
                    if _a1 is not None:
                        _odict[_aid] = False
                        _arcs.append(_a1)
                        if _a2 is not None:
                            _arcs.append(_a2)
                        if _a3 is not None:
                            _arcs.append(_a3)
                    #
                    # if _s1 is not None the segment was split
                    #
                    if _s1 is not None:
                        _odict[_sid] = False
                        _segs.append(_s1)
                        if _s2 is not None:
                            _segs.append(_s2)
                        if _s3 is not None:
                            _segs.append(_s3)
                        break
        #
        # handle arcs
        #
        _narc = []
        _darc = []
        for _obj in _arcs:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Arc: " + `_obj`
            elif _status:
                _narc.append(_obj)
            else:
                _darc.append(_obj)
        for _obj in _darc:
            del self.__rects[id(_obj)]
            if _obj.getParent() is not None:
                _layer.delObject(_obj)
            else:
                _obj.finish()
        for _obj in _narc:
            if _obj.getParent() is None:
                _layer.addObject(_obj)
        self.__arcs = _narc
        #
        # handle segments
        #
        _nseg = []
        _dseg = []
        for _obj in _slist:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Segment: " + `_obj`
            elif _status:
                _nseg.append(_obj)
            else:
                _dseg.append(_obj)
        for _obj in _dseg:
            del self.__rects[id(_obj)]
            if _obj.getParent() is not None:
                _layer.delObject(_obj)
            else:
                _obj.finish()
        for _obj in _nseg:
            if _obj.getParent() is None:
                _layer.addObject(_obj)
        self.__segs = _nseg

    def __splitSegPolyline(self):
        _segs = self.__segs
        _plines = self.__plines
        _layer = self.__layer
        _rects = self.__rects
        _slist = []
        _odict = {}
        while len(_segs):
            _seg = _segs.pop()
            _slist.append(_seg)
            _sid = id(_seg)
            if _sid in _odict and not _odict[_sid]:
                continue
            _p1, _p2 = _seg.getEndpoints()
            if (_p1.getParent() is not _layer or
                _p2.getParent() is not _layer):
                raise RuntimeError, "Invalid Segment endpoints: " + `_seg`
            _odict[_sid] = True
            _rs = _rects.get(_sid)
            if _rs is None:
                _rs = SplitManager.segBounds(_seg)
                _rects[_sid] = _rs
            _ip = None
            for _pl in _plines:
                _pid = id(_pl)
                _rp = _rects.get(_pid)
                if _rp is None:
                    _rp = _pl.getBounds()
                    _rects[_pid] = _rp
                if not SplitManager.canIntersect(_rs, _rp):
                    continue
                _pts = _pl.getPoints()
                _i = 0
                while (_i < (len(_pts) - 1)):
                    _lp1 = _pts[_i]
                    _lp2 = _pts[_i + 1]
                    if (_p1 == _lp1 or
                        _p1 == _lp2 or
                        _p2 == _lp1 or
                        _p2 == _lp2):
                        _i = _i + 1
                        continue
                    _ts = Segment(_lp1, _lp2)
                    _ipts = intersections.find_intersections(_seg, _ts)
                    _ts.finish()
                    if len(_ipts):
                        _count = len(_ipts)
                        if _count == 1:
                            _x, _y = _ipts[0]
                            _ip = self.__getPoint(_x, _y)
                            _pl.addPoint((_i + 1), _ip)
                            _pts = _pl.getPoints()
                            if _ip != _p1 and _ip != _p2:
                                _s1, _s2 = split_segment(_seg, _ip)
                                _odict[_sid] = False
                                _segs.append(_s1)
                                _segs.append(_s2)
                            else:
                                _ip = None
                        else:
                            raise ValueError, "Unexpected count: %d" % _count
                    _i = _i + 1
                    if _ip is not None:
                        break
                if _ip is not None:
                    break
        #
        # handle segments
        #
        _nseg = []
        _dseg = []
        for _obj in _slist:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Segment: " + `_obj`
            elif _status:
                _nseg.append(_obj)
            else:
                _dseg.append(_obj)
        for _obj in _dseg:
            del self.__rects[id(_obj)]
            if _obj.getParent() is not None:
                _layer.delObject(_obj)
            else:
                _obj.finish()
        for _obj in _nseg:
            if _obj.getParent() is None:
                _layer.addObject(_obj)
        self.__segs = _nseg

    def __splitCircCirc(self):
        _layer = self.__layer
        _circs = self.__circs
        _rects = self.__rects
        _olist = []
        _cdict = {}
        while len(_circs):
            _circ = _circs.pop()
            _olist.append(_circ)
            _circid = id(_circ)
            if _circid in _cdict and not _cdict[_circid]:
                continue
            _cdict[_circid] = True
            _rcirc = _rects.get(_circid)
            if _rcirc is None:
                _rcirc = SplitManager.circBounds(_circ)
                _rects[_circid] = _rcirc
            for _c in _circs:
                _cid = id(_c)
                if _cid in _cdict and not _cdict[_cid]:
                    continue
                _rc = _rects.get(_cid)
                if _rc is None:
                    _rc = SplitManager.circBounds(_c)
                    _rects[_cid] = _rc
                if not SplitManager.canIntersect(_rcirc, _rc):
                    continue
                _ipts = intersections.find_intersections(_c, _circ)
                if len(_ipts):
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _ip = self.__getPoint(_x, _y)
                        _arc = split_circle(_circ, _ip)
                        _olist.append(_arc)
                        _cdict[_circid] = False
                        _arc = split_circle(_c, _ip)
                        _olist.append(_arc)
                        _cdict[_cid] = False
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _ip1 = self.__getPoint(_x, _y)
                        _x, _y = _ipts[1]
                        _ip2 = self.__getPoint(_x, _y)
                        _arc1, _arc2 = SplitManager.splitCircTwoPts(_circ, _ip1, _ip2)
                        _cdict[_circid] = False
                        _olist.append(_arc1)
                        _olist.append(_arc2)
                        _arc1, _arc2 = SplitManager.splitCircTwoPts(_c, _ip1, _ip2)
                        _olist.append(_arc1)
                        _olist.append(_arc2)
                        _cdict[_cid] = False
                    else:
                        raise ValueError, "Unexpected count: %d" % _count
                    break
        _alist = []
        _dlist = []
        for _obj in _olist:
            _status = _cdict.get(id(_obj))
            if _status is None:
                _alist.append(_obj)
            elif _status:
                _circs.append(_obj)
            else:
                _dlist.append(_obj)
        for _obj in _dlist:
            self.delObject(_obj)
            del self.__rects[id(_obj)]
            _layer.delObject(_obj)
        for _obj in _alist:
            _layer.addObject(_obj)
            self.addObject(_obj)

    def __splitCircArc(self):
        _layer = self.__layer
        _circs = self.__circs
        _arcs = self.__arcs
        _rects = self.__rects
        _clist = []
        _odict = {}
        while len(_circs):
            _circ = _circs.pop()
            _clist.append(_circ)
            _circid = id(_circ)
            if _circid in _odict and not _odict[_circid]:
                continue
            _odict[_circid] = True
            _rcirc = _rects.get(_circid)
            if _rcirc is None:
                _rcirc = SplitManager.circBounds(_circ)
                _rects[_circid] = _rcirc
            for _arc in _arcs:
                _arcid = id(_arc)
                if _arcid in _odict and not _odict[_arcid]:
                    continue
                _odict[_arcid] = True
                _rarc = _rects.get(_arcid)
                if _rarc is None:
                    _rarc = _arc.getBounds()
                    _rects[_arcid] = _rarc
                if not SplitManager.canIntersect(_rcirc, _rarc):
                    continue
                _ipts = intersections.find_intersections(_circ, _arc)
                if len(_ipts):
                    _ep1, _ep2 = _arc.getEndpoints()
                    _ca1 = _ca2 = _a1 = _a2 = _a3 = None
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _ip = self.__getPoint(_x, _y)
                        _ca1 = split_circle(_circ, _ip)
                        if _ip != _ep1 and _ip != _ep2:
                            _a1, _a2 = split_arc(_arc, _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _ip1 = self.__getPoint(_x, _y)
                        _x, _y = _ipts[1]
                        _ip2 = self.__getPoint(_x, _y)
                        _ca1, _ca2 = SplitManager.splitCircTwoPts(_circ, _ip1, _ip2)
                        if (_ip1 != _ep1 and
                            _ip1 != _ep2 and
                            _ip2 != _ep1 and
                            _ip2 != _ep2):
                            _a1, _a2, _a3 = SplitManager.splitArcTwoPts(_arc, _ip1, _ip2)
                        elif ((_ip1 == _ep1 or _ip1 == _ep2) and
                              (_ip2 != _ep1 and _ip2 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip2)
                        elif ((_ip2 == _ep1 or _ip2 == _ep2) and
                              (_ip1 !=_ep1 and _ip1 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip1)
                        else:
                            pass
                    else:
                        raise ValueError, "Unexpected count: %d" % _count
                    #
                    # if _a1 is not None then the arc was split
                    #
                    if _a1 is not None:
                        _odict[_arcid] = False
                        _arcs.append(_a1)
                        if _a2 is not None:
                            _arcs.append(_a2)
                        if _a3 is not None:
                            _arcs.append(_a3)
                    #
                    # if _ca1 is not none then the circle was split
                    #
                    if _ca1 is not None:
                        _odict[_circid] = False
                        _arcs.append(_ca1)
                        if _ca2 is not None:
                            _arcs.append(_ca2)
                        break
        #
        # handle circles
        #
        _dlist = []
        for _obj in _clist:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Circle: " + `_obj`
            elif _status:
                _circs.append(_obj)
            else:
                _dlist.append(_obj)
        for _obj in _dlist:
            self.delObject(_obj)
            del self.__rects[id(_obj)]
            _layer.delObject(_obj)
        #
        # handle arcs
        #
        _narc = []
        _darc = []
        for _obj in _arcs:
            _status = _odict.get(id(_obj))
            #
            # states:
            # None - Arc untested - created during split of final circle
            # True - Arc survived all split attempts
            # False - Arc was split
            #
            if _status is None or _status:
                _narc.append(_obj)
            else:
                _darc.append(_obj)
        for _obj in _darc:
            del self.__rects[id(_obj)]
            if _obj.getParent() is not None:
                _layer.delObject(_obj)
            else:
                _obj.finish()
        for _obj in _narc:
            if _obj.getParent() is None:
                _layer.addObject(_obj)
        self.__arcs = _narc

    def __splitCircPolyline(self):
        _circs = self.__circs
        _plines = self.__plines
        _layer = self.__layer
        _rects = self.__rects
        _alist = []
        _clist = []
        _odict = {}
        while len(_circs):
            _circ = _circs.pop()
            _clist.append(_circ)
            _circid = id(_circ)
            if _circid in _odict and not _odict[_circid]:
                continue
            _odict[_circid] = True
            _rcirc = _rects.get(_circid)
            if _rcirc is None:
                _rcirc = SplitManager.circBounds(_circ)
                _rects[_circid] = _rcirc
            _hit = False                
            for _pl in _plines:
                _pid = id(_pl)
                _rp = _rects.get(_pid)
                if _rp is None:
                    _rp = _pl.getBounds()
                    _rects[_pid] = _rp
                if not SplitManager.canIntersect(_rcirc, _rp):
                    continue
                _pts = _pl.getPoints()
                for _i in range(len(_pts) - 1):
                    _lp1 = _pts[_i]
                    _lp2 = _pts[_i + 1]
                    _seg = Segment(_lp1, _lp2)
                    _ipts = intersections.find_intersections(_circ, _seg)
                    _seg.finish()
                    if len(_ipts):
                        _a1 = _a2 = None
                        _count = len(_ipts)
                        if _count == 1:
                            _x, _y = _ipts[0]
                            _ip = self.__getPoint(_x, _y)
                            _a1 = split_circle(_circ, _ip)
                            if _ip != _lp1 and _ip != _lp2:
                                _pl.addPoint((_i + 1), _ip)
                        elif _count == 2:
                            _x, _y = _ipts[0]
                            _ip1 = self.__getPoint(_x, _y)
                            _x, _y = _ipts[1]
                            _ip2 = self.__getPoint(_x, _y)
                            _a1, _a2 = SplitManager.splitCircTwoPts(_circ, _ip1, _ip2)
                            if (_ip1 - _lp1) < (_ip2 - _lp1):
                                _p1 = _ip1
                                _p2 = _ip2
                            else:
                                _p1 = _ip2
                                _p2 = _ip1
                            if _p1 != _lp1 and _p1 != _lp2:
                                _pl.addPoint((_i + 1), _p1)
                                _i = _i + 1
                            if _p2 != _lp1 and _p2 != _lp2:
                                _pl.addPoint((_i + 1), _p2)
                        else:
                            raise ValueError, "Unexpected count: %d" % _count
                        #
                        # if _a1 is not None the circle was split
                        #
                        if _a1 is not None:
                            _odict[_circid] = False
                            _alist.append(_a1)
                            if _a2 is not None:
                                _alist.append(_a2)
                            _hit = True
                            break
                if _hit:
                    break
        #
        # handle circles
        #
        _dlist = []
        for _obj in _clist:
            _status = _odict.get(id(_obj))
            if _status is None:
                raise RuntimeError, "No status for Circle: " + `_obj`
            elif _status:
                _circs.append(_obj)
            else:
                _dlist.append(_obj)
        for _obj in _dlist:
            self.delObject(_obj)
            del self.__rects[id(_obj)]
            _layer.delObject(_obj)
        #
        # handle arcs
        #
        for _obj in _alist:
            _layer.addObject(_obj)
            self.addObject(_obj)

    def __splitArcArc(self):
        _arcs = self.__arcs
        _layer = self.__layer
        _rects = self.__rects
        _alist = []
        _adict = {}
        while len(_arcs):
            _arc = _arcs.pop()
            _alist.append(_arc)
            _arcid = id(_arc)
            if _arcid in _adict and not _adict[_arcid]:
                continue
            _adict[_arcid] = True
            _rarc = _rects.get(_arcid)
            if _rarc is None:
                _rarc = _arc.getBounds()
                _rects[_arcid] = _rarc
            _ep1, _ep2 = _arc.getEndpoints()
            for _a in _arcs:
                _aid = id(_a)
                if _aid in _adict and not _adict[_aid]:
                    continue
                _ra = _rects.get(_aid)
                if _ra is None:
                    _ra = _a.getBounds()
                    _rects[_aid] = _ra
                if not SplitManager.canIntersect(_rarc, _ra):
                    continue
                _ep3, _ep4 = _a.getEndpoints()
                _ipts = intersections.find_intersections(_arc, _a)
                if len(_ipts):
                    _a1 = _a2 = _a3 = _a4 = _a5 = _a6 = None
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _ip = self.__getPoint(_x, _y)
                        if _ip != _ep1 and _ip != _ep2:
                            _a1, _a2 = split_arc(_arc, _ip)
                        if _ip != _ep3 and _ip != _ep4:
                            _a4, _a5 = split_arc(_a, _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _ip1 = self.__getPoint(_x, _y)
                        _x, _y = _ipts[1]
                        _ip2 = self.__getPoint(_x, _y)
                        if (_ip1 != _ep1 and
                            _ip1 != _ep2 and
                            _ip2 != _ep1 and
                            _ip2 != _ep2):
                            _a1, _a2, _a3 = SplitManager.splitArcTwoPts(_arc, _ip1, _ip2)
                        elif ((_ip1 == _ep1 or _ip1 == _ep2) and
                              (_ip2 != _ep1 and _ip2 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip2)
                        elif ((_ip2 == _ep1 or _ip2 == _ep2) and
                              (_ip1 != _ep1 and _ip1 != _ep2)):
                            _a1, _a2 = split_arc(_arc, _ip1)
                        else:
                            pass
                        if (_ip1 != _ep3 and
                            _ip1 != _ep4 and
                            _ip2 != _ep3 and
                            _ip2 != _ep4):
                            _a4, _a5, _a6 = SplitManager.splitArcTwoPts(_a, _ip1, _ip2)
                        elif ((_ip1 == _ep3 or _ip1 == _ep4) and
                              (_ip2 != _ep3 and _ip2 != _ep4)):
                            _a4, _a5 = split_arc(_a, _ip2)
                        elif ((_ip2 == _ep3 or _ip2 == _ep4) and
                              (_ip1 != _ep3 and _ip1 != _ep4)):
                            _a4, _a5 = split_arc(_a, _ip1)
                        else:
                            pass
                    else:
                        raise ValueError, "Unexpected count: %d" % _count
                    #
                    # if _a4 is not None then _a was split
                    #
                    if _a4 is not None:
                        _adict[_aid] = False
                        _arcs.append(_a4)
                        if _a5 is not None:
                            _arcs.append(_a5)
                        if _a6 is not None:
                            _arcs.append(_a6)
                    #
                    # if _a1 is not None then _arc was split
                    #
                    if _a1 is not None:
                        _adict[_arcid] = False
                        _arcs.append(_a1)
                        if _a2 is not None:
                            _arcs.append(_a2)
                        if _a3 is not None:
                            _arcs.append(_a3)
                        break
        _narc = []
        _darc = []
        for _arc in _alist:
            _status = _adict.get(id(_arc))
            if _status is None:
                raise RuntimeError, "No status for Arc: " + `_arc`
            elif _status:
                _narc.append(_arc)
            else:
                _darc.append(_arc)
        for _arc in _darc:
            del self.__rects[id(_arc)]
            if _arc.getParent() is not None:
                _layer.delObject(_arc)
            else:
                _arc.finish()
        for _arc in _narc:
            if _arc.getParent() is None:
                _layer.addObject(_arc)
        self.__arcs = _narc

    def __splitArcPolyline(self):
        _arcs = self.__arcs
        _plines = self.__plines
        _layer = self.__layer
        _rects = self.__rects
        _alist = []
        _adict = {}
        while len(_arcs):
            _arc = _arcs.pop()
            _alist.append(_arc)
            _arcid = id(_arc)
            if _arcid in _adict and not _adict[_arcid]:
                continue
            _adict[_arcid] = True
            _rarc = _rects.get(_arcid)
            if _rarc is None:
                _rarc = _arc.getBounds()
                _rects[_arcid] = _rarc
            _ep1, _ep2 = _arc.getEndpoints()
            _hit = False
            for _pl in _plines:
                _pid = id(_pl)
                _rp = _rects.get(_pid)
                if _rp is None:
                    _rp = _pl.getBounds()
                    _rects[_pid] = _rp
                if not SplitManager.canIntersect(_rarc, _rp):
                    continue
                _pts = _pl.getPoints()
                for _i in range(len(_pts) - 1):
                    _lp1 = _pts[_i]
                    _lp2 = _pts[_i + 1]
                    _seg = Segment(_lp1, _lp2)
                    _ipts = intersections.find_intersections(_arc, _seg)
                    _seg.finish()
                    if len(_ipts):
                        _a1 = _a2 = _a3 = None
                        _count = len(_ipts)
                        if _count == 1:
                            _x, _y = _ipts[0]
                            _ip = self.__getPoint(_x, _y)
                            if _ip != _ep1 and _ip != _ep2:
                                _a1, _a2 = split_arc(_arc, _ip)
                            if _ip != _lp1 and _ip != _lp2:
                                _pl.addPoint((_i + 1), _ip)
                        elif _count == 2:
                            _x, _y = _ipts[0]
                            _ip1 = self.__getPoint(_x, _y)
                            _x, _y = _ipts[1]
                            _ip2 = self.__getPoint(_x, _y)
                            if (_ip1 != _ep1 and
                                _ip1 != _ep2 and
                                _ip2 != _ep1 and
                                _ip2 != _ep2):
                                _a1, _a2, _a3 = SplitManager.splitArcTwoPts(_arc, _ip1, _ip2)
                            elif ((_ip1 == _ep1 or _ip1 == _ep2) and
                                  (_ip2 != _ep1 and _ip2 != _ep2)):
                                _a1, _a2 = split_arc(_arc, _ip2)
                            elif ((_ip2 == _ep1 or _ip2 == _ep2) and
                                  (_ip1 != _ep1 and _ip1 != _ep2)):
                                _a1, _a2 = split_arc(_arc, _ip1)
                            else:
                                pass
                            if (_lp1 - _ip1) < (_lp1 -_ip2):
                                _p1 = _ip1
                                _p2 = _ip2
                            else:
                                _p1 = _ip2
                                _p2 = _ip1
                            if _p1 != _lp1 and _p1 != _lp2:
                                _pl.addPoint((_i + 1), _p1)
                                _i = _i + 1
                            if _p2 != _lp1 and _p2 != _lp2:
                                _pl.addPoint((_i + 1), _p2)
                        else:
                            raise ValueError, "Unexpected count: %d" % _count
                        #
                        # if _a1 is not None then _arc was split
                        #
                        if _a1 is not None:
                            _hit = True
                            _adict[_arcid] = False
                            _arcs.append(_a1)
                            if _a2 is not None:
                                _arcs.append(_a2)
                            if _a3 is not None:
                                _arcs.append(_a3)
                    if _hit:
                        break
                if _hit:
                    break
        _narc = []
        _darc = []
        for _arc in _alist:
            _status = _adict.get(id(_arc))
            if _status is None:
                raise RuntimeError, "No status for Arc: " + `_arc`
            elif _status:
                _narc.append(_arc)
            else:
                _darc.append(_arc)
        for _arc in _darc:
            del self.__rects[id(_arc)]
            if _arc.getParent() is not None:
                _layer.delObject(_arc)
            else:
                _arc.finish()
        for _arc in _narc:
            if _arc.getParent() is None:
                _layer.addObject(_arc)
        self.__arcs = _narc

    def __splitPolyPoly(self):
        _plines = self.__plines
        _rects = self.__rects
        _pdict = {}
        _zero = (0.0 - 1e-10)
        _one = (1.0 + 1e-10)
        while len(_plines):
            _pl = _plines.pop()
            _plid = id(_pl)
            if _plid in _pdict and not _pdict[_plid]:
                continue
            _pdict[_plid] = True
            _rpl = _rects.get(_plid)
            if _rpl is None:
                _rpl = _pl.getBounds()
                _rects[_plid] = _rpl
            _maxi = len(_pl) - 1
            _ip = None
            for _p in _plines:
                _pid = id(_p)
                if _pid in _pdict and not _pdict[_pid]:
                    continue
                _rp = _rects.get(_pid)
                if _rp is None:
                    _rp = _p.getBounds()
                    _rects[_pid] = _rp
                if not SplitManager.canIntersect(_rpl, _rp):
                    continue
                for _i in range(_maxi):
                    _p1 = _pl.getPoint(_i)
                    _p2 = _pl.getPoint(_i + 1)
                    _x1, _y1 = _p1.getCoords()
                    _x2, _y2 = _p2.getCoords()
                    _maxj = len(_p) - 1
                    for _j in range(_maxj):
                        _p3 = _p.getPoint(_j)
                        _p4 = _p.getPoint(_j + 1)
                        if (_p1 == _p3 or
                            _p1 == _p4 or
                            _p2 == _p3 or
                            _p2 == _p4):
                            continue
                        _d = intersections.denom(_p1, _p2, _p3, _p4)
                        if abs(_d) > 1e-10: # NOT parallel
                            _r = intersections.rnum(_p1, _p2, _p3, _p4)/_d
                            _s = intersections.snum(_p1, _p2, _p3 ,_p4)/_d
                            if (not (_r < _zero or _r > _one) and
                                not (_s < _zero or _s > _one)):
                                _xi = _x1 + _r * (_x2 - _x1)
                                _yi = _y1 + _r * (_y2 - _y1)
                                _ip = self.__getPoint(_xi, _yi)
                                _pl.addPoint((_i + 1), _ip)
                                _p.addPoint((_j + 1), _ip)
                        if _ip is not None:
                            break
                    if _ip is not None:
                        break
                if _ip is not None:
                    break
            if _ip is not None:
                _plines.append(_pl)

def split_objects(objlist):
    """Split a list of objects at their intersection points.

split_objects(objlist):

objlist: A list or tuple of objects to split
    """
    if not isinstance(objlist, (list, tuple)):
        raise TypeError, "Invalid object list/tuple: " + `type(objlist)`
    _ldict = {}
    for _obj in objlist:
        _layer = _obj.getParent()
        if _layer is not None:
            _mgr = _ldict.setdefault(id(_layer), SplitManager(_layer))
            _mgr.addObject(_obj)
    for _mgr in _ldict.values():
        _mgr.splitObjects()