[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17449570#comment-17449570
]
Matt Juntunen commented on GEOMETRY-142:
----------------------------------------
I've added a [performance testing
harness|https://github.com/darkma773r/commons-geometry/blob/point-map/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/pointmap/PointMapDataStructurePerformance.java]
along with an [initial
implementation|https://github.com/darkma773r/commons-geometry/blob/point-map/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/pointmap/VariableSplitOctree.java]
of what I'm calling a "variable split octree" data structure. The
implementation is by no means complete but it should be sufficient to compare
with other data structures.
The performance test uses the Java's {{TreeMap}} implementation as a baseline.
This class does not actually work for the purposes of a point map but I'm using
it as a general baseline for how a well-designed tree structure should perform.
So far, the octree implementation is slower, in some cases by a small margin
and in others by a lot. This is most likely because the octree is not
self-balancing. More work will be needed to figure that out.
My next step is to add another candidate data structure to the mix. I'm
picturing using a modified k-d tree with the points as the nodes. Instead of
splitting in a single dimension at each node, I'm going to try to split the
tree in all 3 dimensions, similar to what the octree is doing.
> 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)
