CODEWITHSUNDEEP
arraysalgorithmcomputer-science
Dan
Dan

Reputation: 139

Algorithm to sort 2d-points in increasing order

I have to write a pseudo code for an algorithm which sort n 2D points which are randomly distributed within the unit circle. I need to sort them by their distance from the origin 0,0 ( by Increasing Eucledian distance to the circle's origin).

So I think they should be as a 2D array or a Map:

A = { (0.3 , 0.4) , (0.5 , 0.7) , (0.2 , 0.1) , (0.32 , 0.9) }

So here n = 4, we have 4 2D points.

First I thought to calculate the distance from origin (0,0) so (d = sqrt( (A[i].x)^2 + (A[i].y)^2) ) for each point, creating a 1-D array which can be easily sorted using any sorting algorithm, but then I found out that it can be sorted but I cannot have the 2D array sorted in the end, since in the end I just know the d(distance).

Can someone give me a hint on how can I start or explain to me the basic points which I need to go through in order to sorts shuch a system?

Upvotes: 0

Views: 6274

Answers (2)

Eziz Durdyyev
Eziz Durdyyev

Reputation: 1158

In C++ you can store points as a vector of pairs. And use build-in sort function:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool my_comp(const pair<float, float>& point1, const pair<float, float>& point2)
{
    return point1.first*point1.first + point1.second*point1.second < point2.first*point2.first + point2.second*point2.second;
}

int main()
{
    vector< pair<float, float> > points;

    points.push_back( make_pair(3.1, 4.1) );
    points.push_back( make_pair(0.9, 0.8) );
    points.push_back( make_pair(1.0, 1.0) );

    sort(points.begin(), points.end(), my_comp);

    for(int i=0; i<3; i++) {
        cout<<points[i].first<<" "<<points[i].second<<endl;
    }

    return 0;
}

Or, if you want to program in python, same goes for here. Use array of arrays and use build-in sort function:

def my_comp(point1):
    return point1[0]*point1[0] + point1[1]*point1[1]

points = [ [3.1, 4.1], [0.9, 0.8], [1.0, 1.0] ]
points.sort(key=my_comp)
print(points)

Upvotes: 0

Theo Walton
Theo Walton

Reputation: 1105

This question basically boils down to a normal sorting problem. You just need to use the appropriate comparison function.

In c++ for example you could achieve this by storing the x and y values inside a struct and then overloading the < operator.

struct coor
{
        float x;
        float y;

        bool operator < (const coor &lhs)
        {
                return (x * x + y * y < lhs.x * lhs.x + lhs.y * lhs.y);
        }
};

and then std::sort will work on a vector of coor structs.

Upvotes: 1

Related Questions