/usr/share/pythoncad/PythonCAD/Generic/maptree.py is in pythoncad 0.1.37.0-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | #
# Copyright (c) 2002, 2003 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
#
#
# A PointMapTree and PointBMapTree extend a basic Tree
#
from PythonCAD.Generic import point
from PythonCAD.Generic import util
from PythonCAD.Generic import tolerance
from PythonCAD.Generic import tree
class PointMapTree(tree.Tree):
"""A Tree class that containing objects that have Point objects.
The PointMapTree is based on the Tree class, so it shares all
the functionality of that class.
There is one extra method in the PointMapTree
mapPoint(): Find objects in the tree that a Point could fall upon.
Any class stored in this tree must provide a mapPoint() method.
The format of that method is as follows:
mapPoint(p[, tol])
p: Either a Point object or a two-float tuple
Optional argument:
tol: The tolerance used for testing the Point's proximity to the object.
A class should also have a __cmp__ method that can handle an instance
of the class being compared to a Point.
"""
def __init__(self, t):
"""Instantiate a PointMapTree.
PointMapTree(t)
This function has one required argument:
t: The type of object stored in the tree.
"""
tree.Tree.__init__(self, t)
def mapPoint(self, p, tol=tolerance.TOL, count=2):
"""See if an object in the PointMapTree exists at a Point.
mapPoint(p [, tol, count])
This method has one required parameter:
p: Either a Point object or a tuple of two-floats
There are two optional arguments:
tol: A float equal or greater than 0 used to decide if the
point is close enough to the objects held in the Tree.
count: An integer indicating the maximum number of objects
to return. By default this value is 2.
The function returns a list of at tuples, each of the form
(obj, pt)
obj: Object that the Point is mapped to
pt: The projected Point on the object
"""
_p = p
if not isinstance(_p, (point.Point, tuple)):
raise TypeError, "Invalid type for searching in PointMapTree: " + `_p`
if isinstance(_p, tuple):
_x, _y = util.tuple_to_two_floats(_p)
_p = point.Point(_x, _y)
_t = tolerance.toltest(tol)
_count = count
if not isinstance(_count, int):
_count = int(count)
if _count < 0:
raise ValueError, "Invalid count: %d" % _count
_objlist = []
for _obj in self:
_pt = _obj.mapPoint(_p, _t)
if _pt is not None:
_objlist.append((_obj, _pt))
if len(_objlist) == _count or cmp(_obj, _p) == 1:
break
return _objlist
class PointBMapTree(PointMapTree):
"""A Tree class that containing objects that have Point objects.
The PointBMapTree is based on the PointMapTree class, so it shares all
the functionality of that class. The PointBMapTree uses a binary
scan search on objects in the tree to find a particular object, where
the PointMapTree uses a linear search. This implies that any
PointBMapTree will only contain at most one object that a Point
object may be mapped on to.
"""
def __init__(self, t):
"""Instantiate a PointBMapTree.
PointBMapTree(t)
This function has one required argument:
t: The type of object stored in the tree.
"""
PointMapTree.__init__(self, t)
def mapPoint(self, p, tol=tolerance.TOL):
"""See if an object in the PointBMapTree exists at a Point.
mapPoint(p [, tol])
This method has one required parameter:
p: Either a Point object or a tuple of two-floats
There is a single optional argument:
tol: A float equal or greater than 0 used to decide if the
point is close enough to the objects held in the Tree.
The function returns a list of at tuples, each of the form
(obj, pt)
obj: Object that the Point is mapped to
pt: The projected Point on the object
The list will contain at most two tuples.
"""
_p = p
if not isinstance(_p, (point.Point, tuple)):
raise TypeError, "Invalid type for searching in PointMapTree: " + `_p`
if isinstance(_p, tuple):
_x, _y = util.tuple_to_two_floats(_p)
_p = point.Point(_x, _y)
_t = tolerance.toltest(tol)
_objlist = []
_scanlist = []
_lo = 0
_hi = len(self)
while _lo < _hi:
_mid = (_hi+_lo)//2
if _mid in _scanlist:
break
_scanlist.append(_mid)
_obj = self[_mid]
_res = cmp(_obj, _p)
if _res == -1:
_lo = _mid + 1
elif _res == 1:
_hi = _mid
else:
_pt = _obj.mapPoint(_p, _t)
if _pt is not None:
_objlist.append((_obj, _pt))
break
return _objlist
|