RotatedRect fails to calculate correct intersections due to precision

[NCBee]

System information (version)

• OpenCV => master
• Operating System / Platform => Linux 64 Bit
• Compiler => gcc

Detailed description

OpenCV RotatedRect intersection calculation currently uses float for intermediate variables. In some edge cases, the limited precision causes assertion problems inside intersection code:

   CV_Assert( intersection.size() <= 8 );

The problem can be mitigated by doing all calculations in double precision as shown below:

      float A = -vec2[j].y;
      float B = vec2[j].x;
      float C = -(A * pts2[j].x + B * pts2[j].y);

      float s = A * x + B * y + C;

//Using float: xx = -1990.670654, yy = 1636.783203,A = 200.753662, B = -121.916260, C = 599184.937500, x = -2071.253906, y = 1504.090820, s = 0.000000

      double A = -vec2[j].y;
      double B = vec2[j].x;
      double C = -(A * pts2[j].x + B * pts2[j].y);

      double s = A * x + B * y + C;

//Using double: xx = -1990.670654, yy = 1636.783203,A = 200.753662, B = -121.916260, C = 599184.910076, x = -2071.253906, y = 1504.090820, s = -0.023922

Steps to reproduce

See above example.

[NCBee]

Also check http://answers.opencv.org/question/74697/cvrotatedrectangleintersection-assertion-failed/

[alalek]

Precision switch is just a workaround. It usually just hides real problem more deeper.

Please create minimal reproducer for this problem. Dump "failed" inputs and write simple code, like this one)

Update: Thanks! I missed your PR with tests.

[dkurt]

Does samePointEps increasing can help?

opencv/modules/imgproc/src/intersection.cpp

Lines 254 to 255 in 94758c1

	// If this check fails then it means we're getting dupes, increase samePointEps
	CV_Assert( intersection.size() <= 8 );

opencv/modules/imgproc/src/intersection.cpp

Lines 231 to 239 in 94758c1

	double d2 = dx*dx + dy*dy; // can be a really small number, need double here
	if( d2 < samePointEps*samePointEps )
	{
	// Found a dupe, remove it
	std::swap(intersection[j], intersection.back());
	intersection.pop_back();
	j--; // restart check
	}

[NCBee]

@dkurt I don’t think so. When using float, some calculations result in 0.0f, which no matter how you set the epsilon value it’s still less than that.

I have already submitted a PR that has two unit tests showing the numbers that cause the algorithm to fail when using floats.