commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gilles <gil...@harfang.homelinux.org>
Subject Re: [Math] Allow empty "ConvexHull2D"
Date Tue, 09 Jun 2015 21:42:39 GMT
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.]

Gilles


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


Mime
View raw message