Completed

C+ algorithm to sort 2d points in a linear fashion

Published on the January 29, 2023 in IT & Programming

About this project

Open

We need an optimized algorithm written in c++ to sort 2d points along a route. The function shall receive a pointer to a vector that contains a quantity of random points (represented by x,y float coordinates). A typical set will contain 300,000 points. It has to order these points in a way that they form a continuous line, trying to achieve the shortest line possible.

Project overview

Let's say that 3 different people were each holding a pen. There is a somewhat blurred route that goes from location A to location B. These people are told to draw a line along the blurred route starting near one of the locations and going towards near the other (attachment path.png). For every 'd' distance along the drawn lines, the coordinates of a point are saved in the vector. We do not know which coordinate belongs to each person, we don't know where each one started or ended, all we have is the 2d points generated by the three lines in one vector (attachment detail1.png). After sorting the points, we seek the shortest path that contains all of the recorded points, starting in one extreme and ending at the other (something like the black line of attachment detail2.png).

Category IT & Programming
Subcategory Data Science
Project size Small
Is this a project or a position? Project
Required availability As needed

Delivery term: Not specified

Skills needed

Programming Aptitude

Want to start working on this project?

Log into your Workana account or Register today. Boost your freelance work!

Other projects posted by B. S.