Edge quadtrees are used to store
lines.
The difference is the type of information stored about the cells.
Curves are approximated by subdivided cells to a very fine resolution, specifically until there is a single line segment per cell.
Near corners/vertices, edge quadtrees will continue dividing until they reach their
maximum level of decomposition.
This can result in extremely unbalanced trees.
The diagram below illustrates an edge quadtree. Here,
k may be infinite.
For this reason, as mentioned above, the maximum level of decomposition must be designated.
Edge quadtree
diagram
Each node has exactly four children
The quadtree is now implemented in GhPython based on the explanations above.
First, the
quadtree class is defined, taking
bounding_box and
min_size as input values.
The
min_size serves as the maximum level of decomposition, as mentioned above.
class Quadtree:
COUNTER = 1
def __init__(self, bounding_box, min_size=2):
self.bounding_box = bounding_box
self.min_size = min_size
self.crvs = []
self.children = None
self.children_geometries = None
self._post_init()
A quadtree has a root node, middle nodes, and leaf nodes, because its data structure is based on nodes.
When no further subdivision is possible, the children are
None; otherwise, they are other Quadtree objects.
The
crvs instance variable of the quadtree stores the line segments contained in each quadtree rectangle.
The
COUNTER class variable of the quadtree is used as a flag for subdivision when a region of the quadtree contains a curve.
Second, a function is required that checks whether a given curve
intersects(or contains) a quadtree region.
It can be defined as below, and its return value serves as the requirement condition for subdivision.
def _is_intersects(self, crv, bb):
intersects = rg.Intersect.Intersection.CurveCurve(
crv, bb, ConstsCollection.TOLERANCE, ConstsCollection.TOLERANCE
)
return len(intersects) > 0
Finally, once a function to create a
quadtrant and a function to
insert it into each quadtree are defined,
all preparations are complete. These functions can be defined as below, and the full code is available at
this link.
def _subdivide(self):
ne_bb = rg.Rectangle3d(self.plane, self.width / 2, self.height / 2)
ne_bb = ne_bb.ToNurbsCurve()
nw_bb = rg.Rectangle3d(self.plane, -self.width / 2, self.height / 2)
nw_bb = nw_bb.ToNurbsCurve()
se_bb = rg.Rectangle3d(self.plane, self.width / 2, -self.height / 2)
se_bb = se_bb.ToNurbsCurve()
sw_bb = rg.Rectangle3d(self.plane, -self.width / 2, -self.height / 2)
sw_bb = sw_bb.ToNurbsCurve()
ne = Quadtree(ne_bb)
nw = Quadtree(nw_bb)
se = Quadtree(se_bb)
sw = Quadtree(sw_bb)
self.children = [ne, nw, se, sw]
self.children_geometries = [ne_bb, nw_bb, se_bb, sw_bb]
for crv in self.crvs:
if self._is_intersects(crv, ne_bb):
ne.insert(crv)
if self._is_intersects(crv, nw_bb):
nw.insert(crv)
if self._is_intersects(crv, se_bb):
se.insert(crv)
if self._is_intersects(crv, sw_bb):
sw.insert(crv)
def insert(self, crv):
"""Append the geometry to quadtree
Args:
crv (Rhino.Geometry.Curve): Target curve to insert
"""
if self.children:
for child in self.children:
if self._is_intersects(crv, self.bounding_box):
child.insert(crv)
else:
self.crvs.append(crv)
if len(self.crvs) >= self.COUNTER and (
self.width > self.min_size or self.height > self.min_size
):
self._subdivide()