Skip to content

Commit ff190b1

Browse files
vpisarevvpisarev
committed
Merge pull request opencv#9802 from Nickolays:Fix#9797
2 parents 1a495a5 + b2b56b6 commit ff190b1

File tree

2 files changed

+120
-110
lines changed

2 files changed

+120
-110
lines changed

‎modules/imgproc/src/shapedescr.cpp

Lines changed: 63 additions & 110 deletions
Original file line numberDiff line numberDiff line change
@@ -42,84 +42,29 @@
4242
namespace cv
4343
{
4444

45-
// inner product
46-
static float innerProduct(Point2f &v1, Point2f &v2)
47-
{
48-
return v1.x * v2.y - v1.y * v2.x;
49-
}
45+
const float EPS = 1.0e-4f;
5046

5147
static void findCircle3pts(Point2f *pts, Point2f &center, float &radius)
5248
{
5349
// two edges of the triangle v1, v2
5450
Point2f v1 = pts[1] - pts[0];
5551
Point2f v2 = pts[2] - pts[0];
5652

57-
if (innerProduct(v1, v2) == 0.0f)
58-
{
59-
// v1, v2 colineation, can not determine a unique circle
60-
// find the longtest distance as diameter line
61-
float d1 = (float)norm(pts[0] - pts[1]);
62-
float d2 = (float)norm(pts[0] - pts[2]);
63-
float d3 = (float)norm(pts[1] - pts[2]);
64-
if (d1 >= d2 && d1 >= d3)
65-
{
66-
center = (pts[0] + pts[1]) / 2.0f;
67-
radius = (d1 / 2.0f);
68-
}
69-
else if (d2 >= d1 && d2 >= d3)
70-
{
71-
center = (pts[0] + pts[2]) / 2.0f;
72-
radius = (d2 / 2.0f);
73-
}
74-
else if (d3 >= d1 && d3 >= d2)
75-
{
76-
center = (pts[1] + pts[2]) / 2.0f;
77-
radius = (d3 / 2.0f);
78-
}
79-
}
80-
else
81-
{
82-
// center is intersection of midperpendicular lines of the two edges v1, v2
83-
// a1*x + b1*y = c1 where a1 = v1.x, b1 = v1.y
84-
// a2*x + b2*y = c2 where a2 = v2.x, b2 = v2.y
85-
Point2f midPoint1 = (pts[0] + pts[1]) / 2.0f;
86-
float c1 = midPoint1.x * v1.x + midPoint1.y * v1.y;
87-
Point2f midPoint2 = (pts[0] + pts[2]) / 2.0f;
88-
float c2 = midPoint2.x * v2.x + midPoint2.y * v2.y;
89-
float det = v1.x * v2.y - v1.y * v2.x;
90-
float cx = (c1 * v2.y - c2 * v1.y) / det;
91-
float cy = (v1.x * c2 - v2.x * c1) / det;
92-
center.x = (float)cx;
93-
center.y = (float)cy;
94-
cx -= pts[0].x;
95-
cy -= pts[0].y;
96-
radius = (float)(std::sqrt(cx *cx + cy * cy));
97-
}
98-
}
99-
100-
const float EPS = 1.0e-4f;
101-
102-
static void findEnclosingCircle3pts_orLess_32f(Point2f *pts, int count, Point2f &center, float &radius)
103-
{
104-
switch (count)
105-
{
106-
case 1:
107-
center = pts[0];
108-
radius = 0.0f;
109-
break;
110-
case 2:
111-
center.x = (pts[0].x + pts[1].x) / 2.0f;
112-
center.y = (pts[0].y + pts[1].y) / 2.0f;
113-
radius = (float)(norm(pts[0] - pts[1]) / 2.0);
114-
break;
115-
case 3:
116-
findCircle3pts(pts, center, radius);
117-
break;
118-
default:
119-
break;
120-
}
121-
122-
radius += EPS;
53+
// center is intersection of midperpendicular lines of the two edges v1, v2
54+
// a1*x + b1*y = c1 where a1 = v1.x, b1 = v1.y
55+
// a2*x + b2*y = c2 where a2 = v2.x, b2 = v2.y
56+
Point2f midPoint1 = (pts[0] + pts[1]) / 2.0f;
57+
float c1 = midPoint1.x * v1.x + midPoint1.y * v1.y;
58+
Point2f midPoint2 = (pts[0] + pts[2]) / 2.0f;
59+
float c2 = midPoint2.x * v2.x + midPoint2.y * v2.y;
60+
float det = v1.x * v2.y - v1.y * v2.x;
61+
float cx = (c1 * v2.y - c2 * v1.y) / det;
62+
float cy = (v1.x * c2 - v2.x * c1) / det;
63+
center.x = (float)cx;
64+
center.y = (float)cy;
65+
cx -= pts[0].x;
66+
cy -= pts[0].y;
67+
radius = (float)(std::sqrt(cx *cx + cy * cy)) + EPS;
12368
}
12469

12570
template<typename PT>
@@ -145,7 +90,7 @@ static void findThirdPoint(const PT *pts, int i, int j, Point2f &center, float &
14590
ptsf[0] = (Point2f)pts[i];
14691
ptsf[1] = (Point2f)pts[j];
14792
ptsf[2] = (Point2f)pts[k];
148-
findEnclosingCircle3pts_orLess_32f(ptsf, 3, center, radius);
93+
findCircle3pts(ptsf, center, radius);
14994
}
15095
}
15196
}
@@ -210,8 +155,6 @@ void cv::minEnclosingCircle( InputArray _points, Point2f& _center, float& _radiu
210155
Mat points = _points.getMat();
211156
int count = points.checkVector(2);
212157
int depth = points.depth();
213-
Point2f center;
214-
float radius = 0.f;
215158
CV_Assert(count >= 0 && (depth == CV_32F || depth == CV_32S));
216159

217160
_center.x = _center.y = 0.f;
@@ -224,52 +167,62 @@ void cv::minEnclosingCircle( InputArray _points, Point2f& _center, float& _radiu
224167
const Point* ptsi = points.ptr<Point>();
225168
const Point2f* ptsf = points.ptr<Point2f>();
226169

227-
// point count <= 3
228-
if (count <= 3)
170+
switch (count)
229171
{
230-
Point2f ptsf3[3];
231-
for (int i = 0; i < count; ++i)
172+
case 1:
232173
{
233-
ptsf3[i] = (is_float) ? ptsf[i] : Point2f((float)ptsi[i].x, (float)ptsi[i].y);
174+
_center = (is_float) ? ptsf[0] : Point2f((float)ptsi[0].x, (float)ptsi[0].y);
175+
_radius = EPS;
176+
break;
234177
}
235-
findEnclosingCircle3pts_orLess_32f(ptsf3, count, center, radius);
236-
_center = center;
237-
_radius = radius;
238-
return;
239-
}
240-
241-
if (is_float)
242-
{
243-
findMinEnclosingCircle<Point2f>(ptsf, count, center, radius);
244-
#if 0
245-
for (size_t m = 0; m < count; ++m)
178+
case 2:
246179
{
247-
float d = (float)norm(ptsf[m] - center);
248-
if (d > radius)
249-
{
250-
printf("error!\n");
251-
}
180+
Point2f p1 = (is_float) ? ptsf[0] : Point2f((float)ptsi[0].x, (float)ptsi[0].y);
181+
Point2f p2 = (is_float) ? ptsf[1] : Point2f((float)ptsi[1].x, (float)ptsi[1].y);
182+
_center.x = (p1.x + p2.x) / 2.0f;
183+
_center.y = (p1.y + p2.y) / 2.0f;
184+
_radius = (float)(norm(p1 - p2) / 2.0) + EPS;
185+
break;
252186
}
253-
#endif
254-
}
255-
else
256-
{
257-
findMinEnclosingCircle<Point>(ptsi, count, center, radius);
258-
#if 0
259-
for (size_t m = 0; m < count; ++m)
187+
default:
260188
{
261-
double dx = ptsi[m].x - center.x;
262-
double dy = ptsi[m].y - center.y;
263-
double d = std::sqrt(dx * dx + dy * dy);
264-
if (d > radius)
189+
Point2f center;
190+
float radius = 0.f;
191+
if (is_float)
192+
{
193+
findMinEnclosingCircle<Point2f>(ptsf, count, center, radius);
194+
#if 0
195+
for (size_t m = 0; m < count; ++m)
196+
{
197+
float d = (float)norm(ptsf[m] - center);
198+
if (d > radius)
199+
{
200+
printf("error!\n");
201+
}
202+
}
203+
#endif
204+
}
205+
else
265206
{
266-
printf("error!\n");
207+
findMinEnclosingCircle<Point>(ptsi, count, center, radius);
208+
#if 0
209+
for (size_t m = 0; m < count; ++m)
210+
{
211+
double dx = ptsi[m].x - center.x;
212+
double dy = ptsi[m].y - center.y;
213+
double d = std::sqrt(dx * dx + dy * dy);
214+
if (d > radius)
215+
{
216+
printf("error!\n");
217+
}
218+
}
219+
#endif
267220
}
221+
_center = center;
222+
_radius = radius;
223+
break;
268224
}
269-
#endif
270225
}
271-
_center = center;
272-
_radius = radius;
273226
}
274227

275228

‎modules/imgproc/test/test_convhull.cpp

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1017,6 +1017,62 @@ int CV_MinCircleTest::validate_test_results( int test_case_idx )
10171017
return code;
10181018
}
10191019

