commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] geometry algorithms
Date Tue, 09 Oct 2012 19:38:15 GMT
Le 09/10/2012 20:21, Thomas Neidhart a écrit :
> Hi,

Hi Thomas,

> I started to work on the proposed new features, namely convex hull and
> voronoi diagrams but am a bit stuck with the API design.
> The current type structure in the geometry package introduced a so
> called Space with different implementation for 1D, 2D and 3D. To
> represent a Vector in the respective space, a Vector<S extends Space>
> interface exists, with implementing classes for each Space:
>  * Vector1D
>  * Vector2D
>  * Vector3D
> Unfortunately, the Vector interface does not provide a generic access
> method to each component, e.g. get(int) to get the ith component of the
> vector. Each subclass has its own getX(), getY() ... method according to
> the dimension of the Space. This makes it impossible to implement a
> generic algorithm using the Space as type parameter.

Yes, it would be nice to add a generic getter. In fact, we also thought
about implementing the whole RealVector methods. This has to be thought
again since now RealVector is an abstract class.

> Ok, so I was thinking about separate algorithms for the different
> spaces. Now when trying to generify a ConvexHull interface using the
> Space I would have something like this:
> public interface ConvexHull<S extends Space> {
>     Vector<S>[] generate(Vector<S>[] points);
> }
> e.g. with an implementation of the 2D GrahamScan algorithm:
> public class GrahamScan2D implements ConvexHull<Euclidean2D> {
>   public Vector<Euclidean2D>[] generate(
>             final Vector<Euclidean2D>[] points) { ... }
> }
> So the Vector types would not be Vector2D, Vector3D but the generic
> ones. Users would need to explicitly cast to them, as I guess these are
> more convenient to use.

I think you are speaking about what we have already encountered in BSP
trees. For example the 3D Plane implements the toSpace method from the
Embedding interface as follows:

      public Vector3D toSpace(final Vector<Euclidean2D> point) {
        final Vector2D p2D = (Vector2D) point;
        return new Vector3D(p2D.getX(), u,
                            p2D.getY(), v,
                            -originOffset, w);

So yes, there is an ugly cast somewhere.

> A better solution would be to ignore the Space for now and define the
> interface as follows:
> public interface ConvexHull<S extends Space, V extends Vector<S>> {
>     V[] generate(V[] points);
> }
> which allows me to use Vector2D and so forth directly in the implementation.

This is interesting.

> Package structure:
> right now the geometry package is structured as follows:
>  * basic interfaces in the base package
>  * euclidean package split up for the 1D, 2D and 3D cases
>  * partitioning package
> I started creating a hull package, which will contain the outlined
> ConvexHull interface, and implementations, for the different Spaces,
> e.g. GrahamScan2D, DivideAndConquer2D, Chan3D
> Does this make sense? Or should I stick to the general case and provide
> only one algorithm for the 2D and 3D respectively?

No, several algorithms are a good thing. I think all of them have their
pros and cons so they are suited for different problems (accuracy,
speed, memory requirement, size of data...) and users can choose the
best one.

> Maybe we should also create an algo package which will serve as home for
> such algorithms?

This seems too broad a category.

best regards,

> Thanks,
> Thomas
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

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

View raw message