在网络模拟器 ns2 中实现 Delaunay 三角剖分的 Boyer Watson 算法

Question

我想在网络模拟器 ns2 中实现 Delaunay 三角剖分。到现在我知道如何添加节点，如何让它们移动，如何设置流量，以及基本的东西。样本 tcl 脚本在 nam（网络动画师）中完美运行。我很困惑，要为 Delaunay 三角剖分实现 Boyer Watson 算法，第一步是绘制一个包含所有节点的超三角形。我正在使用无线节点并能够获取随机分布节点的坐标。我也可以设法获得每个节点与所有其他节点之间的欧几里得距离。当我在 ns2 中搜索绘图时，它都是关于 xgraph 的。但我希望我能在 nam 内部实现它。那么从哪里开始为我的无线传感器网络画一个超级三角形呢？我在想什么不对吗？在下面发布 Boyer Watson 算法。请问有人帮忙吗？

// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
  badTriangles := empty set
  for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
     if point is inside circumcircle of triangle
        add triangle to badTriangles
  polygon := empty set
  for each triangle in badTriangles do // find the boundary of the polygonal hole
     for each edge in triangle do
        if edge is not shared by any other triangles in badTriangles
           add edge to polygon
  for each triangle in badTriangles do // remove them from the data structure
     remove triangle from triangulation
  for each edge in polygon do // re-triangulate the polygonal hole
     newTri := form a triangle from edge to point
     add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
  if triangle contains a vertex from original super-triangle
     remove triangle from triangulation
return triangulation

Answer 1

最简单的方法是采用您拥有的算法并转录它假设棘手的位是由某些命令实现的。然后选择一个命令是失踪并致力于实施。重复直到完成。

proc computeTriangulation {pointList} {
    # must be large enough to completely contain all the points in pointList
    set superTriangle [computeSuperTriangle $pointList]
    set triangulation [list $superTriangle]
    foreach point $pointList {
        # add all the points one at a time to the triangulation
        set badTriangles {}
        set goodTriangles {}; # INTRODUCED VARIABLE! This is convenient time to split the data
        foreach triangle $triangulation {
            # first find all the triangles that are no longer valid due to the insertion
            if {[pointInCircumcircle $point $triangle]} {
                lappend badTriangles $triangle
            } else {
                lappend goodTriangles $triangle
            }
        }
        set polygon {}
        foreach triangle $badTriangles {
            # find the boundary of the polygonal hole
            foreachEdge edge $triangle {
                if {[edgeIsUnshared $edge $badTriangles] && $edge ni $polygon} {
                    lappend polygon $edge
                }
            }
        }
        set triangulation $goodTriangles; # effectively removes bad triangles from the data structure
        foreach edge $polygon {
            # re-triangulate the polygonal hole
            lappend triangulation [formTriangle $edge $point]
        }
    }
    # This is a standard pattern for doing list filtering where the filter is computed
    return [lmap triangle $triangulation {
        # done inserting points, now clean up
        if {[hasVertexFrom $triangle $superTriangle]} {
            continue
        }
        string cat $triangle
    }]
}

现在，只缺少 computeSuperTriangle、pointInCircumcircle、foreachEdge、edgeIsUnshared、formTriangle 和 hasVertexFrom。但是这些都比整体算法好写。（您将需要决定如何表示三角形；顶点列表可能就足够了。并且必须注意 foreachEdge 始终 return 以“一致”或您将在 polygon 中获得非唯一元素；我建议对边缘中的点进行排序，以便最小坐标排在第一位。毕竟，在此算法中，边缘中点的顺序是任意的。）

在网络模拟器 ns2 中实现 Delaunay 三角剖分的 Boyer Watson 算法

Implementing Boyer Watson algorithm for Delaunay Triangulation in Network Simulator ns2

tcl

sensors

triangulation

ns2

delaunay