[
https://issues.apache.org/jira/browse/GEOMETRY-32?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16800111#comment-16800111
]
Matt Juntunen commented on GEOMETRY-32:
---------------------------------------
Update:
]I'm making slow, steady progress on this. I currently have the following types
in place and tested:
- {{BSPTree}} and {{BSPTree.Node}} interfaces
- {{AbstractBSPTree}} and {{AbstractNode}} classes that implement most basic
tree functionality
- {{AttributeBSPTree}} class for storing arbitrary attributes in a tree
- {{RegionBSPTree}} class for using trees to represent spatial regions. This
contains the core functionality from the original {{BSPTree}} class.
Here are some of my remaining tasks:
- Complete the region boolean operations, ie _union_, _intersection_,
_difference_, _xor_. I finally got the basic algorithm working for this last
night after much tribulation. I need to add and test the remaining methods and
then maybe clean up the API.
- Add the {{BSPTree#transform(Transform t)}} method.
- Create/update the Subhyperplane classes in Euclidean 1D, 2D, and 3D and
spherical 1D and 2D so that they implement the new {{SubHyperplane}} and
{{ConvexSubHyperplane}} interfaces. This is actually the work of GEOMETRY-32,
but I need to do it as part of this if we want to remove the old {{BSPTree}}
hierarchy.
- Create space-specific {{RegionBSPTree1D}}, {{RegionBSPTree2D}}, etc..
classes with an API designed specifically for each type of space. I'm picturing
these types as replacing the {{IntervalsSet}}, {{PolygonsSet}}, and
{{PolyhedronsSet}} classes since they will contain all of the functionality of
the former (and more). I'm planning on removing the {{Region}} interface as
well since it doesn't seem needed anymore. This is also the work of another
issue, GEOMETRY-33, but we can't remove the old {{BSPTree}} types without it.
I could use some feedback on the following:
- The region boolean operations in the old code would modify both the caller
and the argument. For example, after the call {{tree.merge(otherTree,
leafMerger)}}, {{tree}} would be modified to contain the result, but
{{otherTree}} would also be modified and rendered unusable. I don't like this
approach because it makes it necessary to create copies of potentially very
large tree structures each time a boolean operation is applied. My current idea
is to create two versions of each boolean method: one that modifies one of the
input trees to store the answer and another one that leaves both inputs
unmodified and stores the result in a third tree. Users could then choose the
most efficient method based on what inputs need to remain unchanged. Here is
what I'm picturing:
{code:java}
public class RegionBSPTree<P extends Point<P>> extends BSPTree<P,
RegionNode<P>> {
// Compute the union of this instance and the argument and store the result
in this instance.
// The argument is not modified.
void union(RegionBSPTree<P> otherTree);
// Compute the union of the two arguments and store the result in this
instance. Neither
// argument is modified.
void unionOf(RegionBSPTree<P> a, RegionBSPTree<P> b);
void intersection(RegionBSPTree<P> otherTree);
void intersectionOf(RegionBSPTree<P> a, RegionBSPTree<P> b);
// Compute the complement of this instance and store the result in this
instance.
void complement();
// Compute the complement of the argument and store the result in this
instance.
// The argument is not modified.
void complementOf(RegionBSPTree<P> otherTree);
}
{code}
In all cases, the caller is modified and the arguments are not. WDYT?
> BSPTree Updates
> ---------------
>
> Key: GEOMETRY-32
> URL: https://issues.apache.org/jira/browse/GEOMETRY-32
> Project: Apache Commons Geometry
> Issue Type: Improvement
> Components: core
> Reporter: Matt Juntunen
> Priority: Major
> Labels: pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> The following updates should be made to the BSPTree class:
> - add an {{isLeaf()}} method to replace all of the {{node.getCut() == null}}
> expressions
> - add unit tests
> _Edit [2019-02-17]:_
> Additional goals:
> - Refactor the API to split the idea of a general BSPTree and a BSPTree used
> for defining in/out regions. This could result in a BSPTree interface and a
> RegionBSPTree interface. The goal here is to allow end-users to create their
> own extensions of these classes and specialize them for their own
> applications (for example, to implement spatial sorting or other algorithms).
> This will be one of the only planned extension points in the library.
> - Make the API easier to use and extend and reduce the necessity of casting
> (especially unchecked casting) as much as possible.
> - Add the idea of convex subhyperplanes to allow for more efficient tree
> construction.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
