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.
There is an interesting diagram regarding Edge quadtree. Here, the
k is may be infinite.
That's why, as mentioned above you should designate the maximum level of decomposition.
Edge quadtree
diagram
Each node has exactly four children
Now, let's implement it using GhPython based on the explanations above.
First, define the
quadtree class and takes
bounding_box and
min_size as input values.
The
min_size is used 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()
Quadtree has a root node, middle node, and leaf node because its data structure is based on a node.
If cannnot subdivide no more, children will be
None, else other Quadtree objects.
In the
crvs instance variable of the quadtree, the line segments included in each quadtree rectangle are stored.
The
COUNTER class variable that the quadtree has, is used as a flag to subdivide when each region of the quadtree contains a curve.
In the second, you need a function that checks whether
intersects(or contains) between given curves and quadtree region.
It can be defined as below, and a return value of this function is worked as a requirement condition to subdivide.
def _is_intersects(self, crv, bb):
intersects = rg.Intersect.Intersection.CurveCurve(
crv, bb, ConstsCollection.TOLERANCE, ConstsCollection.TOLERANCE
)
return len(intersects) > 0
Finally, if you define a function to create a
quadtrant and a function to
insert it into each quadtree,
all preparations are complete. Those functions can be defined as below, you can see the full code 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()