| 3574 | |
| 3575 | |
| 3576 | static float |
| 3577 | medianPartition( size_t* ofs, int a, int b, const float* vals ) |
| 3578 | { |
| 3579 | int k, a0 = a, b0 = b; |
| 3580 | int middle = (a + b)/2; |
| 3581 | while( b > a ) |
| 3582 | { |
| 3583 | int i0 = a, i1 = (a+b)/2, i2 = b; |
| 3584 | float v0 = vals[ofs[i0]], v1 = vals[ofs[i1]], v2 = vals[ofs[i2]]; |
| 3585 | int ip = v0 < v1 ? (v1 < v2 ? i1 : v0 < v2 ? i2 : i0) : |
| 3586 | v0 < v2 ? i0 : (v1 < v2 ? i2 : i1); |
| 3587 | float pivot = vals[ofs[ip]]; |
| 3588 | std::swap(ofs[ip], ofs[i2]); |
| 3589 | |
| 3590 | for( i1 = i0, i0--; i1 <= i2; i1++ ) |
| 3591 | if( vals[ofs[i1]] <= pivot ) |
| 3592 | { |
| 3593 | i0++; |
| 3594 | std::swap(ofs[i0], ofs[i1]); |
| 3595 | } |
| 3596 | if( i0 == middle ) |
| 3597 | break; |
| 3598 | if( i0 > middle ) |
| 3599 | b = i0 - (b == i0); |
| 3600 | else |
| 3601 | a = i0; |
| 3602 | } |
| 3603 | |
| 3604 | float pivot = vals[ofs[middle]]; |
| 3605 | int less = 0, more = 0; |
| 3606 | for( k = a0; k < middle; k++ ) |
| 3607 | { |
| 3608 | CV_Assert(vals[ofs[k]] <= pivot); |
| 3609 | less += vals[ofs[k]] < pivot; |
| 3610 | } |
| 3611 | for( k = b0; k > middle; k-- ) |
| 3612 | { |
| 3613 | CV_Assert(vals[ofs[k]] >= pivot); |
| 3614 | more += vals[ofs[k]] > pivot; |
| 3615 | } |
| 3616 | CV_Assert(std::abs(more - less) <= 1); |
| 3617 | |
| 3618 | return vals[ofs[middle]]; |
| 3619 | } |
| 3620 | |
| 3621 | static void |
| 3622 | computeSums( const Mat& points, const size_t* ofs, int a, int b, double* sums ) |