[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17512725#comment-17512725 ] Matt Juntunen commented on GEOMETRY-142: Completed in commit 6c6d046532ab6c0c5cd670aaa4dc9ad384190d97. > Point Set/Map > - > > Key: GEOMETRY-142 > URL: https://issues.apache.org/jira/browse/GEOMETRY-142 > Project: Commons Geometry > Issue Type: New Feature >Reporter: Matt Juntunen >Assignee: Matt Juntunen >Priority: Major > Fix For: 1.1 > > > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17504706#comment-17504706 ] Matt Juntunen commented on GEOMETRY-142: I think I've gotten this as good as I'm going to get it. The [final PR|https://github.com/apache/commons-geometry/pull/194] is submitted and ready for review. Let me know what you think! > Point Set/Map > - > > Key: GEOMETRY-142 > URL: https://issues.apache.org/jira/browse/GEOMETRY-142 > Project: Commons Geometry > Issue Type: New Feature >Reporter: Matt Juntunen >Assignee: Matt Juntunen >Priority: Major > Fix For: 1.1 > > > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17502028#comment-17502028 ] Matt Juntunen commented on GEOMETRY-142: I've made some performance improvements and added the set implementations and basic tests. Everything should be ready for review at this point on the draft PR, although I still need to add some more unit tests and documentation. > Point Set/Map > - > > Key: GEOMETRY-142 > URL: https://issues.apache.org/jira/browse/GEOMETRY-142 > Project: Commons Geometry > Issue Type: New Feature >Reporter: Matt Juntunen >Assignee: Matt Juntunen >Priority: Major > Fix For: 1.1 > > > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17496825#comment-17496825
]
Matt Juntunen commented on GEOMETRY-142:
Just finished implementing spherical 1D and 2D maps. The Euclidean and
spherical 1D maps are based on {{TreeMap}} while all of the multidimensional
maps extend {{{}AbstractBucketPointMap{}}}, which contains the majority of the
code. I still need to add some dimension-specific unit tests and maybe tweak
some things. For example, I think there needs to be some logic that will
rebuild the tree if it gets too out of balance. Adding points in sorted order
currently produces trees with unacceptable performance.
> 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
>Assignee: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17491588#comment-17491588
]
Matt Juntunen commented on GEOMETRY-142:
Thanks for the feedback, [~aherbert] and [~kinow]! I've reorganized things and
moved all of the factory methods to a {{EuclideanCollections}} class. (I used
that name instead of {{PointMaps}} so I can also put the {{PointSet}} factory
methods in there later on.) I've also created a draft PR for easier code
review: https://github.com/apache/commons-geometry/pull/193
> 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
>Assignee: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17491526#comment-17491526 ] Bruno P. Kinoshita commented on GEOMETRY-142: - Said that, I looked at the code, and it wasn't hard to understand how to use the `.of` method. I couldn't understand other parts (how to create and use a PointMapAsSetAdapter.java for example, but that's probably because I need to learn more of the new code). [~mattjuntunen] wouldn't you like to have a pull request in GitHub, to gather the feedback there? I synced the code, and browsed the changes using GitHub UI: [https://github.com/darkma773r/commons-geometry/compare/master...point-map,] manually closing the files as I read each one. > 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 >Assignee: Matt Juntunen >Priority: Major > Fix For: 1.1 > > > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17491493#comment-17491493 ] Bruno P. Kinoshita commented on GEOMETRY-142: - I think the factory method in a factory class, as suggested by Alex, is more common than having the factory method in an interface. > 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 >Assignee: Matt Juntunen >Priority: Major > Fix For: 1.1 > > > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17491473#comment-17491473
]
Alex Herbert commented on GEOMETRY-142:
---
Put the static factory methods in a factory class?
{code:java}
public static final class PointMaps {
public static PointMap3D create3D(Precision.DoubleEquivalence precision);
}{code}
> 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
>Assignee: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17491454#comment-17491454
]
Matt Juntunen commented on GEOMETRY-142:
I just completed initial implementations of the {{PointMap}} interface for
Euclidean 1D, 2D, and 3D and pushed them to my working branch
(https://github.com/darkma773r/commons-geometry/tree/point-map). In order to
completely hide the implementation details, I created dimension-specific
interfaces with factory methods that return instances of a package-private
class. For example, this is how you create a 3D point map in the current code:
{code:java}
Precision.DoubleEquivalence precision =
Precision.doubleEquivalenceOfEpsilon(1e-6);
// PointMap3D is an interface; the returned instance is of the package-private
class PointMap3DImpl
PointMap3D map = PointMap3D.of(precision);
{code}
I'm not totally sure of this design. It seems kind of odd to have a factory
method on an interface and I feel like the factory method name "of" isn't quite
right. However, I know that the map implementation will most likely undergo
optimizations and so needs to isolated from the public API.
In terms of the implementations, the 1D point map uses a JDK {{TreeMap}}
internally while the 2D and 3D maps use a base class that implements the
quadtree/octree approach that was the winner of the algorithm performance tests.
Feedback is welcome. I'm picturing the next step to be implementing maps for
spherical 1D and 2D. I won't be able to use the same algorithms there as for
Euclidean. I'm thinking a modified {{TreeMap}} for 1D and a BSP-based data
structure for 2D.
> 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
>Assignee: Matt Juntunen
>Priority: Major
> Fix For: 1.1
>
>
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17480558#comment-17480558 ] Matt Juntunen commented on GEOMETRY-142: Cool. Thanks, [~kinow]! > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17480549#comment-17480549 ] Bruno P. Kinoshita commented on GEOMETRY-142: - No objections [~mattjuntunen] . +1 on the initial implementation. I just synced the branch I had, and to get mvn command passing, had to add this diff --git a/pom.xml b/pom.xml index 5e14c5dc..05487f7e 100644 --- a/pom.xml +++ b/pom.xml @@ -335,6 +335,7 @@ src/site/resources/release-notes/RELEASE-NOTES-*.txt src/site/resources/txt/userguide/stress/** dist-archive/** + commons-geometry-examples/examples-jmh/src/main/resources/jmh-data/teapot-points.txt Looking forward to the pull request! > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17477344#comment-17477344
]
Matt Juntunen commented on GEOMETRY-142:
I tried a few more optimizations and it looks like {{varoctree}} is still the
best algorithm, especially since I improved the {{remove}} performance. The
final results are below.
||Benchmark||(dist)||(impl)||(randomSeed)||(shape)||Mode||Cnt||Score||Error||Units||
|get|random|treemap|1|teapot|avgt|5|8201248.381|± 885353.659|ns/op|
|get|random|varoctree|1|teapot|avgt|5|9954012.963|± 1467457.747|ns/op|
|get|random|kdtree|1|teapot|avgt|5|12047536.590|± 3986439.960|ns/op|
|get|random|rebuilding-kdtree|1|teapot|avgt|5|11241847.287|± 4950094.941|ns/op|
|get|random|bucket-kdtree|1|teapot|avgt|5|14269957.001|± 2984764.586|ns/op|
|get|random|bucket-leaf-kdtree|1|teapot|avgt|5|12613411.642|± 1912904.807|ns/op|
|put|random|treemap|1|teapot|avgt|5|4466342.881|± 829095.368|ns/op|
|put|random|varoctree|1|teapot|avgt|5|6498643.402|± 1110163.867|ns/op|
|put|random|kdtree|1|teapot|avgt|5|7788556.065|± 1568465.224|ns/op|
|put|random|rebuilding-kdtree|1|teapot|avgt|5|6924748.449|± 1312331.439|ns/op|
|put|random|bucket-kdtree|1|teapot|avgt|5|8580674.695|± 3265464.066|ns/op|
|put|random|bucket-leaf-kdtree|1|teapot|avgt|5|6440019.212|± 3284091.562|ns/op|
|remove|random|treemap|1|teapot|avgt|5|160111.447|± 14035.741|ns/op|
|remove|random|varoctree|1|teapot|avgt|5|191145.633|± 45804.812|ns/op|
|remove|random|kdtree|1|teapot|avgt|5|164994.365|± 78422.804|ns/op|
|remove|random|rebuilding-kdtree|1|teapot|avgt|5|197497.579|± 86483.448|ns/op|
|remove|random|bucket-kdtree|1|teapot|avgt|5|226619.480|± 69024.069|ns/op|
|remove|random|bucket-leaf-kdtree|1|teapot|avgt|5|188944.887|±
84743.239|ns/op|
Unless there are any objections or additional ideas, I'm going to start working
on {{PointMap}} implementations for Euclidean 2D and 3D based on this algorithm.
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17467761#comment-17467761
]
Matt Juntunen commented on GEOMETRY-142:
I've added another implementation named {{BucketKDTree}} that stores single
entries in splitting nodes as well as in leaf nodes as lists. However, the
performance is worse than the other implementations. The best implementation
for {{get}} and {{put}} performance is {{varoctree}}, although it does terribly
with {{remove}}. I think the next step is to explore {{varoctree}} a bit more
and see if this can be improved.
||Benchmark||(impl)||(pointDist)||(randomSeed)||(randomized)||Mode||Cnt||Score||Error||Units||
|PointMapDataStructurePerformance.get|treemap|block|1|true|avgt|5|2535086.177|±
196957.459|ns/op|
|PointMapDataStructurePerformance.get|varoctree|block|1|true|avgt|5|3835217.249|±
106874.863|ns/op|
|PointMapDataStructurePerformance.get|kdtree|block|1|true|avgt|5|5918314.090|±
433275.740|ns/op|
|PointMapDataStructurePerformance.get|rebuilding-kdtree|block|1|true|avgt|5|5046805.168|±
397529.992|ns/op|
|PointMapDataStructurePerformance.get|bucket-kdtree|block|1|true|avgt|5|6028908.768|±
598811.980|ns/op|
|PointMapDataStructurePerformance.put|treemap|block|1|true|avgt|5|1543477.168|±
59915.220|ns/op|
|PointMapDataStructurePerformance.put|varoctree|block|1|true|avgt|5|1721624.355|±
31012.494|ns/op|
|PointMapDataStructurePerformance.put|kdtree|block|1|true|avgt|5|7977304.891|±
122840.849|ns/op|
|PointMapDataStructurePerformance.put|rebuilding-kdtree|block|1|true|avgt|5|5687657.624|±
132680.481|ns/op|
|PointMapDataStructurePerformance.put|bucket-kdtree|block|1|true|avgt|5|76366216.557|±
964906.841|ns/op|
|PointMapDataStructurePerformance.remove|treemap|block|1|true|avgt|5|54016.786|±
22942.461|ns/op|
|PointMapDataStructurePerformance.remove|varoctree|block|1|true|avgt|5|1513340.914|±
40069.462|ns/op|
|PointMapDataStructurePerformance.remove|kdtree|block|1|true|avgt|5|61120.730|±
11036.797|ns/op|
|PointMapDataStructurePerformance.remove|rebuilding-kdtree|block|1|true|avgt|5|79552.232|±
10029.806|ns/op|
|PointMapDataStructurePerformance.remove|bucket-kdtree|block|1|true|avgt|5|91491.103|±
14820.207|ns/op|
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17457773#comment-17457773
]
Matt Juntunen commented on GEOMETRY-142:
I've implemented a standard {{KDTree}} and a subclass named
{{RebuildingKDTree}} that rebuilds the tree every time the tree size changes by
a multiple of 2. The rebuilding algorithm is a very simple, brute-force
algorithm so there is still a lot of work to do there. Note that these trees do
_not_ split on all 3 dimensions like I was mentioning before. The algorithms
are much simpler when only a single dimension is split at a time.
Below are the results from one of the performance tests.
||Benchmark||(impl)||(pointDist)||(randomSeed)||(randomized)||Mode||Cnt||Score||Error||Units||
|PointMapDataStructurePerformance.get|treemap|block|1|true|avgt|5|1901011.695|±
267736.431|ns/op|
|PointMapDataStructurePerformance.get|varoctree|block|1|true|avgt|5|2216097.740|±
30461.346|ns/op|
|PointMapDataStructurePerformance.get|kdtree|block|1|true|avgt|5|9498722.093|±
648666.885|ns/op|
|PointMapDataStructurePerformance.get|rebuilding-kdtree|block|1|true|avgt|5|6910157.540|±
649841.106|ns/op|
|PointMapDataStructurePerformance.put|treemap|block|1|true|avgt|5|1918716.941|±
51856.642|ns/op|
|PointMapDataStructurePerformance.put|varoctree|block|1|true|avgt|5|2228210.059|±
48411.970|ns/op|
|PointMapDataStructurePerformance.put|kdtree|block|1|true|avgt|5|10285677.435|±
213900.413|ns/op|
|PointMapDataStructurePerformance.put|rebuilding-kdtree|block|1|true|avgt|5|7505692.915|±
340146.696|ns/op|
|PointMapDataStructurePerformance.remove|treemap|block|1|true|avgt|5|73542.543|±
15082.714|ns/op|
|PointMapDataStructurePerformance.remove|varoctree|block|1|true|avgt|5|2037858.976|±
430068.967|ns/op|
|PointMapDataStructurePerformance.remove|kdtree|block|1|true|avgt|5|88291.325|±
15735.485|ns/op|
|PointMapDataStructurePerformance.remove|rebuilding-kdtree|block|1|true|avgt|5|111478.176|±
14909.521|ns/op|
*Observations*
- Varoctree is actually not that bad for get and put. I thought it would be
much worse compared to the other ones.
- Rebuilding the tree periodically improved the KD tree performance except on
remove.
*Next steps*
- Work on improving the performance of the rebuild algorithm.
- Continue researching alternative algorithms.
> 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17450168#comment-17450168 ] Bruno P. Kinoshita commented on GEOMETRY-142: - Had a read this morning in the code and in the octree wikipedia page to remind me how it works (I remembered seeing it in gaming & GIS projects before, but never used it). >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. Sounds like a good initial implementation, but interested to see the k-d tree - this one never had to use, and can't recall reading about either, so looking forward to learning something new soon :) Great job so far Matt! -Bruno > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[
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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17449200#comment-17449200 ] Matt Juntunen commented on GEOMETRY-142: Welcome, [~kinow]! The more, the merrier :-) > 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)
[jira] [Commented] (GEOMETRY-142) Point Set/Map
[ https://issues.apache.org/jira/browse/GEOMETRY-142?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17448446#comment-17448446 ] Bruno P. Kinoshita commented on GEOMETRY-142: - No idea what's the best way to implement it (not even sure where to start, to be honest). But sounds so interesting that I've subscribed to this issue to follow & learn. Maybe try to help too, but am sure I will end up mainly learning here. Thanks [~mattjuntunen] ! > 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)
