[Math] Allow empty "ConvexHull2D"

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

[Math] Allow empty "ConvexHull2D"

Gilles Sadowski
Hi.

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).


Regards,
Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

RE: [Math] Allow empty "ConvexHull2D"

Shriver, Daniel
Personally, I'd think having an exception is "better" in this case.
1) the computation is fundamentally invalid, an exception conveys this well (the same thing is used with other invalid computations like division by zero)
2) an empty region could be a valid result of some valid operation (unless you are suggesting creating some "invalid region" that just conveys the same info- that an exception occurred) this effectively masks the fact that an invalid operation occurred

A programmer can and should catch exceptions from invalid computations.  They should be able to decide if they want to "ignore" the problem (such as create something like an empty region) and continue on, or if they want to follow some other path (halting work, logging a problem,...).  If you return some valid "empty region" you would mask the exception (or if it is only for invalid computations you'd be simply recreating it as something other than an exception).

-----Original Message-----
From: Gilles [mailto:[hidden email]]
Sent: Monday, June 01, 2015 8:38 AM
To: [hidden email]
Subject: [Math] Allow empty "ConvexHull2D"

Hi.

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).


Regards,
Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Luc Maisonobe-2
In reply to this post by Gilles Sadowski
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.

best regards
Luc

>
>
> Regards,
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
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();

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?

Thanks,
Gilles

>
> best regards
> Luc


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Luc Maisonobe-2
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.

>
> 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: [hidden email]
> For additional commands, e-mail: [hidden email]

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Thomas Neidhart
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: [hidden email]
>> For additional commands, e-mail: [hidden email]
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
In reply to this post by Luc Maisonobe-2
On Mon, 01 Jun 2015 15:52:11 +0200, 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.
>
>> 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.

I surely miss basic understanding of the classes involved here, as
I worked my way from the needed functionality (hull, constructive
geometry)
and gradually importing more classes as required by the methods'
arguments
and return values.
Now, as I showed in the code excerpt, I think that one shouldn't need
to
know/use any of PolygonsSet, BSPTree, and the associated "tolerance"
(no
idea what value I should set there); from my (biased) POV, the methods
in
"RegionFactory" should handle an "empty region" in the obvious way:
e.g.
   AssertTrue(a, RegionFactory.union(a, empty))
should pass.
Is there more than one way to be "empty"?

Regards,
Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

RE: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
In reply to this post by Shriver, Daniel
On Mon, 1 Jun 2015 12:56:53 +0000, Shriver, Daniel wrote:
> Personally, I'd think having an exception is "better" in this case.
> 1) the computation is fundamentally invalid, an exception conveys
> this well (the same thing is used with other invalid computations
> like
> division by zero)

When points are gradually removed from a set, the hull of the set
gradually shrinks until it becomes a line. IIUC that line would be
equivalent to an empty region (in 2D space).
Hence, I think that returning an empty region is more logical than
raising an exception.

> 2) an empty region could be a valid result of some valid operation
> (unless you are suggesting creating some "invalid region" that just
> conveys the same info- that an exception occurred) this effectively
> masks the fact that an invalid operation occurred

I don't propose such an "invalid region".
An "empty region" is a valid region.

> A programmer can and should catch exceptions from invalid
> computations.  They should be able to decide if they want to "ignore"
> the problem (such as create something like an empty region) and
> continue on, or if they want to follow some other path (halting work,
> logging a problem,...).  If you return some valid "empty region" you
> would mask the exception (or if it is only for invalid computations
> you'd be simply recreating it as something other than an exception).

Cf. above.  I see it the other way around (any set operation is
meaningful even when applied to an empty set), there is no need
to consider it invalid: if the *caller* does not expect an "empty"
result, he should check and act (i.e. raise an exception).

In my use-case, the shape shrinks, then disappears, than reappears
and grows again, in a "continuous" way; nothing "exceptional" occurs.
If I want apply some geometrical operation to the region that encloses
the shape why should the code handle differently empty and non-empty
regions?


Gilles

> -----Original Message-----
> From: Gilles [mailto:[hidden email]]
> Sent: Monday, June 01, 2015 8:38 AM
> To: [hidden email]
> Subject: [Math] Allow empty "ConvexHull2D"
>
> Hi.
>
> 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).
>
>
> Regards,
> Gilles



---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Thomas Neidhart
In reply to this post by Thomas Neidhart
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?

Or should we add an additional method: isValidRegion() to check if the
given convex hull can form a valid region?

Thomas


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Thomas Neidhart
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

RE: [Math] Allow empty "ConvexHull2D"

Andy Turner
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:[hidden email]]
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: [hidden email]
For additional commands, e-mail: [hidden email]


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]
Reply | Threaded
Open this post in threaded view
|

RE: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
On Wed, 10 Jun 2015 11:30:35 +0100, Andy Turner wrote:
> 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.)

Excerpt:
---CUT---
8.2.2 Empty Geometry
The SFS specifies that objects of each Geometry subclass may be empty.
It is sometimes
necessary to construct an generic empty object of class Geometry (e.g.
if the exact type of
the Geometry to be returned is not known). The SFS does not define an
specific class or
object to represent this generic empty Geometry. JTS uses the
convention that an empty
GeometryCollection will be returned.
---CUT---

Gilles


> Andy
> http://www.geog.leeds.ac.uk/people/a.turner/index.html
>
>
> -----Original Message-----
> From: Thomas Neidhart [mailto:[hidden email]]
> 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: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
In reply to this post by Thomas Neidhart
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"...


Gilles


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Thomas Neidhart
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.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Gilles Sadowski
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: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [Math] Allow empty "ConvexHull2D"

Luc Maisonobe-2
Le 10/06/2015 15:16, Gilles a écrit :

> 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.]

Trying to catch the discussion, sorry to be late ...

The Region is really intended to allow both empty and full-space
regions. This allows for example operations like intersection or union
to always return a Region, even if it is degenerate. It is also possible
to have infinite but not full-spece regions (say for example a half
plane in 2D or an infinite strip).

Concerning the factory method (or static constants EMPTY or FULL_SPACE)
I don't like this. The problem is that many operations that combines
Regions in consructive geometry will inherit the tolerance setting from
one of the input regions. As it a classical way to build up a region is
to start from either empty or full and then perform operations in a loop
(adding parts with union or removing parts with intersection or
difference), this would mean we would inherit a default value that may
not be meaningful for the problem. The tolerance is really an important
parameter and it is really problem dependent. If you are dealing with
regions to model a stellar-system size object (say the Heliopause for
example) you will not use the same threshold that if you are modelling
devices in nano-technology. Many of the bugs that were raised in BSP
tree are related to tolerance settings. These tolerance settings were
hard-coded values at the beginning and I had to change it to make them
explicit and user-configurable in January 2014. The constructors without
tolerance were removed with commit dfc2324.

So if a factory method is desired, at least it should specify the tolerance.

best regards,
Luc

>
> Gilles
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]