I have some cross section survey data, which is like this:
X Y Z pt_dt 2970969.635 359725.0088 83.4242 1-x 2970968.278 359722.2182 83.2591 1-x 2970941.771 359670.127 83.0655 1-x 2970961.369 359708.6424 83.4785 1-x 2970950.888 359688.048 85.2994 1-x 2970955.084 359696.2922 83.6479 1-x 2970953.47 359693.1165 84.9628 1-x 2970948.813 359683.977 83.1451 1-x 2970931.904 359650.7413 83.1042 1-x
When I use the X & Y to make points, I can see the points on the map like this:
What I need to do now, is to get the points in linear order (i.e. from left to right, or right to left), so that I can create a 3D line, which can serve as the Cross sectional profile.
My current algorithm, is to calculate the distance between every pair of points(For one given cross section, which is indicated by pt_dt). The pair which has the maximum distance, are the outermost points. I then arrange the points based on distance from one of the outermost points. I have implemented this algorithm in python, and it works.
This algorithm is O(n2); My entire data consists of about 5000 such surveys, so any complexity that I can reduce will be beneficial.
So Is there a more efficient way, or algorithm to do this?