1020+
/****************************************************************************************\
1021+
* MinEnclosingCircle Test 2 *
1022+
\****************************************************************************************/
1023+
1024+
class CV_MinCircleTest2 : public CV_BaseShapeDescrTest
1025+
{
1026+
public:
1027+
CV_MinCircleTest2();
1028+
protected:
1029+
RNG rng;
1030+
void run_func(void);
1031+
int validate_test_results( int test_case_idx );
1032+
float delta;
1033+
};
1034+
1035+
1036+
CV_MinCircleTest2::CV_MinCircleTest2()
1037+
{
1038+
rng = ts->get_rng();
1039+
}
1040+
1041+
1042+
void CV_MinCircleTest2::run_func()
1043+
{
1044+
Point2f center = Point2f(rng.uniform(0.0f, 1000.0f), rng.uniform(0.0f, 1000.0f));;
1045+
float radius = rng.uniform(0.0f, 500.0f);
1046+
float angle = (float)rng.uniform(0.0f, (float)(CV_2PI));
1047+
vector<Point2f> pts;
1048+
pts.push_back(center + Point2f(radius * cos(angle), radius * sin(angle)));
1049+
angle += (float)CV_PI;
1050+
pts.push_back(center + Point2f(radius * cos(angle), radius * sin(angle)));
1051+
float radius2 = radius * radius;
1052+
float x = rng.uniform(center.x - radius, center.x + radius);
1053+
float deltaX = x - center.x;
1054+
float upperBoundY = sqrt(radius2 - deltaX * deltaX);
1055+
float y = rng.uniform(center.y - upperBoundY, center.y + upperBoundY);
1056+
pts.push_back(Point2f(x, y));
1057+
// Find the minimum area enclosing circle
1058+
Point2f calcCenter;
1059+
float calcRadius;
1060+
minEnclosingCircle(pts, calcCenter, calcRadius);
1061+
delta = (float)norm(calcCenter - center) + abs(calcRadius - radius);
1062+
}
1063+
1064+
int CV_MinCircleTest2::validate_test_results( int test_case_idx )
1065+
{
1066+
float eps = 1.0F;
1067+
int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1068+
if (delta > eps)
1069+
{
1070+
ts->printf( cvtest::TS::LOG, "Delta center and calcCenter > %f\n", eps );
1071+
code = cvtest::TS::FAIL_BAD_ACCURACY;
1072+
ts->set_failed_test_info( code );
1073+
}
1074+
return code;
1075+
}
10201076

10211077
/****************************************************************************************\
10221078
* Perimeter Test *
@@ -1905,6 +1961,7 @@ TEST(Imgproc_ConvexHull, accuracy) { CV_ConvHullTest test; test.safe_run(); }
19051961
TEST(Imgproc_MinAreaRect, accuracy) { CV_MinAreaRectTest test; test.safe_run(); }
19061962
TEST(Imgproc_MinTriangle, accuracy) { CV_MinTriangleTest test; test.safe_run(); }
19071963
TEST(Imgproc_MinCircle, accuracy) { CV_MinCircleTest test; test.safe_run(); }
1964+
TEST(Imgproc_MinCircle2, accuracy) { CV_MinCircleTest2 test; test.safe_run(); }
19081965
TEST(Imgproc_ContourPerimeter, accuracy) { CV_PerimeterTest test; test.safe_run(); }
19091966
TEST(Imgproc_FitEllipse, accuracy) { CV_FitEllipseTest test; test.safe_run(); }
19101967
TEST(Imgproc_FitEllipse, parallel) { CV_FitEllipseParallelTest test; test.safe_run(); }

0 commit comments

Comments
 (0)