[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17452992#comment-17452992
]
Matt Juntunen commented on GEOMETRY-142:
----------------------------------------
Thanks, [~kinow]!
{quote} From what I understood, you created an octree that uses the existing
Vector3D and Precision classes, to add Vector3DNodes into the octtree, and when
searching simply compare the value desired with the value stored in the octree
allowing the Precision threshold.
{quote}
Correct. The difference between my implementation and what I consider a
"standard" octree implementation is that mine splits each leaf on the centroid
of the points collected instead of at the center of the node. This ensures that
the points are distributed into different child nodes. The octrees I've used
before all start with an initial bounding box and then split into 8
equally-sized children when a leaf becomes full. This is fine when we have
initial knowledge of the points and the bounding box but not when we have
absolutely no idea what will be added next, as is the case here.
bq. ... interested to see the k-d tree ...
Me, too :-) I've been struggling to come up with a way to balance the tree as
it is being created without much luck. I haven't been able to find much on
self-balancing multi-dimensional tree structures in the literature, but I did
find [this|https://github.com/naimaryan1/KD_TREE] yesterday which should give
me a good start. The approach used there is to simply rebuild the tree each
time the number of nodes doubles.
> Point Set/Map
> -------------
>
> Key: GEOMETRY-142
> URL: https://issues.apache.org/jira/browse/GEOMETRY-142
> Project: Apache Commons Geometry
> Issue Type: New Feature
> Reporter: Matt Juntunen
> Priority: Major
>
> It would be very useful to have set and map implementations that accepts
> points and vectors as keys and use "fuzzy" look up logic, where values are
> compared using a precision context. This would have uses in a number of
> situations, including the implementation of GEOMETRY-110.
> Options for the implementation of such classes include
> * BSP trees (as already implemented)
> * k-d trees
> * quadtrees/octrees
> * r-trees
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
