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 MATH749.
>>>> 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
>> usecase of a BSP.
>>
>> Something that I would like to see in 4.0: make the Vector interface
>> very lightweight, 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 usecase 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 suboptimal, 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 doublylinked 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, email: devunsubscribe@commons.apache.org
> For additional commands, email: devhelp@commons.apache.org
>
>
>

To unsubscribe, email: devunsubscribe@commons.apache.org
For additional commands, email: devhelp@commons.apache.org
