开发者

Remove duplicate items without rounding, C++

开发者 https://www.devze.com 2023-02-17 11:21 出处:网络
I am trying to remove duplicate items from vector using the following comparator bool operator() ( const Point * p1, const Point * p2 ) const

I am trying to remove duplicate items from vector using the following comparator

            bool operator() ( const Point * p1, const Point * p2 ) const
            {
               开发者_开发知识库     return ( p1->X() < p2->X() ) || ( ( p1->X() == p2->X() ) && ( p1->Y() < p2-Y() ) );
            }

and overloaded opeartor ==

bool Point::operator == ( const Point &p ) const
{
    return ( x - p.x ) * ( x - p.x ) + ( y - p.y ) * ( y - p.y ) < DIFF;
}

schematic removing:

std::sort ( it_begin, it_end, Comp );
Points::iterator i_new_end = std::unique ( it_begin, it_end, Uniq);
items.erase ( i_new_end, this->items.end() );

However there is a problem with data. Points sorted according to x coordinate

-0.0000000015   -6281103.8487118632   0.0000000000
-0.0000000011   -5993359.5353725236   0.0000000000
-0.0000000010   -5523510.0253371494   0.0000000000
-0.0000000009   -4885831.4582128422   0.0000000000
-0.0000000009   -4099699.3745807474   0.0000000000
-0.0000000008   -3189000.0000000000   0.0000000000
-0.0000000008   -2181404.4741311157   0.0000000000
-0.0000000008   -1107528.0771596823   0.0000000000 //unique
-0.0000000008   -0.0000000005   0.0000000000
-0.0000000007   1107528.0771596811   0.0000000000  //unique
-0.0000000007   2181404.4741311143   0.0000000000
-0.0000000007   3188999.9999999991   0.0000000000
-0.0000000006   4099699.3745807474   0.0000000000
-0.0000000006   4885831.4582128404   0.0000000000
-0.0000000005   5523510.0253371485   0.0000000000
-0.0000000004   5993359.5353725236   0.0000000000
0.0000000000   -6281103.8487118632   0.0000000000
0.0000000004   5993359.5353725236   0.0000000000
0.0000000005   5523510.0253371485   0.0000000000
0.0000000006   4099699.3745807474   0.0000000000
0.0000000006   4885831.4582128404   0.0000000000
0.0000000007   1107528.0771596811   0.0000000000
0.0000000007   2181404.4741311143   0.0000000000
0.0000000007   3188999.9999999991   0.0000000000
0.0000000008   -3189000.0000000000   0.0000000000
0.0000000008   -2181404.4741311157   0.0000000000
0.0000000008   -1107528.0771596823   0.0000000000
0.0000000008   -0.0000000005   0.0000000000
0.0000000009   -4885831.4582128422   0.0000000000
0.0000000009   -4099699.3745807474   0.0000000000
0.0000000010   -5523510.0253371494   0.0000000000
0.0000000011   -5993359.5353725236   0.0000000000
0.0000000015   -6281103.8487118632   0.0000000000
0.0089638987   -6377999.9999999991   0.0000000000

Operator == does not bring any effect, near points are not sorted next to each other...

Is there any possibility to remove such duplicit points WITHOUT rounding (for exmple a diffrenet comparator)? I know, that coordinates have to many decimal places...


std::sort needs operator <, not operator ==


Operator == does not bring any effect, near points are not sorted next to each other...

If the type of x and y is float or double, then equality cannot be done reliably.

Consider using numeric_limits<double>::epsilon() or numeric_limits<float>::epsilon() when comparison!

Is DIFF in your implementation equal to numeric_limits<T>::epsilon()? (where T is the data type: float or double)


std::sort uses operator<. std::unique uses operator==.

In STL there is a distinction between equality, defined by operator==,and equivalence, defined using operator<:

Two objects are equivalent if neither precedes the other in some sort order of interest. Often, equivalent values are equal, but not always. For example, the strings “STL” and “stl” are equivalent in a case-insensitive sort, but they are certainly not equal. For details on the distinction between equivalence and equality, consult any good reference on the STL. In Effective STL, the issue is examined in Item 19.

http://drdobbs.com/184401469#1


I think you've encountered an unsolvable problem. The standard sort algorithm requires an ordering operator which defines a strict ordering. And there's no way to implement it with "fuzzy" relationships. You're best bet is to define your relationship along the same lines as your ==, but without the epsilon:

inline double mag2( Point const& p )
{
    return p.X() * p.X() + p.Y() * p.Y();
}

bool operator()( Point const* lhs, Point const* rhs )
{
    return mag2( *lhs ) < mag2( *rhs );
}

(Throwing the epsilon in there anywhere will cause the relationship order to cease to be strict, and will result in undefined behavior in the sort algorithm.)

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号