Stack overflow on iPhone

[GoogleCodeExporter]

My polygon attached and also at http://codepad.org/tAMTC5XU

Should look something like http://stuff.brokenbeta.co.uk/brokepolygon.png

poly2tri seems to go down to ~36120 recursion levels then dies. I am using the 
iPhone version which is limited to stack size of 1MB.

Can someone test this and give me any suggestions to reduce stack usage?

Original issue reported on code.google.com by brokenb...@gmail.com on 26 Jan 2012 at 1:23

Attachments:

• polygon.txt

[GoogleCodeExporter]

Sorry hit submit too soon :)

C++ version, got the latest version yesterday.

The stack trace looks like it's flipping between two functions
p2t::Sweep::FlipEdgeEvent
p2t::Sweep::FlipScanEdgeEvent

I'm trying to work out if it is calling the same triangle edges more than once, 
but it's difficult to tell because Xcode and gdb are freaking out over the 
large stack :D

Original comment by brokenb...@gmail.com on 26 Jan 2012 at 1:27

[GoogleCodeExporter]

Hi, I had the same issue yesterday :)
it seems that the polyline passed to the CDT in the c'tor had a duplicate 
point. removing it resolved the infinite recursion for us. 

Original comment by y...@visualtao.com on 1 Feb 2012 at 12:58

[GoogleCodeExporter]

Check issue 34: Your issue may be the same as the one I encountered and has 
been under investigation. You'll find many geometry data samples that cause 
failures in the discussion. (assertions or stack overflows)

The picture you posted looks a bit confusing though. You have what are 
essentially three sets of polygons. Are the purple squares the actual vertices? 

Original comment by stevenlu...@gmail.com on 1 Feb 2012 at 11:51

[GoogleCodeExporter]

No. The black polygon is the main shape, the red polygons are holes. The purple 
squares are points added with AddPoint ("steiner points"?). This was just the 
situation I had which caused the crash, but it went away if you removed 
anything.

the steiner points are needed, btw. Bit difficult to explain why, but we 
actually need 'more' than we have here.

The whole lot comes from the Clipper library, which deals in integers, so 
that's why they're integers.

Anyway this is for a commercial product on a timescale, so I was forced to 
remove poly2tri for being too unstable. I've left it in in a branch though, in 
case anyone has a light bulb moment.

Original comment by brokenb...@gmail.com on 2 Feb 2012 at 7:49

[GoogleCodeExporter]

I get this pointset to work perfectly well with C++, on the first try. See the 
attached screenshot.

You're probably not using the library correctly, or there's an error with the 
Objective-C version.

Original comment by mason.gr...@gmail.com on 4 Feb 2012 at 10:21

Attachments:

• shot.png

[GoogleCodeExporter]

Original comment by mason.gr...@gmail.com on 5 Feb 2012 at 1:42

• Changed state: Invalid

[GoogleCodeExporter]

There isn't an objective-c version, is there? I'm just compiling the c++ 
version in.

Is it possible to find out how many recursion levels the algorithm goes down to 
on your try? Or the highest amount of memory used the stack in the entire run?

I'll try using the same point set outside of my complicated project and see how 
that goes. But I don't see what I can have messed up while still getting 
correct results for simpler polygons.

Original comment by brokenb...@gmail.com on 5 Feb 2012 at 10:48

[GoogleCodeExporter]

I guess one could try using a simple global index counter to see how far down 
the recursion goes, but this is a very simple shape and I don't suspect that it 
will take much computation.

In regard to memory, maybe you could try Valgrind? I don't have much experience 
with that myself. But, as I mentioned, this is a very simple shape and should 
not take much memory at all. The pointset is very small.

Original comment by mason.gr...@gmail.com on 5 Feb 2012 at 7:54