On 01/27/2014 09:13 PM, Thomas Neidhart wrote: > 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?
I have committed an updated version. The ConvexHullGenerator now returns a specific object: ConvexHull which allows to access various properties of the convex hull, similar to an EnclosingBall. I did not yet add your idea with the Vertex and Edge, but this may be interesting too. My attempts to generalize the Hyperplanes (Line in 2D, Triangle in 3D) in the ConvexHull interface failed, so I decided to make a specialized version (ConvexHull2D) for the 2D case, which provides a method: Line[] getLineSegments() whereas in the 3D case there will be another one for the Triangles I guess. It's not perfect, but I would like to hear your opinion on this. Thomas --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
