On 01/27/2014 10:13 AM, Luc Maisonobe wrote: > Le 26/01/2014 23:52, Thomas Neidhart a écrit : >> Hi, > > Hi Thomas, > >> >> finally, I have a patch ready to be included for MATH-749. >> What took me so long was some confusion about the type system in the >> geometry package. >> >> It is actually quite difficult to do some generic algorithm code by only >> specifying the relevant space type (e.g. Euclidean2D). > > Yes, I know. I am the one to be blamed for this mess. > The reason for it is that for partitioning needs, there are several > interdependent classes and the generic type system in Java is quite limited.
It is certainly not a mess, but maybe too specific for the original use-case of a BSP. Something that I would like to see in 4.0: make the Vector interface very light-weight, so that it is easy to implement also for domain objects, similar to the Clusterable interface in ml.clustering, but as you said, lets discuss this later. >> >> The Vector/Point interface does not allow access to its components, thus >> any algorithm that needs access to them either has to cast, or >> explicitly specify the type. >> >> I decided now to come up with the following: >> >> There is a generic interface for convex hull generators: >> >> public interface ConvexHullGenerator<S extends Space, V extends Vector<S>> > > I was doing *exactly* the same thing yesterday for a generic Ball class > (containing a point and a radius) to be used as the return value of a > smallest enclosing ball using Emo Welzl algorithm. > > So I agree this is one way we could go. good. Today I was thinking of adding an additional interface for the 2D case, to make it more specific for users: public interface ConvexHullGenerator2D<V extends Vector2D> extends ConvexHullGenerator<Euclidean2D, V> the concrete implementations would then implement this interface. >> and currently one concrete implementation for the euclidean 2d space: >> >> public class GrahamScan2D<V extends Vector2D> implements >> ConvexHullGenerator<Euclidean2D, V> >> >> The reason GrahamScan2D still has a generic type parameter is because I >> wanted to cover also the use-case of people extending Vector2D, although >> I am not sure if this is realistic/useful. We may also change this to: >> >> public class GrahamScan2Dimplements ConvexHullGenerator<Euclidean2D, >> Vector2D> >> >> >> Ideally, the Vector interface would have a method >> >> double getComponent(int dimension) >> >> or >> >> double[] getData() >> >> to provide access to the components of the vector and I would like to >> discuss this for 4.0 considering the other uses of Vector. > > For sure, we need to clean up my mess for 4.0. > I think that Point/Vector should be used rather than Space as the > discriminator for other classes (and perhaps Space could completely > disappear). Another change that would be interesting would be to replace > inheritance with delegation wherever possible in the partitioning part > to avoid some internal purpose interfaces like (Hyperplane, > SubHyperplane, ...) to leak into public interface when they are only > here for internal purposes. But lets wait until 4.0 for this discussion. +1. >> Anyway, I would be grateful if somebody could review the patch. If the >> general interface is accepted, I plan to add more implementations. > > I wonder if it would be interesting to have some connection links in the > output instead of a raw Collection<Point>. A Vertex/Edge structure would > be interesting for a hull I think. Collection is certainly sub-optimal, at least we should return a List, as the vertices are ordered. > In the recent spherical.twod package, Edge and Vertex have been > extracted as public classes and can be used to loop around boundaries. > > In the former euclidean.twod package, there are also an Edge and a > Vertex class, but they still are inside PolygonsSet and are even > private. They could easily be promoted to public standalone classes. In > fact, I think I will do it also in order to revamp the boundary > generation algorithm and get rid of the horrific AVLTree and > OrderedTuple classes, using the better algorithm that was created for > the spherical case. > > Don't you think convex hull could simply return a single start Vertex > and that user would simply follow the doubly linked list alternating > vertices and edges to follow the hull? Originally, I was only considering the very simple use case to get the set of points that form the convex hull. I could imagine that the following set of data could be of interest: - ordered set of vertices (with defined winding) - ordered set of line segments (with defined winding) - region formed by the convex hull (I already do this in the unit test to check if the resulting hull is correct) Regarding the Edge/Vertex classes: it looks like they are closely coupled with a BSPTree, so I wonder if they would not be too heavy for a simple doubly-linked list? Thomas --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
