我有一个三角形网格。 假设它看起来像一个崎岖不平的表面。 我希望能够找到落在网的外围边框的所有边。 （忘记内顶点）
我知道我必须要找到那些只连接到一个三角形的边缘，并收集所有这些结合在一起，这就是答案。 但我想，以确保这些边缘的顶点是有序的形状周围顺时针方向旋转。
我想这样做，因为我想避开网外侧的多边形线。
我希望这是不够清楚明白。 在某种意义上，我试图“去三角测量”网格。 哈！ 如果有这样的术语。
Answer 1:
边界边仅由在网格中的一个三角形引用的，所以找到他们需要通过网所有三角形进行扫描，并采取边用一个单一的引用计数。 你可以有效地做到这一点（在O(N)通过利用哈希表）。
要边集转换为有序的多边形循环您可以使用遍历方法：
- 挑选任何未访问的边缘段
[v_start,v_next]和这些顶点添加到多边形环。 - 找到未访问的边缘段
[v_i,v_j]具有任一v_i = v_next或v_j = v_next并添加其他顶点（一个不等于v_next）到多边形环。 复位v_next因为这新增加的顶点，作为访问和2继续标记边缘。 - 当我们回到遍历完成
v_start。
遍历会给多边形循环，可能有两种顺时针或反顺时针排序。 一致的顺序可以通过考虑建立多边形的签面积 。 如果在错误的方向遍历结果你只需要扭转多边形环顶点的顺序。
Answer 2:
那么俗话说 - 得到它的工作 - 然后得到它的工作好。 我注意到上面的例子中它假定边缘阵列中的所有边做实际上是在一个不错的边界连接起来。 这可能不是在现实世界的情况下（因为我已经从我用我的输入文件发现！）其实我的一些输入的实际文件有许多多边形和所有需要检测的边界。 我也想确保缠绕顺序是正确的。 所以，我有固定的了也。 见下文。 （觉得我在去年取得进展！）
private static List<int> OrganizeEdges(List<int> edges, List<Point> positions)
{
var visited = new Dictionary<int, bool>();
var edgeList = new List<int>();
var resultList = new List<int>();
var nextIndex = -1;
while (resultList.Count < edges.Count)
{
if (nextIndex < 0)
{
for (int i = 0; i < edges.Count; i += 2)
{
if (!visited.ContainsKey(i))
{
nextIndex = edges[i];
break;
}
}
}
for (int i = 0; i < edges.Count; i += 2)
{
if (visited.ContainsKey(i))
continue;
int j = i + 1;
int k = -1;
if (edges[i] == nextIndex)
k = j;
else if (edges[j] == nextIndex)
k = i;
if (k >= 0)
{
var edge = edges[k];
visited[i] = true;
edgeList.Add(nextIndex);
edgeList.Add(edge);
nextIndex = edge;
i = 0;
}
}
// calculate winding order - then add to final result.
var borderPoints = new List<Point>();
edgeList.ForEach(ei => borderPoints.Add(positions[ei]));
var winding = CalculateWindingOrder(borderPoints);
if (winding > 0)
edgeList.Reverse();
resultList.AddRange(edgeList);
edgeList = new List<int>();
nextIndex = -1;
}
return resultList;
}
/// <summary>
/// returns 1 for CW, -1 for CCW, 0 for unknown.
/// </summary>
public static int CalculateWindingOrder(IList<Point> points)
{
// the sign of the 'area' of the polygon is all we are interested in.
var area = CalculateSignedArea(points);
if (area < 0.0)
return 1;
else if (area > 0.0)
return - 1;
return 0; // error condition - not even verts to calculate, non-simple poly, etc.
}
public static double CalculateSignedArea(IList<Point> points)
{
double area = 0.0;
for (int i = 0; i < points.Count; i++)
{
int j = (i + 1) % points.Count;
area += points[i].X * points[j].Y;
area -= points[i].Y * points[j].X;
}
area /= 2.0f;
return area;
}
Answer 3:
遍历代码（效率不高-需要进行一些清理工作，将能在某个时候）请注意：我在链中的每个片段存储为2个指数-而不是1达伦的建议。 这纯粹是我自己执行/渲染需求。
// okay now lets sort the segments so that they make a chain.
var sorted = new List<int>();
var visited = new Dictionary<int, bool>();
var startIndex = edges[0];
var nextIndex = edges[1];
sorted.Add(startIndex);
sorted.Add(nextIndex);
visited[0] = true;
visited[1] = true;
while (nextIndex != startIndex)
{
for (int i = 0; i < edges.Count - 1; i += 2)
{
var j = i + 1;
if (visited.ContainsKey(i) || visited.ContainsKey(j))
continue;
var iIndex = edges[i];
var jIndex = edges[j];
if (iIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(jIndex);
nextIndex = jIndex;
visited[j] = true;
break;
}
else if (jIndex == nextIndex)
{
sorted.Add(nextIndex);
sorted.Add(iIndex);
nextIndex = iIndex;
visited[i] = true;
break;
}
}
}
return sorted;
文章来源: Get border edges of mesh - in winding order
