commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Andy Turner <A.G.D.Tur...@leeds.ac.uk>
Subject RE: [Math] Allow empty "ConvexHull2D"
Date Wed, 10 Jun 2015 10:30:35 GMT
Perhaps it is worth investigating how JTS operates in this respect:
http://www.vividsolutions.com/jts/JTSHome.htm

(I have not looked, but I assume that JTS has a similar operation/test case.)

Andy
http://www.geog.leeds.ac.uk/people/a.turner/index.html
 

-----Original Message-----
From: Thomas Neidhart [mailto:thomas.neidhart@gmail.com] 
Sent: 10 June 2015 11:24
To: Commons Users List
Subject: Re: [Math] Allow empty "ConvexHull2D"

On 06/09/2015 11:42 PM, Gilles wrote:
> On Tue, 09 Jun 2015 23:19:35 +0200, Thomas Neidhart wrote:
>> On 06/01/2015 09:36 PM, Thomas Neidhart wrote:
>>> On 06/01/2015 03:52 PM, luc wrote:
>>>> Le 2015-06-01 15:27, Gilles a écrit :
>>>>> Hello.
>>>>>
>>>>> On Mon, 01 Jun 2015 15:03:47 +0200, luc wrote:
>>>>>> Le 2015-06-01 14:38, Gilles a écrit :
>>>>>>> Hi.
>>>>>>
>>>>>> Hi Gilles,
>>>>>>> I have a question regarding
>>>>>>> public Region<Euclidean2D> createRegion() throws 
>>>>>>> InsufficientDataException in ConvexHull2D.
>>>>>>> It throws the exception when the number of points is < 3.
>>>>>>> One can imagine that rather than aborting it could return an

>>>>>>> "empty Region"
>>>>>>> (which would seamlessly work with further operations on the Region).
>>>>>>> What do you think?
>>>>>>> Context: in the course of a program, a "valid" region can 
>>>>>>> undergo successive transformation until it is indeed impossible

>>>>>>> to compute the hull; it seems that it would be interesting to

>>>>>>> not treat that as a hard-failure (warranting an exception).
>>>>>>
>>>>>> I'm on the fence on this. The exception is advertised right at 
>>>>>> the the top interface level (ConvexHull in o.a.c.m.geometry.hull

>>>>>> package) and clearly intended to cover this case. An empty region

>>>>>> could be expected from computing the hull of n >= 3 aligned 
>>>>>> points, but n < 3 points is something different to me.
>>>>>
>>>>> This is how I get the "Region" in my program:
>>>>>
>>>>>    final ConvexHullGenerator2D hullGen = new MonotoneChain(false);
>>>>>    final ConvexHull2D hull = hullGen.generate(data);
>>>>>    final Region<Euclidean2D> hullRegion = hull.createRegion();
>>>>
>>>> Looking at AbstractConvexHullGenerator2D and ConvexHull2D, they 
>>>> indeed seem inconsistent with respect to the number of points.
>>>>
>>>> In AbstractConvexHullGenerator2D.generate, you can have 
>>>> points.size() < 2, there is a special handling. In ConvexHull2D you 
>>>> cannot have vertices.length < 3.
>>>>
>>>> I think this is a problem.
>>>
>>> My understanding was that creating a 2D region with less than 3 
>>> points does not give a meaningful result, but this assumption may be wrong.
>>>
>>> I did recall doing some tests with less than 3 points and got weird 
>>> results, see the test case below:
>>>
>>>   final RegionFactory<Euclidean2D> factory = new 
>>> RegionFactory<Euclidean2D>();
>>>
>>>   Vector2D p1 = new Vector2D(0, 0);
>>>   Vector2D p2 = new Vector2D(1, 0);
>>>   Vector2D p3 = new Vector2D(1, 1);
>>>   Vector2D p4 = new Vector2D(0.8, 0.8);
>>>
>>>   final Line[] lineArray = new Line[1];
>>>   lineArray[0] = new Line(p1, p2, 1e-6);
>>>
>>>   Region<Euclidean2D> reg = factory.buildConvex(lineArray);
>>>   System.out.println(reg.getSize());
>>>   System.out.println(reg.checkPoint(p3));
>>>   System.out.println(reg.checkPoint(p4));
>>>
>>> I get different results for 3.3 and 4.0:
>>>
>>> In 3.3, the results are:
>>>
>>>  Infinity
>>>  INSIDE
>>>  INSIDE
>>>
>>> In 4.0:
>>>
>>>  IndexOutOfBoundsException
>>>  INSIDE
>>>  INSIDE
>>>
>>> Doing the same test with 2 line segments (p1 -> p2 and p2 -> p3) 
>>> leads to a NullPointerException when calling getSize().
>>>
>>> So, I tried to be conservative when creating the region, and this is 
>>> also expressed in the javadoc, although I admit there is no method 
>>> to return the minimum number of hull points that need to be present 
>>> in order to create a region.
>>>
>>> I am really wondering if a 2D region consisting of less than 3 
>>> points does make sense, and if so, what is the correct way to 
>>> construct such a region and what are the expected properties?
>>>
>>> If this is clarified, I am fine to update the ConvexHull2D class to 
>>> handle these cases too.
>>
>> There was no further response to my posting, but I am curious how to 
>> proceed with this topic.
>>
>> Is it reasonable to return an empty region if the number of hull 
>> vertices is below 3?
> 
> In the code excerpt I had given (cf. above), I now use
> 
>   final Region<Euclidean2D> hullRegion = data.size() < 3 ?
>     EMPTY_REGION :
>     hull.createRegion();
> 
> where EMPTY_REGION is defined as suggested by Luc:
> 
>   new PolygonsSet(new BSPTree<Euclidean2D>(false), 0d);
> 
> Hence my question in the other post about a factory method that would 
> create such a region.
> 
> It seems logical to me that if no hull exists, the region it covers is 
> "empty", and can be used as such through the "Region" interface 
> without any problem; hence raising an exception hinders functionality 
> and code flow.
> 
>> Or should we add an additional method: isValidRegion() to check if 
>> the given convex hull can form a valid region?
> 
> What is a valid/invalid region?
> [Cf. other post.]

according to
http://en.wikipedia.org/wiki/Region_%28mathematical_analysis%29 a region must be non-empty,
but I am not sure if the Region interface is intended to follow this convention, that's why
I am asking.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org

Mime
View raw message