FindHull Integer overrun
Opened this issue · 2 comments
GoogleCodeExporter commented
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 commented
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 commented
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