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 Wed, 10 Jun 2015 13:16:29 GMT
On Wed, 10 Jun 2015 14:45:41 +0200, Thomas Neidhart wrote:
> On 06/10/2015 01:44 PM, Gilles wrote:
>> On Wed, 10 Jun 2015 12:23:58 +0200, Thomas Neidhart wrote:
>>> 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.
>>
>> I've given a reasonable (IMHO) practical use-case (in an earlier 
>> post).
>>
>> Another, comparable, situation would be empty collections: it would 
>> not
>> occur to anyone that an exception must be thrown because one would 
>> want to
>> loop over all elements of an empty list.
>>
>> And finally, there is an "isEmpty()" method in the "Region" 
>> interface.
>> If an empty region cannot exist, wouldn't it mean that the method 
>> should
>> always return "false"?  Yet Luc's suggestion creates a Region for 
>> which
>> "isEmpty" returns "true"...
>
> I did not think about returning an empty Region in the case of 1 or 2
> hull points before.
>
> Tests for regions with 1 or 2 points, see results above to which no 
> one
> responded, resulted in exceptions or unexpected behavior, that's the
> reason that I made this check to require at least 3 points.
>
> I guess returning an empty Region in such cases is reasonable, so it
> was the intention of my postings to get feedback and not to disregard
> the proposal.

I had provided feedback, in another post that was a reply to a 
(sort-of)
"fork" of the thread (where someone gave an argument in favour of 
raising
an exception).  Nobody answered there... :-}
I could not discuss "technical" details (referring to the result of 
tests
above). Thus I was waiting for someone to raise the practical 
limitations
that would forbid the concept of "empty region"... [Luc mentioned 
precision
and problem-specific tolerances.]

Gilles



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


Mime
View raw message