CODEWITHSUNDEEP
c++sortingvector
JGrieco
JGrieco

Reputation: 27

Sort container, then shift elements while preserving original sort

I have a std::vector filled with 2d line endpoints that emit from a circle's center.

std::vector<vec2> points(fillPoints( ));
std::sort( points.begin( ), points.end( ), [&]( const vec2& a, const vec2& b ) {
    return clockwiseSortPredicate( a, b, center );
} );

The center variable is in-class, so the lambda is fine. The lines are of variable length, and the sort places the point at 12:00 (90 degrees) as the first element.

I would like to maintain this clockwise sort, but I would like to rearrange the elements in the container so that the first element is the element with the shortest distance from the circle's center. A predicate to compare the distances is easy, but I don't understand how to shift the elements around.

e.g., if the point with smallest distance from center has angle of 45 degrees, then I would like that 45-degree element to be the first element in the container, maintain the sort order for the remainder of the container, then re-insert the elements from the beginning of the container in the clockwise-sorted order they already have.

EDIT for more information: Here's an example, making a circle then arbitrarily taking one point and making it the smallest. Like center, radius is an in-class variable, and should be assumed to be a valid float.

const auto numPoints = 30;
std::vector<vec2> points;
const auto increment = 6.283185308f / numPoints;  //2pi radians
for ( auto i = 0; i != numPoints; ++i ) {
    const float theta = i * increment;
    auto newRadius = i == 2 ? radius / 2 : radius;
    const auto x = center.x + std::cos( theta ) * newRadius;
    const auto y = center.y + std::sin( theta ) * newRadius;
    points.push_back( vec2(x,y) );
}

sorting output is from 12:00 rotating clockwise, and points[2] has the smallest distance:

{ p0, p1, p2(smallest!), ..., p29 }

After the second operation, the set would look like:

{ p2, p3, p4, ..., p29, p0, p1 }

Upvotes: 0

Views: 114

Answers (2)

quantdev
quantdev

Reputation: 23813

Use std::min_element to find the element with the shortest distance (that is, a min with a custom comparer), and use std::rotate to perform an in-place rotation.

Something like :

auto it = std::min_element( points.begin(), points.end() , IsClosestComparer);
std::rotate(points.begin(), it , points.end() )

Upvotes: 3

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153955

It seems, you are looking for std::min_element() to locate the shorted element and std::rotate() to move elements within the std::vector<vec2>.

Upvotes: 3

Related Questions