C++ 将线段数组排序为 CW 或 CCW 顺序

Question

我正在研究一种算法，用于将 STL 文件切片为每个切片的单独 SVG 文件。我是我有一组线段的点，这些线段将在每个切片中组成一个或多个多边形(如果 STL 模型中有一个洞，将有几个多边形组成轮廓)，我需要一个将这些段分类为

的方法

1. CW 或 CCW 顺序(必要时重新定向)
2. 将起始数组中的每个多边形放入单独的数组中。

假定这些段在数组中的顺序和方向是随机的。每个多边形中的所有线段都将排成一行，但我希望它们也从头到尾排成一行，因此某些线段可能需要翻转顶点

顶点结构只是 xyz 坐标。我实际上并不关心这些片段是顺时针还是逆时针排列，只要它们按顺序排列即可。

Answer 1

您没有向我们展示任何代码，所以我将编写伪代码:

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