commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <...@spaceroots.org>
Subject Re: [math][MATH-749] Convex hull
Date Sat, 01 Feb 2014 10:27:58 GMT
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-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


Mime
View raw message