You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Thomas Neidhart <th...@gmail.com> on 2012/10/09 20:21:25 UTC
[math] geometry algorithms
Hi,
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.
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.
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.
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?
Maybe we should also create an algo package which will serve as home for
such algorithms?
Thanks,
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
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);
> > }
> > -----
> >
>
> hmm, I am split on this. It sounds right but may also introduce an
> additional layer that is not necessary at all.
It's true that we could just add a method to the "Vector" interface:
-----
public double getCartesianCoordinate(int i);
-----
[But it should not be named "get(int i)" since that would be confusing if we
ever wanted to create a subclass, say of "Vector3D", to represent spherical
coordinates.]
> [...]
> > 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). [...]
The idea was to group tools by dimension, like there is now e.g. "Vector3D"
and (tridimensional) "Rotation" in the same "threed" subpackage of
"geometry".
> [...]
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Thomas Neidhart <th...@gmail.com>.
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: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Luc Maisonobe <Lu...@free.fr>.
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,
Luc
>
> Thanks,
>
> Thomas
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
> >> [...]
> >>
> >> public interface ConvexHull<S extends Space> {
> >> Vector<S>[] generate(Vector<S>[] points);
> >> }
> >
> > I think that you should use "List" instead of arrays (even "Iterable"
> > whenever possible); it will be plainly more flexible. Just a little
> > thought...
>
> I have now several implementations of at least 2D algorithms with this
> interface:
>
> Iterable<Vector2D> generate(Iterable<Vector2D> points)
>
> which works, but I find it quite cumbersome for the following reasons:
>
> * Iterable obviously does not provide a size() method which is quite
> handy in the algorithms
>
> * the addAll() method of collections is not defined for Iterable, but
> only for Collection
If the algorithm needs some API to perform decently, it's fair to require
it.
>
> So I would better opt for an interface like:
>
> Iterable<Vector2D> generate(Collection<Vector2D> points)
>
> The output may be an Iterable as it is ordered, a Collection might give
> a wrong impression to the user (a Collection is not sorted per se,
> although the same is true for Iterable, hmm)
I don't understand; should the output be sortable?
> What do you think?
Not mixing different types makes the API simpler; the prototype could be
Collection<Vector2D> generate(Collection<Vector2D> points)
or
List<Vector2D> generate(List<Vector2D> points)
[Also, usability is enhanced by arguments as abstract as possible, but the
returned value's concreteness is only limited by the developer's willingness
to not be tied to a specific data structure.]
If the answer to the above question is yes, then the second prototype makes
more sense.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Thomas Neidhart <th...@gmail.com>.
On 10/10/2012 12:04 AM, Gilles Sadowski wrote:
> Hi.
>
>> [...]
>>
>> public interface ConvexHull<S extends Space> {
>> Vector<S>[] generate(Vector<S>[] points);
>> }
>
> I think that you should use "List" instead of arrays (even "Iterable"
> whenever possible); it will be plainly more flexible. Just a little
> thought...
I have now several implementations of at least 2D algorithms with this
interface:
Iterable<Vector2D> generate(Iterable<Vector2D> points)
which works, but I find it quite cumbersome for the following reasons:
* Iterable obviously does not provide a size() method which is quite
handy in the algorithms
* the addAll() method of collections is not defined for Iterable, but
only for Collection
So I would better opt for an interface like:
Iterable<Vector2D> generate(Collection<Vector2D> points)
The output may be an Iterable as it is ordered, a Collection might give
a wrong impression to the user (a Collection is not sorted per se,
although the same is true for Iterable, hmm)
What do you think?
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] geometry algorithms
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hi.
> [...]
>
> public interface ConvexHull<S extends Space> {
> Vector<S>[] generate(Vector<S>[] points);
> }
I think that you should use "List" instead of arrays (even "Iterable"
whenever possible); it will be plainly more flexible. Just a little
thought...
Regards,
Gilles
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org