commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] recursive typing
Date Sun, 22 May 2011 20:38:12 GMT
Le 22/05/2011 22:09, Phil Steitz a écrit :
> On 5/22/11 4:20 AM, Luc Maisonobe wrote:
>> Hello,
>> The BSP tree code introduced recently into [math] was written
>> several years ago, in the Java 4 days. The implementation was
>> already dimension independent (and even topology-independent) and
>> used simple interfaces like Point (which was a marker interface
>> without any methods), Hyperplane, Transform ... The
>> implementations of these interfaces were aware of the dimension,
>> so for example an hyperplane in 3D is a Plane, but an hyperplane
>> in 2D is a Line.
> Question number 1, is this level of abstraction practically useful?
> Need to ask this both for dimension and topology.

Yes, it allow to share some really difficult code and separate the tree 
logic (walking trees, splitting cells, merging sub-trees ...) from the 
geometry (computing planes, lines, circles intersection). Once the logic 
of the algorithm is validated, using it for other geometry contexts is 
far easier, we only have to tackle geometric problems.

It is also the way it is already implemented since a few years (this is 
old code that simply needs some cleaning).

>> This implied lots of casts between types and the developer had to
>> be aware of what types were currently used. This is tricky and
>> error-prone, especially when looking at the BSP tree. BSP-tree are
>> recursive from a geometry point of view: we split space, then
>> split the resulting half space, the split again and again to
>> create a large number of convex polytopes which are at least glued
>> together to form non-convex shapes. BSP-tree are also recursive
>> from a dimension point of view as for example a 3D shape is
>> defined in the 3D space, the cutting planes are 2D sub-spaces in
>> the 3D space, the boundaries (facets) are themselves 2D shapes
>> (polygons) inside these 2D planes, these 2D shapes are defined by
>> 2D BSP-trees, which cutting planes are 1D lines, which ... So from
>> a type point of view we go from 3D to 2D to 1D and use the whole
>> set of classes and interfaces at each dimension: Hyperplane,
>> SubHyperplane, SplitSubHyperplane, Point, Region ...
>> I am trying to simplify this and use generics to both avoid typing
>> errors and having a code that can be understood and maintained. A
>> classical error I have already made a large number of time during
>> development was to mix dimensions. A typical example occurs while
>> dealing with hyperplanes, as one can see a point belonging to the
>> hyperplane both as a point in the n dimensions space or as a point
>> in the n-1 dimensions hyperplane.
> I wonder if generics are really the right way to do this.  Have you
> considered just making dimensionality an attribute?

This would work only for Euclidean spaces, and I need to extend this to 

>> The start point for the refactoring was to add generics and use
>> HyperPlane<Vector3D>, BSPTree<Vector3D>  and the likes.
>> Unfortunately, I am facing some unexpected (and interesting)
>> problems. Since BSPTree needs to both handle the global space and
>> the cut hyperplanes, it needs to be parameterized with the two
>> dimensions, so it appeared I should rather use BSPTree<Vector3D,
>> Point2D>. But then, the sub-hyperplanes inside a BSPTree
>> themselves are parameterized by Point2D and need to access 1D
>> points. These sub-hyperplanes should be SubHyperplane<Point2D,
>> Point1D>. As these sub-hyperplanes are stored in BSPTree, either
>> the attributes in BSPTree should use raw types or should also have
>> the parameters an be BSPTree<Vector3D, Point2D, Point1D>. We have
>> here a recursive type definition and the recursion stop condition
>> corresponds to dimension 0.
>> I don't know yet how to set up something simple and type-safe. My
>> current guess is that I should separate some interfaces in two
>> interfaces, say Hyperplane<SpacePoint>  and Embedding<SpacePoint,
>> SubSpacePoint>, even if the implementation (for example Plane in
>> 3D) would implement both interfaces.
>> If someone has another idea, I would be interested to read about it.
> The only thing that occurs to me is to move to using attributes for
> dimensionality.   If you need arbitrary dimension support, you will
> effectively have to do this; otherwise what you are suggesting above
> is a little complicated but should work.  The real question is how
> important is type-safety as defined above.  This is sort of like
> ensuring matrix operations are well defined by exhaustively typing
> columns.  With bounded dimensions you could do that; but how bad is
> it really to have the dimension-checking attribute-based at runtime?

Thanks for the hint, I'll look at it.
I am currently trying another idea, simpler than my previous one.
Basically, I have only one parameter Space which is implemented as 
Euclidean3D, Euclidean2D, Euclidean1D and serve almost only as a marker. 
All top level interfaces depend only on this parameter:
Hyperplane<S extends Space>, SubHyperplane<S extends Space>, BSPTree<S 
extends Space> ...
The recursion stated above is now hidden in the implementation of 
SubHyperplane using an abstract class:

  AbstractSubHyperplane<S extends Space, T extends Space>
       implements SubHyperplane<S>.

So everything is declared using only the largest dimension (S), but the 
concrete class can rely on elements defined in lower dimensions (T). It 
seems to work with only a few casts and suppressWarning. I agree I 
cannot have a complete type safe system here.


> Phil
>> best regards,
>> Luc
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail:
>> For additional commands, e-mail:
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message