Le 30/01/2014 23:23, Thomas Neidhart a écrit : > 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.
I thinks it is good as is (except for spurious @Override annotations). I wonder if it would be interesting to make sure computations are highly accurate (this is often a problem in computational geometry, wich nearly aligned or nearly orthogonal vectors). In some cases, I have used MathArrays.linearComputation to improve accuracy in degenerate cases. It may take more time, but up to now I did not experience any bad performance drop (and I did get accuracy improvements). best regards, Luc > > Thomas > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org > For additional commands, e-mail: dev-h...@commons.apache.org > > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
