On 10/10/2012 02:09 PM, Gilles Sadowski wrote:
> Hello.
>
Hi Luc, Gilles,
>>> 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);
> }
> -----
>
hmm, I am split on this. It sounds right but may also introduce an
additional layer that is not necessary at all.
>>>
>>> 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.
indeed, I am particularly interested in output-sensitive algorithms like
Chan's algorithm, but they are more difficult to implement.
> 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".
this sound like a good plan, I did not intend to reproduce the
oned/twod/threed package structure from the euclidean package.
Otoh, distributing implementations over several packages could also be
confusing for users (and for developers too). Atm I also do not know if
a fully generic algorithm is possible, so that you would instantiate it
for the space you are interested in, like:
ConvexHull hull = new DivideAndConquer<Euclidean3D, Vector3D>();
...
or whether there will be a specific class:
ConvexHull hull = new DivideAndConquer3D();
which may reside in euclidean.threed and uses common parts which are in
geometry.hull
Anyway thanks for your comments,
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
