CODEWITHSUNDEEP
c++sortinggeometry
n_ermosh
n_ermosh

Reputation: 649

C++ Sorting line segment array into CW or CCW order

I am working on an algorithm for slicing an STL file into separate SVG files for each slice. I am the point where I have an array of line segments that will make up one or more polygons in each slice (if the STL model has a hole in it, there will be several polygons that make up the contour), and I need a way to sort these segments into

  1. CW or CCW order (and reoriented if necessary)
  2. Into separate arrays for every polygon in the starting array.

The segments are assumed to be in random order and random orientation in the array. All the segments in each polygon will line up, but I want them to be also be lined up head to tail, so some of the segments might need to have their vertices flipped

The vertex struct is just xyz coordinates. I don't actually care if the segments are arranged CW or CCW, as long as they are in order.

Upvotes: 2

Views: 1473

Answers (1)

Beta
Beta

Reputation: 99094

You haven't shown us any code, so I'll write pseudocode:

while there are still loose segments
  take a loose segment and put it in a new polygon
  while the tail vertex of the polygon doesn't match its head vertex
    iterate over the remaining loose segments
      if the head of the segment matches the tail of the polygon
        append it to the polygon
        break out of the iteration
      reverse the segment
      if the head of the segment matches the tail of the polygon
        append it to the polygon
        break out of the iteration
    if control reaches here, the segments don't form a polygon -- ERROR!
  the polygon is complete, add it to the collection

Upvotes: 3

Related Questions