Hello.
> >
> > 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.
>
We should be careful not to prevent future flexibility by assuming that a
"Vector" is a Cartesian vector.
I.e. we should not assume that a generic getter "get(int)" will return the
Cartesian coordinates. Maybe that an extended interface would do:
-----
public interface Cartesian<S> extends Vector<S extends Space> {
public double getCartesianCoordinate(int i);
}
-----
> >
> > 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.
I guess that we could drop the cast (with the new interface):
-----
public Vector3D toSpace(final Cartesian<Euclidean2D> point) {
return new Vector3D(point.getCartesianCoordinate(0), u,
point.getCartesianCoordinate(1), v,
-originOffset, w);
}
-----
>
> >
> > 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.
Several algorithms, yes; but if they share anything (in principle) they
should be designed so as to avoid code duplication. [Maybe that the
situation is similar to "SimplexOptimizer", where there are two different
strategies for the simplex update ("NelderMead" and "MultiDirectional").]
> >
> > Maybe we should also create an algo package which will serve as home for
> > such algorithms?
>
> This seems too broad a category.
I agree; ultimately almost everything would go in "algo" ;-).
At this point, I don't have a proposal on how to organize those
functionalities.
I'd be wary about creating a mirror of what is under "euclidean" (i.e.
"oned", "twod", etc.); e.g. this would better be avoided:
euclidean/oned
/twod
/threed
hull/oned
/twod
/threed
Ideally, common (non-dimension-specific) algorithms would go under "hull"
and dimension-specific implementations (if needed or useful) would go under
the corresponding sub-packages of "euclidean".
Best regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
