You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Thomas Neidhart <th...@gmail.com> on 2014/01/26 23:52:00 UTC
[math][MATH-749] Convex hull
Hi,
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).
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>>
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.
Anyway, I would be grateful if somebody could review the patch. If the
general interface is accepted, I plan to add more implementations.
Thanks,
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math][MATH-749] Convex hull
Posted by Gilles <gi...@harfang.homelinux.org>.
> [...]
>
> 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.
>
> [...]
>
>
> 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.
>
> [...]
How would an algorithm know how to deal with the returned value
if it does not know the actual type (i.e. the meaning of the
components)?
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math][MATH-749] Convex hull
Posted by Thomas Neidhart <th...@gmail.com>.
On 02/01/2014 11:27 AM, Luc Maisonobe wrote:
> 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).
Hi Luc,
thanks for looking at it.
I did incorporate your feedback, and added a new method to Vector2D:
crossProduct(Vector2D p1, Vector2D p2)
which computes the cross product of the three points p1, p2, p3 (with p3
being the point itself). The method uses MathArrays.linearCombination to
compute its result.
Furthermore I did fix the @Override issues: in my eclipse environment
java 1.6 was enabled as compiler level.
The ConvexHull2D class has been slightly changed. Now you get Segment
objects instead of Line objects, as it is more convenient for a user imho.
I am still unsure whether the Segments shall be created in the
constructor or only on demand, but this is more an implementation detail.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math][MATH-749] Convex hull
Posted by Luc Maisonobe <lu...@spaceroots.org>.
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
Re: [math][MATH-749] Convex hull
Posted by Thomas Neidhart <th...@gmail.com>.
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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math][MATH-749] Convex hull
Posted by Thomas Neidhart <th...@gmail.com>.
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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math][MATH-749] Convex hull
Posted by Luc Maisonobe <lu...@spaceroots.org>.
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.
>
> 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.
>
> 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.
>
> 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.
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?
best regards,
Luc
>
> Thanks,
>
> 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