[jira] [Commented] (GEOMETRY-32) BSPTree Updates

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[jira] [Commented] (GEOMETRY-32) BSPTree Updates

Woonsan Ko (Jira)

    [ https://issues.apache.org/jira/browse/GEOMETRY-32?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16931956#comment-16931956 ]

Matt Juntunen commented on GEOMETRY-32:

{quote}My impression is that what we "intuitively" expect contradicts what is "naturally" provided by the framework.
This is not just a matter of intuition, but also of the properties of the region. The points that are in the interior of the region must remain in the interior when everything is transformed. In other words, if we consider the region as a set of points, then the transform may modify the coordinates of the points but must not change their membership in the set. If we did not handle the case where the orientation is not preserved, then this may not hold true. For example, in the previous scenario, the point (1, 1) is in the interior of the region. However, if we did not flip the interior and exterior, then the transformed point (-1, 1) would be on the exterior of the transformed region.
{quote}From the above, I'd feel that the clean way out of the contradiction is to _change the orientation of the bounding lines_ rather than _flip the interior/exterior_.
This is exactly what is done for the immutable convex region classes (ex: [https://github.com/darkma773r/commons-geometry/blob/geometry-32-working/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegion.java#L187).] However, the hyperplane orientations are less important in the BSP tree classes (after the initial insertion, at least) and so the interior and exterior nodes are simply swapped. When the boundary is extracted from the BSP tree, then the hyperplanes are adjusted to have the correct orientations.
{quote}I get that the result would be the same when the POV is on the intuitive meaning of the transforms being discussed here, but I wonder if the decoupling of transformation and orientation would not lead to a better design (and ultimately more flexibility?).
What do you mean here?

> 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: 20m
>  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