#
# Copyright (c) 2003, 2004 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 intersections

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 _segment_bounds(segment):
    _p1, _p2 = segment.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

def _circle_bounds(circle):
    _x, _y = circle.getCenter().getCoords()
    _r = circle.getRadius()
    return ((_x - _r), (_y - _r), (_x + _r), (_y + _r))

def _no_overlap(r1, r2):
    return ((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:

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: " + str(seg)
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + str(pt)
    _p1, _p2 = seg.getEndpoints()
    _style = seg.getStyle()
    _linetype = seg.getLinetype()
    _color = seg.getColor()
    _thickness = seg.getThickness()
    _s1 = Segment(_p1, pt, _style, _linetype, _color, _thickness)
    _s2 = Segment(pt, _p2, _style, _linetype, _color, _thickness)
    return _s1, _s2

def _split_seg_2pts(seg, pt1, pt2):
    _p1, _p2 = seg.getEndpoints()
    _style = seg.getStyle()
    _linetype = seg.getLinetype()
    _color = seg.getColor()
    _thickness = seg.getThickness()
    _s1 = Segment(_p1, pt1, _style, _linetype, _color, _thickness)
    _s2 = Segment(pt1, pt2, _style, _linetype, _color, _thickness)
    _s3 = Segment(pt2, _p2, _style, _linetype, _color, _thickness)
    return _s1, _s2, _s3

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: " + str(circle)
    if isinstance(circle, Arc):
        raise TypeError, "Arc passed to split_circle()"
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + str(pt)
    _cp = circle.getCenter()
    _rad = circle.getRadius()
    _cx, _cy = _cp.getCoords()
    _px, _py = pt.getCoords()
    _angle = (180.0/math.pi) * 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_circ_2pts(circ, p1, p2):
    _cp = circ.getCenter()
    _r = circ.getRadius()
    _cx, _cy = _cp.getCoords()            
    _px, _py = p1.getCoords()
    _angle1 = (180.0/math.pi) * math.atan2((_py - _cy),(_px - _cx))
    if _angle1 < 0.0:
        _angle1 = _angle1 + 360.0
    _px, _py = p2.getCoords()
    _angle2 = (180.0/math.pi) * math.atan2((_py - _cy),(_px - _cx))
    if _angle2 < 0.0:
        _angle2 = _angle2 + 360.0
    _style = circ.getStyle()
    _color = circ.getColor()
    _linetype = circ.getLinetype()
    _thickness = circ.getThickness()
    _a1 = Arc(_cp, _r, _angle1, _angle2, _style,
                          _linetype, _color, _thickness)
    _a2 = Arc(_cp, _r, _angle2, _angle1, _style,
                          _linetype, _color, _thickness)
    return _a1, _a2

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: " + str(arc)
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + str(pt)
    _cp = arc.getCenter()
    _cx, _cy = _cp.getCoords()
    _px, _py = pt.getCoords()
    _angle = (180.0/math.pi) * 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_arc_2pts(arc, pt1, pt2):
    if not isinstance(arc, Arc):
        raise TypeError, "Invalid Arc: " + str(arc)
    if not isinstance(pt1, Point):
        raise TypeError, "Invalid Point: " + str(pt1)
    if not isinstance(pt2, Point):
        raise TypeError, "Invalid Point: " + str(pt2)
    _cp = arc.getCenter()
    _rad = arc.getRadius()
    _sa = arc.getStartAngle()
    _ea = arc.getEndAngle()
    _cx, _cy = _cp.getCoords()
    _px, _py = pt1.getCoords()
    _angle1 = (180.0/math.pi) * math.atan2((_py - _cy), (_px - _cx))
    if _angle1 < 0.0:
        _angle1 = _angle1 + 360.0
    _px, _py = pt2.getCoords()
    _angle2 = (180.0/math.pi) * math.atan2((_py - _cy), (_px - _cx))
    if _angle2 < 0.0:
        _angle2 = _angle2 + 360.0
    if _sa < _ea:
        _a1 = min(_angle1, _angle2)
        _a2 = max(_angle1, _angle2)
    else:
        _d1 = _angle1 - _sa
        if _d1 < 0.0:
            _d1 = _angle1 + _sa
        _d2 = _angle2 - _sa
        if _d2 < 0.0:
            _d2 = _angle2 + _sa
        if _d1 < _d2:
            _a1 = _angle1
            _a2 = _angle2
        else:
            _a1 = _angle2
            _a2 = _angle1
    _style = arc.getStyle()
    _linetype = arc.getLinetype()
    _color = arc.getColor()
    _thickness = arc.getThickness()
    _arc1 = Arc(_cp, _rad, _sa, _a1,
                            _style, _linetype, _color, _thickness)
    _arc2 = Arc(_cp, _rad, _a1, _a2,
                            _style, _linetype, _color, _thickness)
    _arc3 = Arc(_cp, _rad, _a2, _ea,
                            _style, _linetype, _color, _thickness)    
    return _arc1, _arc2, _arc3

def split_polyline(polyline, pt):
    if not isinstance(polyline, Polyline):
        raise TypeError, "Invalid Polyline: " + str(polyline)
    if not isinstance(pt, Point):
        raise TypeError, "Invalid Point: " + str(pt)
    _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
        
def _poly_poly_split(layer, objdict):
    _polylist = objdict['polylines']
    _objrects = objdict['objrects']
    while len(_polylist):
        _testpoly = _polylist.pop(0)
        if _testpoly not in _objrects:
            _objrects[_testpoly] = _testpoly.getBounds()
        _hit_test = False            
        for _poly in _polylist:
            if _poly not in _objrects:
                _objrects[_poly] = _poly.getBounds()
            if _no_overlap(_objrects[_testpoly], _objrects[_poly]):
                continue
            _maxi = len(_testpoly) - 1
            for _i in range(_maxi):
                _p1 = _testpoly.getPoint(_i)
                _p2 = _testpoly.getPoint(_i + 1)
                _x1, _y1 = _p1.getCoords()
                _x2, _y2 = _p2.getCoords()
                _maxj = len(_poly) - 1
                for _j in range(_maxj):
                    _p3 = _poly.getPoint(_j)
                    _p4 = _poly.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
                        _rn = intersections.rnum(_p1, _p2, _p3, _p4)
                        if abs(_rn) > 1e-10: # NOT colinear
                            _sn = intersections.snum(_p1, _p2, _p3 ,_p4)
                            _r = _rn/_d
                            _s = _sn/_d
                            if ((0.0 < _r < 1.0) and (0.0 < _s < 1.0)):
                                _xi = _x1 + _r * (_x2 - _x1)
                                _yi = _y1 + _r * (_y2 - _y1)
                                _pts = layer.find('point', _xi, _yi)
                                if len(_pts) == 0:
                                    _lp = Point(_xi, _yi)
                                    layer.addObject(_lp)
                                else:
                                    _lp = _most_used(_pts)
                                _hit_test = True
                                _testpoly.addPoint((_i + 1), _lp)
                                _poly.addPoint((_j + 1), _lp)
                                break
                if _hit_test:
                    break
            if _hit_test:
                break
        if _hit_test:
            _polylist.insert(0, _testpoly)
    
def _arc_polyline_split(layer, objdict):
    _arclist = objdict['arcs']
    _polylist = objdict['polylines']
    _objstate = {}
    _newarcs = []
    _oldarcs = []
    _objrects = objdict['objrects']
    for _arc in _arclist:
        _objstate[id(_arc)] = True
        _oldarcs.append(_arc)
    while len(_arclist):
        _testarc = _arclist.pop(0)
        _testid = id(_testarc)
        if _testid in _objstate and not _objstate[_testid]:
            continue
        if _testid not in _objstate:
            _objstate[_testid] = True
        if _testid not in _objrects:
            _objrects[_testid] = _testarc.getBounds()
        _ep1, _ep2 = _testarc.getEndpoints()            
        for _poly in _polylist:
            _polyid = id(_poly)
            if _polyid not in _objrects:
                _objrects[_polyid] = _poly.getBounds()
            if _no_overlap(_objrects[_testid], _objrects[_polyid]):
                continue
            _hit = False
            _ptcount = len(_poly) - 1
            for _i in range(_ptcount):
                _lp1 = _poly.getPoint(_i)
                _lp2 = _poly.getPoint(_i + 1)
                _tempseg = Segment(_lp1, _lp2)
                _ipts = intersections.find_intersections(_testarc, _tempseg)
                _tempseg.finish()
                if len(_ipts):
                    _arc1 = _arc2 = _arc3 = None
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip = Point(_x, _y)
                            layer.addObject(_ip)
                        else:
                            _ip = _most_used(_pts)
                        if _ip != _ep1 and _ip != _ep2:
                            _hit = True
                            _arc1, _arc2 = split_arc(_testarc, _ip)
                        if _ip != _lp1 and _ip != _lp2:
                            _hit = True
                            _poly.addPoint((_i + 1), _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip1 = Point(_x, _y)
                            layer.addObject(_ip1)
                        else:
                            _ip1 = _most_used(_pts)
                        _x, _y = _ipts[1]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip2 = Point(_x, _y)
                            layer.addObject(_ip2)
                        else:
                            _ip2 = _most_used(_pts)
                        if (_ip1 != _ep1 and
                            _ip1 != _ep2 and
                            _ip2 != _ep1 and
                            _ip2 != _ep2):
                            _hit = True
                            _arc1, _arc2, _arc3 = _split_arc_2pts(_testarc, _ip1, _ip2)
                        elif _ip1 == _ep1 or _ip1 == _ep2:
                            if _ip2 != _ep1 and _ip2 != _ep2:
                                _hit = True
                                _arc1, _arc2 = split_arc(_testarc, _ip2)
                        elif _ip2 == _ep1 or _ip2 == _ep2:
                            if _ip1 != _ep1 and _ip1 != _ep2:
                                _hit = True
                                _arc1, _arc2 = split_arc(_testarc, _ip1)
                        _d1 = _ip1 - _lp1
                        _d2 = _lp2 - _lp1
                        if _d1 < _d2:
                            _p1 = _ip1
                            _p2 = _ip2
                        else:
                            _p1 = _ip2
                            _p2 = _ip1
                        if (_p1 != _lp1 and _p1 != _lp2):
                            _hit = True
                            _poly.addPoint((_i + 1), _p1)
                            _i = _i + 1
                        if (_p2 != _lp1 and _p2 != _lp2):
                            _hit = True
                            _poly.addPoint((_i + 1), _p2)
                    else:
                        raise ValueError, "Unexpected arc/polyline count: %d" % _count
                    #
                    # if _arc1 is not None then _testarc was split
                    #
                    if _arc1 is not None:
                        _objstate[_testid] = False
                        _newarcs.append(_arc1)
                        _objstate[id(_arc1)] = True
                        _arclist.append(_arc1)
                    if _arc2 is not None:
                        _newarcs.append(_arc2)
                        _objstate[id(_arc2)] = True
                        _arclist.append(_arc2)
                    if _arc3 is not None:
                        _newarcs.append(_arc3)
                        _objstate[id(_arc3)] = True
                        _arclist.append(_arc3)
                    if _hit:
                        break
            if _hit:
                break
    _layerarclist = []
    for _arc in _newarcs:
        if _objstate[id(_arc)]:
            layer.addObject(_arc)
            _layerarclist.append(_arc)
        else:
            _arc.finish()
    for _arc in _oldarcs:
        if _objstate[id(_arc)]:
            _layerarclist.append(_arc)
    objdict['arcs'] = _layerarclist
    for _arc in _oldarcs:
        if not _objstate[id(_arc)]:
            layer.delObject(_arc)

def _arc_arc_split(layer, objdict):
    _arclist = objdict['arcs']
    _arcstate = {}
    _newarcs = []
    _oldarcs = []
    _objrects = objdict['objrects']
    for _arc in _arclist:
        _arcstate[id(_arc)] = True
        _oldarcs.append(_arc)
    while len(_arclist):
        _testarc = _arclist.pop(0)
        _x, _y = _testarc.getCenter().getCoords()
        _testid = id(_testarc)
        if _testid in _arcstate and not _arcstate[_testid]:
            continue
        if _testid not in _arcstate:
            _arcstate[_testid] = True
        if _testid not in _objrects:
            _objrects[_testid] = _testarc.getBounds()
        _ep1, _ep2 = _testarc.getEndpoints()
        for _arc in _arclist:
            _x, _y = _arc.getCenter().getCoords()
            _arcid = id(_arc)
            if _arcid in _arcstate and not _arcstate[_arcid]:
                continue
            if _arcid not in _arcstate:
                _arcstate[_arcid] = True
            if _arcid not in _objrects:
                _objrects[_arcid] = _arc.getBounds()
            if _no_overlap(_objrects[_testid], _objrects[_arcid]):
                continue
            _ep3, _ep4 = _arc.getEndpoints()
            _ipts = intersections.find_intersections(_testarc, _arc)
            if len(_ipts):
                _a1 = _a2 = _a3 = _a4 = _a5 = _a6 = None
                _count = len(_ipts)
                if _count == 1:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    if _ip != _ep1 and _ip != _ep2:
                        _a1, _a2 = split_arc(_testarc, _ip)
                    if _ip != _ep3 and _ip != _ep4:
                        _a4, _a5 = split_arc(_arc, _ip)
                elif _count == 2:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip1 = Point(_x, _y)
                        layer.addObject(_ip1)
                    else:
                        _ip1 = _most_used(_pts)
                    _x, _y = _ipts[1]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip2 = Point(_x, _y)
                        layer.addObject(_ip2)
                    else:
                        _ip2 = _most_used(_pts)
                    if (_ip1 != _ep1 and
                        _ip1 != _ep2 and
                        _ip2 != _ep1 and
                        _ip2 != _ep2):
                        _a1, _a2, _a3 = _split_arc_2pts(_testarc, _ip1, _ip2)
                    elif _ip1 == _ep1 or _ip1 == _ep2:
                        if _ip2 != _ep1 and _ip2 != _ep2:
                            _a1, _a2 = split_arc(_testarc, _ip2)
                    elif _ip2 == _ep1 or _ip2 == _ep2:
                        if _ip1 != _ep1 and _ip1 != _ep2:
                            _a1, _a2 = split_arc(_testarc, _ip1)
                    if (_ip1 != _ep3 and
                        _ip1 != _ep4 and
                        _ip2 != _ep3 and
                        _ip2 != _ep4):
                        _a4, _a5, _a6 = _split_arc_2pts(_arc, _ip1, _ip2)
                    elif _ip1 == _ep3 or _ip1 == _ep4:
                        if _ip2 != _ep3 and _ip2 != _ep4:
                            _a4, _a5 = split_arc(_arc, _ip2)
                    elif _ip2 == _ep3 or _ip2 == _ep4:
                        if _ip1 != _ep3 and _ip1 != _ep4:
                            _a4, _a5 = split_arc(_arc, _ip1)
                else:
                    raise ValueError, "Unexpected arc/arc int count: %d" % _count
                #
                # if _a1 is not None then _testarc was split
                #
                if _a1 is not None:
                    _arcstate[_testid] = False
                    _arclist.append(_a1)
                    _newarcs.append(_a1)
                    _arcstate[id(_a1)] = True
                if _a2 is not None:
                    _arclist.append(_a2)
                    _newarcs.append(_a2)
                    _arcstate[id(_a2)] = True
                if _a3 is not None:
                    _arclist.append(_a3)
                    _newarcs.append(_a3)
                    _arcstate[id(_a3)] = True
                #
                # if _a4 is not None then _arc was split
                #
                if _a4 is not None:
                    _arcstate[_arcid] = False
                    _arclist.append(_a4)
                    _newarcs.append(_a4)
                    _arcstate[id(_a4)] = True
                if _a5 is not None:
                    _arclist.append(_a5)
                    _newarcs.append(_a5)
                    _arcstate[id(_a5)] = True
                if _a6 is not None:
                    _arclist.append(_a6)
                    _newarcs.append(_a6)
                    _arcstate[id(_a6)] = True
                if _a1 is not None or _a4 is not None:
                    break
    _layerarclist = []
    for _arc in _newarcs:
        if _arcstate[id(_arc)]:
            layer.addObject(_arc)
            _layerarclist.append(_arc)
        else:
            _arc.finish()
    for _arc in _oldarcs:
        if _arcstate[id(_arc)]:
            _layerarclist.append(_arc)
    objdict['arcs'] = _layerarclist
    # print "Old arcs ..."
    # for _arc in _oldarcs:
        # _cp = _arc.getCenter()
        # print "Center: " + str(_cp)
        # print "Radius: %g" % _arc.getRadius()
        # print "SA: %g" % _arc.getStartAngle()
        # print "EA: %g" % _arc.getEndAngle()
        # for _ep in _arc.getEndpoints():
            # print "Endpoint: (%g, %g)" % (_ep[0], _ep[1])
        # print "Arc state is " + str(_arcstate[id(_arc)])
    for _arc in _oldarcs:
        if not _arcstate[id(_arc)]:
            if abs(_arc.getEndAngle() - _arc.getStartAngle()) < 1e-10:
                print "Invalid arc found/created; SA == EA (%g)" % _arc.getEndAngle()
            layer.delObject(_arc)

def _circ_polyline_split(layer, objdict):
    _circlist = objdict['circles']
    _polylist = objdict['polylines']
    _objstate = {}
    _newarcs = []
    _oldcircs = []
    _objrects = objdict['objrects']
    for _circ in _circlist:
        _objstate[id(_circ)] = True
        _oldcircs.append(_circ)
    while len(_circlist):
        _testcirc = _circlist.pop(0)
        _testid = id(_testcirc)
        if _testid in _objstate and not _objstate[_testid]:
            continue
        if _testid not in _objstate:
            _objstate[_testid] = True
        if _testid not in _objrects:
            _objrects[_testid] = _circle_bounds(_testcirc)
        for _poly in _polylist:
            _polyid = id(_poly)
            if _polyid not in _objrects:
                _objrects[_polyid] = _poly.getBounds()
            if _no_overlap(_objrects[_testid], _objrects[_polyid]):
                continue
            _count = len(_poly) - 1
            _hit = False
            for _i in range(_count):
                _lp1 = _poly.getPoint(_i)
                _lp2 = _poly.getPoint(_i + 1)
                _tempseg = Segment(_lp1, _lp2)
                _ipts = intersections.find_intersections(_testcirc, _tempseg)
                _tempseg.finish()
                if len(_ipts):
                    _hit = True
                    _arc1 = _arc2 = None
                    _count = len(_ipts)
                    if _count == 1:
                        _x, _y = _ipts[0]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip = Point(_x, _y)
                            layer.addObject(_ip)
                        else:
                            _ip = _most_used(_pts)
                        _arc1 = split_circle(_testcirc, _ip)
                        if _ip != _lp1 and _ip != _lp2:
                            _poly.addPoint((_i + 1), _ip)
                    elif _count == 2:
                        _x, _y = _ipts[0]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip1 = Point(_x, _y)
                            layer.addObject(_ip1)
                        else:
                            _ip1 = _most_used(_pts)
                        _x, _y = _ipts[1]
                        _pts = layer.find('point', _x, _y)
                        if len(_pts) == 0:
                            _ip2 = Point(_x, _y)
                            layer.addObject(_ip2)
                        else:
                            _ip2 = _most_used(_pts)
                        _arc1, _arc2 = _split_circ_2pts(_circ, _ip1, _ip2)
                        _d1 = _ip1 - _lp1
                        _d2 = _ip2 - _lp1
                        if _d1 < _d2:
                            _p1 = _ip1
                            _p2 = _ip2
                        else:
                            _p1 = _ip2
                            _p2 = _ip1
                        if (_p1 != _lp1 and _p1 != _lp2):
                            _poly.addPoint((_i + 1), _p1)
                            _i = _i + 1
                        if (_p2 != _lp1 and _p2 != _lp2):
                            _poly.addPoint((_i + 1), _p2)
                    else:
                        raise ValueError, "Unexpected circle/polyline count: %d" % _count
                    #
                    # if _arc1 is not None the circle was split
                    #
                    if _arc1 is not None:
                        _objstate[_testid] = False
                        _newarcs.append(_arc1)
                        _objstate[id(_arc1)] = True
                    if _arc2 is not None:
                        _newarcs.append(_arc2)
                        _objstate[id(_arc2)] = True
                    break
            if _hit:
                break
    if len(_newarcs):
        _arclist = objdict['arcs']
        for _arc in _newarcs:
            layer.addObject(_arc)
            _arclist.append(_arc)
    _layercirclelist = []
    for _circ in _oldcircs:
        if _objstate[id(_circ)]:
            _layercirclelist.append(_circ)
    objdict['circles'] = _layercirclelist
    for _circ in _oldcircs:
        if not _objstate[id(_circ)]:
            layer.delObject(_circ)

def _circ_arc_split(layer, objdict):
    _circlist = objdict['circles']
    _oldcircs = []
    _arclist = objdict['arcs']
    _objstate = {}
    _oldarcs = []
    _newarcs = []
    _objrects = objdict['objrects']
    for _circ in _circlist:
        _objstate[id(_circ)] = True
        _oldcircs.append(_circ)
    for _arc in _arclist:
        _objstate[id(_arc)] = True
        _oldarcs.append(_arc)
    while len(_circlist):
        _testcirc = _circlist.pop(0)
        _testid = id(_testcirc)
        if _testid in _objstate and not _objstate[_testid]:
            continue
        if _testid not in _objstate:
            _objstate[_testid] = True
        if _testid not in _objrects:
            _objrects[_testid] = _circle_bounds(_testcirc)
        for _arc in _arclist:
            _arcid = id(_arc)
            if _arcid in _objstate and not _objstate[_arcid]:
                continue
            if _arcid not in _objstate:
                _objstate[_arcid] = True
            if _arcid not in _objrects:
                _objrects[_arcid] = _arc.getBounds()
            if _no_overlap(_objrects[_arcid], _objrects[_testid]):
                continue
            _ipts = intersections.find_intersections(_testcirc, _arc)
            if len(_ipts):
                _ep1, _ep2 = _arc.getEndpoints()
                _ca1 = _ca2 = _arc1 = _arc2 = _arc3 = None
                _count = len(_ipts)
                if _count == 1:
                    _x, _y = _ipts[0]
                    # print "circ/arc intersection one point: (%g, %g)" % (_x, _y)
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    _ca1 = split_circle(_testcirc, _ip)
                    if _ip != _ep1 and _ip != _ep2:
                        _arc1, _arc2 = split_arc(_arc, _ip)
                elif _count == 2:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip1 = Point(_x, _y)
                        layer.addObject(_ip1)
                    else:
                        _ip1 = _most_used(_pts)
                    _x, _y = _ipts[1]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip2 = Point(_x, _y)
                        layer.addObject(_ip2)
                    else:
                        _ip2 = _most_used(_pts)
                    _ca1, _ca2 = _split_circ_2pts(_testcirc, _ip1, _ip2)
                    if (_ip1 != _ep1 and
                        _ip1 != _ep2 and
                        _ip2 != _ep1 and
                        _ip2 != _ep2):
                        _arc1, _arc2, _arc3 = _split_arc_2pts(_arc, _ip1, _ip2)
                    elif _ip1 == _ep1 or _ip1 == _ep2:
                        if _ip2 != _ep1 and _ip2 != _ep2:
                            _arc1, _arc2 = split_arc(_arc, _ip2)
                    elif _ip2 == _ep1 or _ip2 == _ep2:
                        if _ip1 !=_ep1 and _ip1 != _ep2:
                            _arc1, _arc2 = split_arc(_arc, _ip1)
                else:
                    raise ValueError, "Unexpected circle/arc count: %d" % _count
                #
                # if _ca1 is not none then the circle was split
                #
                if _ca1 is not None:
                    _objstate[_testid] = False
                    _arclist.append(_ca1)
                    _newarcs.append(_ca1)
                    _objstate[id(_ca1)] = True
                if _ca2 is not None:
                    _arclist.append(_ca2)
                    _newarcs.append(_ca2)
                    _objstate[id(_ca2)] = True
                #
                # if _arc1 is not None then the arc was split
                #
                if _arc1 is not None:
                    _objstate[_arcid] = False
                    _arclist.append(_arc1)
                    _newarcs.append(_arc1)
                    _objstate[id(_arc1)] = True
                if _arc2 is not None:
                    _arclist.append(_arc2)
                    _newarcs.append(_arc2)
                    _objstate[id(_arc2)] = True
                if _arc3 is not None:
                    _arclist.append(_arc3)
                    _newarcs.append(_arc3)
                    _objstate[id(_arc3)] = True
                if _ca1 is not None or _arc1 is not None:
                    break
    _layerarclist = []
    for _arc in _newarcs:
        if _objstate[id(_arc)]:
            layer.addObject(_arc)
            _layerarclist.append(_arc)
        else:
            _arc.finish()
    for _arc in _oldarcs:
        if _objstate[id(_arc)]:
            _layerarclist.append(_arc)
    objdict['arcs'] = _layerarclist
    _layercirclelist = []
    for _circ in _oldcircs:
        if _objstate[id(_circ)]:
            _layercirclelist.append(_circ)
    objdict['circles'] = _layercirclelist
    for _arc in _oldarcs:
        if not _objstate[id(_arc)]:
            layer.delObject(_arc)
    for _circ in _oldcircs:
        if not _objstate[id(_circ)]:
            layer.delObject(_circ)

def _circ_circ_split(layer, objdict):
    _circlist = objdict['circles']
    _circstate = {}
    _oldcircs = []
    _newarcs = []
    _objrects = objdict['objrects']
    for _circ in _circlist:
        _circstate[id(_circ)] = True
        _oldcircs.append(_circ)
    while len(_circlist):
        _testcirc = _circlist.pop(0)
        _testid = id(_testcirc)
        if _testid in _circstate and not _circstate[_testid]:
            continue
        if _testid not in _circstate:
            _circstate[_testid] = True
        if _testid not in _objrects:
            _objrects[_testid] = _circle_bounds(_testcirc)
        for _circ in _circlist:
            _circid = id(_circ)
            if _circid in _circstate and not _circstate[_circid]:
                continue
            if _circid not in _circstate:
                _circstate[_circid] = True
            if _circid not in _objrects:
                _objrects[_circid] = _circle_bounds(_circ)
            if _no_overlap(_objrects[_testid], _objrects[_circid]):
                continue
            _ipts = intersections.find_intersections(_testcirc, _circ)
            if len(_ipts):
                _count = len(_ipts)
                if _count == 1:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    _circstate[_testid] = False
                    _arc = split_circle(_testcirc, _ip)
                    _newarcs.append(_arc)
                    _circstate[_circid] = False
                    _arc = split_circle(_circ, _ip)
                    _newarcs.append(_arc)
                elif _count == 2:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip1 = Point(_x, _y)
                        layer.addObject(_ip1)
                    else:
                        _ip1 = _most_used(_pts)
                    _x, _y = _ipts[1]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip2 = Point(_x, _y)
                        layer.addObject(_ip2)
                    else:
                        _ip2 = _most_used(_pts)
                    _arc1, _arc2 = _split_circ_2pts(_testcirc, _ip1, _ip2)
                    _circstate[_testid] = False
                    _newarcs.append(_arc1)
                    _newarcs.append(_arc2)
                    _circstate[_circid] = False
                    _arc1, _arc2 = _split_circ_2pts(_circ, _ip1, _ip2)
                    _newarcs.append(_arc1)
                    _newarcs.append(_arc2)
                else:
                    raise ValueError, "Unexpected circle/circle count: %d" % _count
                break
    if len(_newarcs):
        _arclist = objdict['arcs']
        for _arc in _newarcs:
            layer.addObject(_arc)
            _arclist.append(_arc)
    _layercirclelist = []
    for _circ in _oldcircs:
        if _circstate[id(_circ)]:
            _layercirclelist.append(_circ)            
    objdict['circles'] = _layercirclelist
    for _circ in _oldcircs:
        if not _circstate[id(_circ)]:
            layer.delObject(_circ)

def _seg_polyline_split(layer, objdict):
    _seglist = objdict['segments']
    _polylist = objdict['polylines']
    _segstate = {}
    _newsegs = []
    _oldsegs = []
    _objrects = objdict['objrects']
    for _seg in _seglist:
        _segstate[id(_seg)] = True
        _oldsegs.append(_seg)
    while len(_seglist):
        _testseg = _seglist.pop(0)
        _testid = id(_testseg)
        if _testid in _segstate and not _segstate[_testid]:
            continue
        if _testid not in _segstate:
            _segstate[_testid] = True
        _p1, _p2 = _testseg.getEndpoints()
        if _testid not in _objrects:
            _objrects[_testid] = _segment_bounds(_testseg)
        for _poly in _polylist:
            _polyid = id(_poly)
            if _polyid not in _objrects:
                _objrects[_polyid] = _poly.getBounds()
            if _no_overlap(_objrects[_testid], _objrects[_polyid]):
                continue
            _count = len(_poly) - 1
            _hit = False
            for _i in range(_count):
                _lp1 = _poly.getPoint(_i)
                _lp2 = _poly.getPoint(_i + 1)
                if _p1 == _lp1 or _p1 == _lp2 or _p2 == _lp1 or _p2 == _lp2:
                    continue
                _tempseg = Segment(_lp1, _lp2)
                _ipts = intersections.find_intersections(_testseg, _tempseg)
                _tempseg.finish()
                if len(_ipts):
                    assert len(_ipts) == 1, "Invalid length: %d" % len(_ipts)
                    _hit = True
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    _s1, _s2 = split_segment(_testseg, _ip)
                    _segstate[_testid] = False
                    _newsegs.append(_s1)
                    _segstate[id(_s1)] = True
                    _newsegs.append(_s2)
                    _segstate[id(_s2)] = True
                    _seglist.append(_s1)
                    _seglist.append(_s2)
                    _poly.addPoint((_i + 1), _ip)
                    break
            if _hit:
                break
    _layerseglist = []
    for _seg in _newsegs:
        if _segstate[id(_seg)]:
            layer.addObject(_seg)
            _layerseglist.append(_seg)
        else:
            _seg.finish()
    for _seg in _oldsegs:
        if _segstate[id(_seg)]:
            _layerseglist.append(_seg)
    objdict['segments'] = _layerseglist
    for _seg in _oldsegs:
        if not _segstate[id(_seg)]:
            layer.delObject(_seg)

def _seg_arc_split(layer, objdict):
    _seglist = objdict['segments']
    _arclist = objdict['arcs']
    _objstate = {}
    _newsegs = []
    _oldsegs = []
    _newarcs = []
    _oldarcs = []
    _objrects = objdict['objrects']
    for _seg in _seglist:
        _objstate[id(_seg)] = True
        _oldsegs.append(_seg)
    for _arc in _arclist:
        _objstate[id(_arc)] = True
        _oldarcs.append(_arc)
    while len(_seglist):
        _testseg = _seglist.pop(0)
        _testid = id(_testseg)
        if _testid in _objstate and not _objstate[_testid]:
            continue
        if _testid not in _objstate:
            _objstate[_testid] = True
        _p1, _p2 = _testseg.getEndpoints()
        if _testid not in _objrects:
            _objrects[_testid] = _segment_bounds(_testseg)
        for _arc in _arclist:
            _arcid = id(_arc)
            if _arcid in _objstate and not _objstate[_arcid]:
                continue
            if _arcid not in _objstate:
                _objstate[_arcid] = True
            if _arcid not in _objrects:
                _objrects[_arcid] = _arc.getBounds()
            if _no_overlap(_objrects[_arcid], _objrects[_testid]):
                continue
            _ipts = intersections.find_intersections(_testseg, _arc)
            if len(_ipts):
                _s1 = _s2 = _s3 = _arc1 = _arc2 = _arc3 = None
                _p1, _p2 = _testseg.getEndpoints()
                _ep1, _ep2 = _arc.getEndpoints()
                _count = len(_ipts)
                if _count == 1:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    if _ip != _ep1 and _ip != _ep2:
                        _arc1, _arc2 = split_arc(_arc, _ip)
                    if _ip != _p1 and _ip != _p2:
                        _s1, _s2 = split_segment(_testseg, _ip)
                elif _count == 2:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip1 = Point(_x, _y)
                        layer.addObject(_ip1)
                    else:
                        _ip1 = _most_used(_pts)
                    _x, _y = _ipts[1]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip2 = Point(_x, _y)
                        layer.addObject(_ip2)
                    else:
                        _ip2 = _most_used(_pts)
                    if (_ip1 != _ep1 and
                        _ip1 != _ep2 and
                        _ip2 != _ep1 and
                        _ip2 != _ep2):
                        _arc1, _arc2, _arc3 = _split_arc_2pts(_arc, _ip1, _ip2)
                    elif _ip1 == _ep1 or _ip1 == _ep2:
                        if _ip2 != _ep1 and _ip2 != _ep2:
                            _arc1, _arc2 = split_arc(_arc, _ip2)
                    elif _ip2 == _ep1 or _ip2 == _ep2:
                        if _ip1 !=_ep1 and _ip1 != _ep2:
                            _arc1, _arc2 = split_arc(_arc, _ip1)
                    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 = _split_seg_2pts(_testseg, _m1, _m2)
                    elif _ip1 == _p1 or _ip1 == _p2:
                        if _ip2 != _p1 and _ip2 != _p2:
                            _s1, _s2 = split_segment(_testseg, _ip2)
                    elif _ip2 == _p1 or _ip2 == _p2:
                        if _ip1 != _p1 and _ip1 != _p2:
                            _s1, _s2 = split_segment(_testseg, _ip1)
                else:
                    raise ValueError, "Unexpected seg/arc count: %d" % _count
                #
                # if _s1 is not None then the segment was split
                #
                if _s1 is not None:
                    _objstate[_testid] = False
                    _newsegs.append(_s1)
                    _objstate[id(_s1)] = True
                    _seglist.append(_s1)
                if _s2 is not None:
                    _newsegs.append(_s2)
                    _objstate[id(_s2)] = True
                    _seglist.append(_s2)
                if _s3 is not None:
                    _newsegs.append(_s3)
                    _objstate[id(_s3)] = True
                    _seglist.append(_s3)
                #
                # if _arc1 is not None then the arc was split
                #
                if _arc1 is not None:
                    _objstate[_arcid] = False
                    _newarcs.append(_arc1)
                    _objstate[id(_arc1)] = True
                    _arclist.append(_arc1)
                if _arc2 is not None:
                    _newarcs.append(_arc2)
                    _objstate[id(_arc2)] = True
                    _arclist.append(_arc2)
                if _arc3 is not None:
                    _newarcs.append(_arc3)
                    _objstate[id(_arc3)] = True
                    _arclist.append(_arc3)
                break
    _layerarclist = []
    for _arc in _newarcs:
        if _objstate[id(_arc)]:
            layer.addObject(_arc)
            _layerarclist.append(_arc)
        else:
            _arc.finish()
    for _arc in _oldarcs:
        if _objstate[id(_arc)]:
            _layerarclist.append(_arc)
    objdict['arcs'] = _layerarclist
    _layerseglist = []
    for _seg in _newsegs:
        if _objstate[id(_seg)]:
            layer.addObject(_seg)
            _layerseglist.append(_seg)
        else:
            _seg.finish()
    for _seg in _oldsegs:
        if _objstate[id(_seg)]:
            _layerseglist.append(_seg)
    objdict['segments'] = _layerseglist
    for _arc in _oldarcs:
        if not _objstate[id(_arc)]:
            layer.delObject(_arc)
    for _seg in _oldsegs:
        if not _objstate[id(_seg)]:
            layer.delObject(_seg)

def _seg_circle_split(layer, objdict):
    _seglist = objdict['segments']
    _circlist = objdict['circles']
    _objstate = {}
    _newsegs = []
    _oldsegs = []
    _oldcircs = []
    _newarcs = []    
    _objrects = objdict['objrects']
    for _seg in _seglist:
        _objstate[id(_seg)] = True
        _oldsegs.append(_seg)
    for _circ in _circlist:
        _objstate[id(_circ)] = True
        _oldcircs.append(_circ)
    while len(_seglist):
        _testseg = _seglist.pop(0)
        _testid = id(_testseg)
        if _testid in _objstate and not _objstate[_testid]:
            continue
        if _testid not in _objstate:
            _objstate[_testid] = True
        _p1, _p2 = _testseg.getEndpoints()
        if _testid not in _objrects:
            _objrects[_testid] = _segment_bounds(_testseg)
        for _circ in _circlist:
            _circid = id(_circ)
            if _circid in _objstate and not _objstate[_circid]:
                continue
            if _circid not in _objrects:
                _objrects[_circid] = _circle_bounds(_circ)
            if _no_overlap(_objrects[_circid], _objrects[_testid]):
                continue
            _ipts = intersections.find_intersections(_testseg, _circ)
            if len(_ipts):
                _s1 = _s2 = _s3 = _arc1 = _arc2 = None
                _p1, _p2 = _testseg.getEndpoints()
                _count = len(_ipts)
                if _count == 1:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip = Point(_x, _y)
                        layer.addObject(_ip)
                    else:
                        _ip = _most_used(_pts)
                    _arc1 = split_circle(_circ, _ip)
                    if _ip != _p1 and _ip != _p2:
                        _s1, _s2 = split_segment(_testseg, _ip)
                elif _count == 2:
                    _x, _y = _ipts[0]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip1 = Point(_x, _y)
                        layer.addObject(_ip1)
                    else:
                        _ip1 = _most_used(_pts)
                    _x, _y = _ipts[1]
                    _pts = layer.find('point', _x, _y)
                    if len(_pts) == 0:
                        _ip2 = Point(_x, _y)
                        layer.addObject(_ip2)
                    else:
                        _ip2 = _most_used(_pts)
                    _arc1, _arc2 = _split_circ_2pts(_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 = _split_seg_2pts(_testseg, _m1, _m2)
                    elif _ip1 == _p1 or _ip1 == _p2:
                        if _ip2 != _p1 and _ip2 != _p2:
                            _s1, _s2 = split_segment(_testseg, _ip2)
                    elif _ip2 == _p1 or _ip2 == _p2:
                        if _ip1 != _p1 and _ip1 != _p2:
                            _s1, _s2 = split_segment(_testseg, _ip1)
                else:
                    raise ValueError, "Unexpected seg/circle count: %d" % _count
                #
                # if _s1 is not None then the test segment was split
                #
                if _s1 is not None:
                    _objstate[_testid] = False
                    _seglist.append(_s1)
                    _objstate[id(_s1)] = True
                    _newsegs.append(_s1)
                if _s2 is not None:
                    _seglist.append(_s2)
                    _objstate[id(_s2)] = True
                    _newsegs.append(_s2)
                if _s3 is not None:
                    _seglist.append(_s3)
                    _objstate[id(_s3)] = True
                    _newsegs.append(_s3)
                #
                # if _arc1 is not None the the circle was split
                #
                if _arc1 is not None:
                    _objstate[_circid] = False
                    _newarcs.append(_arc1)
                if _arc2 is not None:
                    _newarcs.append(_arc2)
                break
    if len(_newarcs):
        _arclist = objdict['arcs']
        for _arc in _newarcs:
            layer.addObject(_arc)
            _arclist.append(_arc)
    _layercirclelist = []
    for _circ in _oldcircs:
        if _objstate[id(_circ)]:
            _layercirclelist.append(_circ)            
    objdict['circles'] = _layercirclelist
    _layerseglist = []
    for _seg in _newsegs:
        if _objstate[id(_seg)]:
            layer.addObject(_seg)
            _layerseglist.append(_seg)
        else:
            _seg.finish()
    for _seg in _oldsegs:
        if _objstate[id(_seg)]:
            _layerseglist.append(_seg)
    objdict['segments'] = _layerseglist
    for _circ in _oldcircs:
        if not _objstate[id(_circ)]:
            layer.delObject(_circ)
    for _seg in _oldsegs:
        if not _objstate[id(_seg)]:
            layer.delObject(_seg)
 
def _seg_seg_split(layer, objdict):
    _seglist = objdict['segments']
    _segstate = {}
    _newsegs = []
    _oldsegs = []
    _objrects = objdict['objrects']
    for _seg in _seglist:
        _segstate[id(_seg)] = True
        _oldsegs.append(_seg)
    while len(_seglist):
        _testseg = _seglist.pop(0)
        _testid = id(_testseg)
        if _testid in _segstate and not _segstate[_testid]:
            continue
        if _testid not in _segstate:
            _segstate[_testid] = True
        _p1, _p2 = _testseg.getEndpoints()
        if _testid not in _objrects:
            _objrects[_testid] = _segment_bounds(_testseg)
        for _seg in _seglist:
            _segid = id(_seg)
            if (_segid in _segstate and not _segstate[_segid]):
                continue
            if _segid not in _segstate:
                _segstate[_segid] = True
            if _segid not in _objrects:
                _objrects[_segid] = _segment_bounds(_seg)
            if _no_overlap(_objrects[_testid], _objrects[_segid]):
                continue
            _p3, _p4 = _seg.getEndpoints()
            if _p1 == _p3 or _p1 == _p4 or _p2 == _p3 or _p2 == _p4:
                continue
            _ipts = intersections.find_intersections(_testseg, _seg)
            if len(_ipts):
                assert len(_ipts) == 1, "Invalid length: %d" % len(_ipts)
                _x, _y = _ipts[0]
                _pts = layer.find('point', _x, _y)
                if len(_pts) == 0:
                    _ip = Point(_x, _y)
                    layer.addObject(_ip)
                else:
                    _ip = _most_used(_pts)
                if _ip != _p1 and _ip != _p2:
                    _s1, _s2 = split_segment(_testseg, _ip)
                    _newsegs.append(_s1)
                    _segstate[id(_s1)] = True
                    _newsegs.append(_s2)
                    _segstate[id(_s2)] = True
                    _seglist.append(_s1)
                    _seglist.append(_s2)
                    _segstate[_testid] = False
                if _ip != _p3 and _ip != _p4:
                    _s1, _s2 = split_segment(_seg, _ip)
                    _newsegs.append(_s1)
                    _segstate[id(_s1)] = True
                    _newsegs.append(_s2)
                    _segstate[id(_s2)] = True
                    _seglist.append(_s1)
                    _seglist.append(_s2)
                    _segstate[_segid] = False
                break
    _layerseglist = []
    for _seg in _newsegs:
        if _segstate[id(_seg)]:
            layer.addObject(_seg)
            _layerseglist.append(_seg)
        else:
            _seg.finish()
    for _seg in _oldsegs:
        if _segstate[id(_seg)]:
            _layerseglist.append(_seg)            
    objdict['segments'] = _layerseglist
    for _seg in _oldsegs:
        if not _segstate[id(_seg)]:
            layer.delObject(_seg)

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

split_objects(layer, objlist):

layer: The layer containing the objects
objlist: The list of objects to split. This argument must be a list.
    """
    if not isinstance(layer, Layer):
        raise TypeError, "Invalid layer: " + str(layer)
    if not isinstance(objlist, list):
        raise TypeError, "Invalid object list: " + str(objlist)
    _objdict = {}
    _segments = []
    _objdict['segments'] = _segments
    _arcs = []
    _objdict['arcs'] = _arcs
    _circles = []
    _objdict['circles'] = _circles
    _polylines = []
    _objdict['polylines'] = _polylines
    _objrects = {}
    _objdict['objrects'] = _objrects
    for _obj in objlist:
        _lobj = layer.findObject(_obj)
        if _lobj is not _obj:
            raise ValueError, "Object not found in layer: " + str(_obj)
        if isinstance(_obj, Segment):
            _segments.append(_obj)
        elif isinstance(_obj, Arc):
            _arcs.append(_obj)
        elif isinstance(_obj, Circle):
            _circles.append(_obj)
        elif isinstance(_obj, Polyline):
            _polylines.append(_obj)
        else:
            pass
    if len(_objdict['segments']):
        _seg_seg_split(layer, _objdict)
        #
        # splitting circles produces arcs, so let the arc test
        # below handling segment/arc intersections ...
        #
        if len(_objdict['circles']):
            _seg_circle_split(layer, _objdict)
        if len(_objdict['polylines']):
            _seg_polyline_split(layer, _objdict)
    if len(_objdict['circles']):
        _circ_circ_split(layer, _objdict)
        if len(_objdict['arcs']):
            _circ_arc_split(layer, _objdict)
        if len(_objdict['polylines']):
            _circ_polyline_split(layer, _objdict)
    if len(_objdict['arcs']):
        if len(_objdict['segments']):
            _seg_arc_split(layer, _objdict)
        if len(_objdict['polylines']):
            _arc_polyline_split(layer, _objdict)
        _arc_arc_split(layer, _objdict)
    if len(_objdict['polylines']):
        _poly_poly_split(layer, _objdict)
