Sort lines, part of a closed shape

Question

I have an array of structures, each structure element holds the endpoints of lines in 3D space.

struct POINTS
{
   float xStart;
   float yStart;
   float zStart;

   float xEnd;
   float yEnd;
   float zEnd;
};

Combining these lines will create a closed shape. Unfortunately the lines are not in the correct order.

To make the lines in order, to create the closed loop, I think the line points should rearrange like:

  • Take a line, say LINE-A.
  • Find the start point of another line, say LINE-X, whose start point is LINE-A's end point.

    OR

  • Find the End point of another line, say LINE-Y, whose End point is LINE-A's start point.....

However I am not sure this is the right solution. I will appreciate for suggesting suitable optimized methods to solve this problem.

[Note Added] My real intention is to create the closed shape in 2D plane. So solution for 2D plane is also expected from the geniuses.


Show source
| sorting   | c++   | algorithm   | line   | 3d   2016-12-30 12:12 1 Answers

Answers to Sort lines, part of a closed shape ( 1 )

  1. 2016-12-30 14:12

    Main idea - put all points to multimap (where key is a point coordinates and value is a index of line and begin/end mark). After that you need to select any point as startup, find index of line that has this point and fetch another end of line. Then you mark current line as used and use end of current line as startup for next iteration.

    vector<POINTS> lines = generate_lines(10);
    multimap<tuple<double, double, double>, pair<double, double> > M;
    
    for (int i = 0; i < lines.size(); i++)
    {
        // start point
        M.insert(make_pair(make_tuple(lines[i].xStart, lines[i].yStart, lines[i].zStart),
                           make_pair(i, 0) ) );
    
        // end point
        M.insert(make_pair(make_tuple(lines[i].xEnd, lines[i].yEnd, lines[i].zEnd),
                           make_pair(i, 1) ) );
    }
    
    auto coords1 = M.begin()->first;
    auto pos1 = M.begin()->second;
    
    vector<bool> used(lines.size(), false);
    
    for (int i = 0; i < lines.size(); i++)
    {
        std::tuple<double, double, double> coords2 = pos1.second ? make_tuple(lines[pos1.first].xStart, lines[pos1.first].yStart, lines[pos1.first].zStart) :
                                                                   make_tuple(lines[pos1.first].xEnd, lines[pos1.first].yEnd, lines[pos1.first].zEnd);
    
        cout << pos1.first << ": " << get<0>(coords1) << " " << get<1>(coords1) << " " << get<2>(coords1) << " - "
                                   << get<0>(coords2) << " " << get<1>(coords2) << " " << get<2>(coords2) << endl;
    
        used[pos1.first] = true;
    
        pair<int, int> nextPos(-1, -1);
    
        auto r = M.equal_range(coords2);
        for (auto it = r.first; it != r.second; it++)
            if (!used[it->second.first])
            {
                nextPos = it->second;
                break;
            }
    
        if (nextPos.first == -1 && i != lines.size()-1)
        {
            cout << "something bad happens\n";
            return 1;
        }
    
        pos1 = nextPos;
        coords1 = coords2;
    }
    

    The complexity of the algorithm is O(N * logN). This algorithm doesn't required end-to-start sorted data.

    You can find full source code with example generation here: http://ideone.com/TuzjMn

Leave a reply to - Sort lines, part of a closed shape

◀ Go back