# # 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 _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) _lp = layer.find('point', _xi, _yi) if _lp is None: _lp = Point(_xi, _yi) layer.addObject(_lp) _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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) 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] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) 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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) 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] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) 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 for _arc in _oldarcs: if not _arcstate[id(_arc)]: 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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) _arc1 = split_circle(_testcirc, _ip) if _ip != _lp1 and _ip != _lp2: _poly.addPoint((_i + 1), _ip) elif _count == 2: _x, _y = _ipts[0] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) _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) _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) _ca1 = split_circle(_testcirc, _ip) if _ip != _ep1 and _ip != _ep2: _arc1, _arc2 = split_arc(_arc, _ip) elif _count == 2: _x, _y = _ipts[0] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) _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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) _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] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) _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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) _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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) 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] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_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) 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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) _arc1 = split_circle(_circ, _ip) if _ip != _p1 and _ip != _p2: _s1, _s2 = split_segment(_testseg, _ip) elif _count == 2: _x, _y = _ipts[0] _ip1 = layer.find('point', _x, _y) if _ip1 is None: _ip1 = Point(_x, _y) layer.addObject(_ip1) _x, _y = _ipts[1] _ip2 = layer.find('point', _x, _y) if _ip2 is None: _ip2 = Point(_x, _y) layer.addObject(_ip2) _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] _ip = layer.find('point', _x, _y) if _ip is None: _ip = Point(_x, _y) layer.addObject(_ip) 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)