poly2tri
poly2tri copied to clipboard
greenm01
Stack overflow on 204 point simple polygon input (C++)
What steps will reproduce the problem?
1. Triangulate a particular point set
What is the expected output? What do you see instead?
Stack overflow leading to segfault.
What version of the product are you using? On what operating system?
Most recent code base, Linux 2.6.32-33-generic x86_64. I will test with MinGW
compiled version soon.
Please provide any additional information below.
Included file contains a double array where rand_test[2*i] is poly[i].x and
rand_test[2*i+1] is poly[i].y
I encountered this stack overflow when running a stress test on my convex
decomposition code. I generated a complex polygon by stringing together
entirely random points in the range -2000 to 2000 in both x and y, and used a
custom polygon simplification algorithm to extract the perimeter of the
polygon.
If you examine this test case you will notice that it is a completely valid
polygon without extreme angles anywhere, it just has a few small triangular
features. In any case there should not be a stack overflow here. Here is
relevant part of stack trace:
#93544 0x0000000000427d44 in CDT_testRoutine (data=0x6b3f80,
length=408) at Polygon.cpp:318
318 cdt.Triangulate();
(gdb)
#93543 0x000000000047ff97 in p2t::Sweep::Triangulate(p2t::SweepContext&) ()
(gdb)
#93542 0x000000000047fddc in p2t::Sweep::SweepPoints(p2t::SweepContext&) ()
(gdb)
#93541 0x000000000047f5a9 in p2t::Sweep::EdgeEvent(p2t::SweepContext&,
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&) ()
(gdb)
#93540 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&,
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
()
(gdb)
#93539 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&,
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
()
(gdb)
#93538 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&,
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
()
(gdb)
#93537 0x000000000047f18e in p2t::Sweep::FlipEdgeEvent(p2t::SweepContext&,
p2t::Point&, p2t::Point&, p2t::Triangle*, p2t::Point&)
()
(gdb)
Good luck!
Original issue reported on code.google.com by [email protected] on 19 Dec 2011 at 10:49
Attachments:
Forgot to mention: The two lines I've got commented out are two points that
create a rather thin spike in the geometry. I had hoped that this "extreme"
shape was the cause of the issue but turns out I still get a stack overflow
without it.
If somebody could tell me what sort of features or properties about this input
are bringing about this stack overflow, and what sorts of input I should try to
avoid, that'd be great also. It's got me puzzled because I have inspected the
geometry and there's nothing particularly pathological about it.
Original comment by [email protected] on 20 Dec 2011 at 3:01
I made a quick last-ditch effort which somehow worked: Avoided the stack
overflow by shifting all vertices so that all position values were positive.
This is quite interesting. I'm gonna re run my stress tests, forcing all input
above the axes. Will post back w/ results.
Original comment by [email protected] on 20 Dec 2011 at 3:07
Continued testing, went a bit further, this one's a failed assertion on a 277
vertex shape.
I tried this input shifted +2500.0 on both x and y and that went through
without an error, so it seems like it's not something about the shape itself
that's causing these runs to fail. Please verify these results...
Original comment by [email protected] on 20 Dec 2011 at 3:28
Attachments:
I ran your poly2tri_stackoverflow.c pointset including the two commented points
on the Java version of poly2tri and it worked fine.
I tried to find anything wierd that could cause some precision issues and there
is a case where we got some almost collinear edges when doing the flip part of
the constrained algorithm. See attached image. Maybe doesn't say so much
without some explanation :P
I tried some different values for the epsilon used in utils.h InScanArea test
method.
I did this with the Java version.
It will only fail for me if I use epsilon <= 1e-15 and the default is 1e-12.
You could try 1e-11, but keep 1e-12 for the orient2d test. So create a new
epsilon just for the InScanArea method.
Original comment by [email protected] on 20 Dec 2011 at 6:30
Attachments:
poly2tri_assertion.c also worked fine on the Java version.
Since it works it can't be an algorithmic issue. Must be some precision thing,
but can't understand why it would work with Java but not C++.
Well one thing my debugger code does is to find the bounding box of the
pointset and center the pointset around 0,0 and rescale it to range 0-1. If
that could have any impact.
Original comment by [email protected] on 20 Dec 2011 at 6:45
It does! If I don't recenter and rescale it I will get a Stack Overflow to.
Will look into this closer to try to find what fails.
Original comment by [email protected] on 20 Dec 2011 at 7:10
Try with the second dataset also. It's an assertion failure rather than stack
overflow.
Original comment by [email protected] on 20 Dec 2011 at 6:38
I have analyzed this further and the issue was my initial guess. The thing is
the basic three point orientation test that is used extensively in this lib is
scale dependent. E.g. The value I use for epsilon to check for collinearity
will also be dependent on scale. Thats is why when comparing to 1e-12 works
when the pointset is rescaled but not at original scale. The second one pass
the test. If you change the epsilon for InAreaScan to 1e-11 your pointset
should work with original scale.
I have always been scaling my dataset to the range -1,1 and haven't considered
this until now.
I have to think some more on this.
I cannot reproduce the error in the second dataset, what assertion does it fail
on?
Original comment by [email protected] on 20 Dec 2011 at 11:34
sweep/sweep.cc:715: p2t::Point& p2t::Sweep::NextFlipPoint(p2t::Point&,
p2t::Point&, p2t::Triangle&, p2t::Point&): Assertion `0' failed.
(second dataset)
So you say I should try to limit my domain to -1,1? I'll go give that a spin.
Original comment by [email protected] on 20 Dec 2011 at 11:53
Here's one in the [-1,1] range.
I've got some information on this data-set that may be of help. On line 19 is a
point which is 0.00006 distance from the point on line 17. Removing that
however does not fix the problem on my machine. Once I nuke line 140, though,
no stack overflow. The point on line 140 is 0.00008 from the point on line 138.
Happens to be the 2nd smallest distance between points (I check dist from point
to the one before and the one before that. No adjacent points are ever very
close because I run ramer douglas peucker on my set)
You say epsilon is 1e-11? What would be the size of the smallest feature I can
afford to have?
Original comment by [email protected] on 21 Dec 2011 at 12:24
Sorry forgot attachment.
Points of interest that I mentioned are indented in there.
Original comment by [email protected] on 21 Dec 2011 at 12:25
Attachments:
I got a "spine eliminator".. Here the features are at minimum 0.0001 across at
the root.
I'll just keep sending you failed input data as I encounter them.
Original comment by [email protected] on 21 Dec 2011 at 1:00
Attachments:
Overflow2 was exactly the same issue as before. After putting my thinking cap
on for a while I realized that I could probably improve the precision a bit by
just reordering the way I do the InAreaScan test.
Updating the Java version solved the problem.
Below is the new InAreaScan in utils.h.
Please try it and let me know how it works.
bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd)
{
double oadb = (pa.x - pb.x)*(pd.y - pb.y) - (pd.x - pb.x)*(pa.y - pb.y);
if (oadb >= EPSILON) {
return false;
}
double oadc = (pa.x - pc.x)*(pd.y - pc.y) - (pd.x - pc.x)*(pa.y - pc.y);
if (oadc <= EPSILON) {
return false;
}
return true;
}
Original comment by [email protected] on 21 Dec 2011 at 5:48
Alright, I can confirm my previously failing cases that I presented are now
working with that replacement code. Thanks!
I'll come back if I run into any more similar issues. I've found a rather
frustrating issue with my own segment-segment intersecting code... here follow
the link if you're interested.
http://stackoverflow.com/questions/8585427/precision-issues-with-segment-segment
-intersection-code
thanks again.
Original comment by [email protected] on 21 Dec 2011 at 6:16
Damn. That didn't take long.
See if this one asserts for you. Did for me.
Original comment by [email protected] on 21 Dec 2011 at 6:22
Attachments:
In this lib points need to be separated by atleast Epsilon, e.g 1e-12.
There hasn't been any floating point analysis done on the lib. It's precision
has been enough for anything I have needed it for to date. I started to look
into triangulation when I needed to triangulate some 2d fonts, which are pretty
simple polygons :)
I picked epsilon 1e-12 after running some polygon generation code that
generated some nasty polygons. Did a circle sweep polygon with some function
for altering the radius. After increasing the points to around 500k something.
I found that epsilon 1e-13 was where the algorithm broke down in precision when
using so many points so to be safe I felt that 1e-12 would be enough precision
for almost any triangulation needs :)
Original comment by [email protected] on 21 Dec 2011 at 6:23
I see. I did notice the debug geometry you have which is circular and very
spikey. But my method of generating test geometry is a bit more involved and
produces more random angles and stuff.
Original comment by [email protected] on 21 Dec 2011 at 6:26
Hehe.. keep em comming. Anything that can improve the lib is nice :)
The last dump is wierd. On the first triangulation it works but if I run it a
second time with same set I get the assert error to.
Looking into that.
Original comment by [email protected] on 21 Dec 2011 at 6:40
The last dump works fine with the old InScanArea method :(.
I'll get to the depth with this later. Guess it might be trickier than I
expected.
Original comment by [email protected] on 21 Dec 2011 at 6:47
Yeah, I'm generating a few more cases so you have enough of them to play with.
Soon enough I'll have the entire thing automated...
Original comment by [email protected] on 21 Dec 2011 at 6:51
Attachments:
I did something silly and some of those datasets may run fine. In that case
don't worry about it. But most of them either asserted or overflowed on me.
I'll be working on coming up with some different shapes now.
Original comment by [email protected] on 21 Dec 2011 at 7:37
I did something silly with the new InAreaScan to
if (oadb >= EPSILON) {
return false;
}
should be
if (oadb >= -EPSILON) {
return false;
}
The original old issues didn't get fixed by the new InScanArea. I might have to
tweak the algorithm a bit to fix this.
Original comment by [email protected] on 21 Dec 2011 at 8:17
Alright, now here's something interesting.
I made a random walk test, which is a 2D random walk. I have a vector that i
incrementally walk forwards and turn slightly each vertex. Then I add a noisy
random vector to that (which does not affect the walked vector itself). First I
set the noise vector small, so it always walks farther than the noise.
This passed all 5000 test cases I threw at it. I'm gonna run that one in a loop
overnight.
So then i modified it so the random factor got increased a bunch, so now I'm
still walking my location around but each vertex sent has a ton of noise. Then
with my perimeter algorithm I get a jaggy convex simple polygon out of that
mess. It basically looks like my squares and circles from before, same
jaggedyness but now theyre all amoeba-like too.
These jaggy mofo's assert and overflow like crazy. I'm fairly certain I did
these files right so you best check these ones out.
Original comment by [email protected] on 21 Dec 2011 at 8:19
Attachments:
- dump157.dat
- dump438.dat
- dump495.dat
- dump591.dat
- dump627.dat
- dump675.dat
- dump720.dat
- dump737.dat
- dump805.dat
I would say the issue only crops up with protruding triangular bits. I might
design some tests that produce protruding mini-quadrilaterals and pentagons to
see if that affects it.
But smooth-ish shapes, even with large numbers of vertices, are handled just
fine.
Original comment by [email protected] on 21 Dec 2011 at 8:22
I ran non-jaggy randomwalk shapes overnight, it performed 55 loops of 5000
tests, what I do is I make a 3 vertex shape and send it through my polygonator
routine, then a 4 vertex shape, then 5, ... up to 5000, then I restart with a
new random seed from 3. This went 55 times so that's a total of 687 million
vertices processed. I had a memory leak which is why it stopped.
Original comment by [email protected] on 21 Dec 2011 at 10:59