commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [Math] Allow empty "ConvexHull2D"
Date Mon, 01 Jun 2015 19:36:14 GMT
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.

Thomas

> 
>>
>> So, I note that "generate" did not raise an exception whereas the
>> computation
>> request could be deemed invalid.  Then "createRegion" raises an
>> exception...
>> Something looks wrong here: if the "hull" instance is valid (from a
>> programming
>> perspective), then "hullRegion" should be valid too (i.e. "empty").
>>
>> Assuming that you don't want to change the existing code, how can I
>> create an
>> empty region?  Is there a singleton instance to represent the concept?
> 
> There are no singleton for empty space or full space as regions are
> always associated
> with other meta-data like tolerance, which are often problem-specific.
> 
> You can build one as follows:
> 
>   Region empty = new PolygonsSet(new BSPTree<Euclidean2D>(false),
> tolerance);
> 
> Tolerance is mainly a distance in the space (here the 2D Euclidean
> plane), and
> points this close to a line will be consider to belong to the line.
> 
> best regards,
> Luc
> 
>>
>> Thanks,
>> Gilles
>>
>>>
>>> best regards
>>> Luc
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
>> For additional commands, e-mail: user-help@commons.apache.org
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
> 


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


Mime
View raw message