if points_0 == p1 bad access

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Threshold an image from a webcam
2. Apply an OpenCV contours on the image
3. Apply a CDT without holes on the contour output by OpenCV

What is the expected output? What do you see instead?
I can see the triangles until it crashes. No visible reasons. 
On XCode I have an EXC_BAD_ACCESS in shapes.cc

int Triangle::EdgeIndex(const Point* p1, const Point* p2)
{
  if (points_[0] == p1) {
    if (points_[1] == p2) {
      return 2;
    } else if (points_[2] == p2) {
      return 1;
    }
  } else if (points_[1] == p1) {
    if (points_[2] == p2) {
      return 0;
    } else if (points_[0] == p2) {
      return 2;
    }
  } else if (points_[2] == p1) {
    if (points_[0] == p2) {
      return 1;
    } else if (points_[1] == p2) {
      return 0;
    }
  }
  return -1;
}

What version of the product are you using? On what operating system?
Download of November 2011 on OSX (C++)

Please provide any additional information below.
It seems that it crashes when the contours touch the border of the image. 

Original issue reported on code.google.com by lahoz....@gmail.com on 28 Dec 2011 at 3:36

[GoogleCodeExporter]

Any chance you could dump the polygon data in a file of the form
x,y
x,y
.
.
x,y

then add it as an attachment to this thread so I could run a test triangulation 
on the failing points.

Original comment by thahlen@gmail.com on 28 Dec 2011 at 4:26

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Can't help you without some polygon data. But if you have a crash when the 
contours touch the border I guess you get multiple points that are located on a 
straight line.

I am aware of an issue when multiple points is collinear to a line. The 
triangulation might fail in some rare cases and I'm working on solving that. 
Don't know it this has anything to do with your problem.

You could try to just add a tiny random x,y offset to points that are on the 
"border" and see if that help. The offset could be very tiny so it not even 
visible.

Original comment by thahlen@gmail.com on 5 Jan 2012 at 11:10

[GoogleCodeExporter]

Thanks a lot for your answer. 
In fact I implemented the library in a Quartz Composer plugin, so it's hard to 
obtain the coordinates list before it crashes. 
I'll try your "tiny random" way and tell you. 

Original comment by lahoz....@gmail.com on 6 Jan 2012 at 1:23

[GoogleCodeExporter]

I can try to output the reqquested list to the console so I can send you a file.

Original comment by lahoz....@gmail.com on 6 Jan 2012 at 1:25

[GoogleCodeExporter]

Hi, and thank you for your patience. 
Here are finally two diferent file output by my Quartz Composer plugin before 
it crashes (don't know exactly if this is before or while it is crashing, but 
I'm writing to the file before passing the coordinates to the poly2tri 
routine). 
Thanks a lot for your help !

Original comment by lahoz....@gmail.com on 10 Jan 2012 at 5:03

Attachments:

• Coordinates_01.txt
• Coordinates_02.txt

[GoogleCodeExporter]

I found the error in both files.

The thing is that poly2tri require the input to only have one point on a 
specific coordinate. If we are talking polygons this means that the polygon 
can't touch itself.
So your polygon needs to be a simple polygon, eg. no intersecting or touching 
edges/points.

01 contains these duplicates points: [139.000000,20.000000]
02 contains these duplicates points: [251.000000,51.000000]

Maybe you can alter your algorithm a bit so polygons with touching points 
aren't generated.

One thing that we really should have added in a readme is that the lib prefers 
points to be in the range -1,1 for best precision handling. But I don't think 
you will run into that problem with your points.

Original comment by thahlen@gmail.com on 11 Jan 2012 at 12:24

[GoogleCodeExporter]

Thanks !
I'm sure my ploygons are not self-intersecting, but perhaps OpenCV might 
duplicate point on found contours ? 
I'm a bit afraid about comparing each point to the other points of the same 
polygon, for the performance. Do you have any advice ?

Original comment by lahoz....@gmail.com on 11 Jan 2012 at 9:37

[GoogleCodeExporter]

I'm sorry : I checked the OpenCV doc and it might produce self-intersecting 
contours...

Original comment by lahoz....@gmail.com on 11 Jan 2012 at 9:46

[GoogleCodeExporter]

Sorry for flooding... I implemented this code to make it treat my OpenCV 
contours result and it is working very well : 
http://www.gamedev.net/topic/548477-fast-2d-polygon-self-intersect-test/
Thanks again

Original comment by lahoz....@gmail.com on 11 Jan 2012 at 11:48

[GoogleCodeExporter]

Great that you could find a solution :).

At some point I want poly2tri to support self-touching polygons, e.g. polygons 
with holes that touch the outer contour. Hopefully this will happen sooner than 
later.

Original comment by thahlen@gmail.com on 11 Jan 2012 at 12:03

• Changed state: WontFix

[GoogleCodeExporter]

Another simple and fast solution : set the contour flag in OpenCV to 
CV_RETR_EXTERNAL instead of CV_RETR_TREE. That was the problem ! I was not 
treating holes (that I can get from RETR_TREE) na dpassing them as polygons... 
Your lib is very fast and useful. Thanks a lot !

Original comment by lahoz....@gmail.com on 11 Jan 2012 at 12:38