FindHull Integer overrun

[GoogleCodeExporter]

What steps will reproduce the problem?
1. pass list (Int32) to FindHull with values slightly less than 2E9
2.
3.

What is the expected output? What do you see instead?

expected: Convex Hull line points (polygon). 

instead sometimes: nothing returned, call results in exception; However Call to 
FindHull (C# VS2013) works as expected If list value magnitudes are reduced a 
bit; Success with:  ~< 1/2 Int32.MaxValue... perhaps more depending upon data. 
Results are varied (not consistent). 


What version of the product are you using?

AForge.Math.dll is reported @ 2.2.5.0  
please email me @:  ASC@GoMeasure.com   if u desire me to dig up more  detail. 


Please provide any additional information below.

FindHull is being called from a full VS2013 Pro in C# Windows (desktop) 
project. 
We desire ConvexHull from double decimal data, so we "scale" the decimal data 
to integers for needed res to FindHull. 
Sometimes FindHull works, sometimes not (with ~exact same in data set.. perhaps 
slight roundoff diffs).
This is observed while in IDE or exe. 

I can likely use present FindHull IF I know what the variance is with its 
Int32. 
Thank you in advance for reply. Bests! rjf. 

Original issue reported on code.google.com by SStokes9...@gmail.com on 2 Oct 2014 at 2:12

[GoogleCodeExporter]

It would be nice if you provide sample list, which reproduces the issue (you 
can attach it as a code file). "slightly less than 2E9" is a bit vague. Also 
you don't tell anything about the number of points.

Original comment by andrew.k...@gmail.com on 2 Oct 2014 at 7:06

[GoogleCodeExporter]

1) Provide list with 4 or more x,y list points where all values are 2E9 - 1. 

2) Try: 2,000,000,000. - 1. 
Given that, we've found issues with values much more reduced... 
We're not presently dedicated to this issue-- just trying to help you. 
We've found success & failures with values @ (.5 * Int32.MaxValue). 
We're in the field running real field data and not purposed @ debugging your 
code. 

3) The number of points is ~believed not critical, but obviously you need to 
get into the process... ie, >3. 
-------

Somewhat irritated by the tongue lash, 
spending a few hours after our immediate above, 
we believe we've found the problem: 

1) 
Within AForge's 2.2.5.0 AForge.Math.DLL @ method "public List<IntPoint> 
FindHull(List<IntPoint> points)", the following source line appears to be the 
issue: 
"if ((newPoint.X - prevPoint.X) * (lastPoint.Y - newPoint.Y) - (lastPoint.X - 
newPoint.X) * (newPoint.Y - prevPoint.Y) < 0)". 

2)This line, when loaded as previously described (ie, large Int32 magnitudes), 
May throw exception: 
 "...'System.ArgumentOutOfRangeException' occurred in MSCORLIB.DLL". 

3) Further investigation shows possibility of ~ (8 * Int32.MaxValue^2). 

4) Solution, we ~think:  Change the subject line so as to process LONG values; 
ex:

//-------------------------------------------------
                // check if current point is on the left side from two last points

                //test:
                long sub1 = newPoint.X - prevPoint.X;
                long sub2 = lastPoint.Y - newPoint.Y;
                long sub3 = lastPoint.X - newPoint.X;
                long sub4 = newPoint.Y - prevPoint.Y;
                long mult1 = sub1 * sub2;
                long mult2 = sub3 * sub4;
                long diff = mult1 - mult2;
                if (diff < 0)
                    //if ((newPoint.X - prevPoint.X) * (lastPoint.Y - newPoint.Y) - (lastPoint.X - newPoint.X) * (newPoint.Y - prevPoint.Y) < 0)
                    {
                        // add the point to the hull
                        convexHullTemp.Add(newPoint);
                        // and remove it from the list of points to process
                        pointsToProcess.RemoveAt(0);

                        prevPoint = lastPoint;
                        lastPoint = newPoint;
                    }
                    else
                    {
                        // remove the last point from the hull
                        convexHullTemp.RemoveAt(convexHullTemp.Count - 1);

                        lastPoint = prevPoint;
                        prevPoint = convexHullTemp[convexHullTemp.Count - 2];
                    }
//-------------------------------------------------

That's our 2cents, Vaguely. 
:-)

If you desire converse, please eme directly at "ASC@GoMeasure.com" .
We're working in the gulf & google connect not regularly available. 
Bests, RJF. 

Original comment by SStokes9...@gmail.com on 2 Oct 2014 at 9:18