时间戳

首页 > 解决方案 > 在 Network Simulator ns2 中实现用于 Delaunay 三角剖分的 Boyer Watson 算法

tcl - 在 Network Simulator ns2 中实现用于 Delaunay 三角剖分的 Boyer Watson 算法

问题描述

我想在 Network Simulator ns2 中实现 Delaunay Triangulation。到目前为止，我知道如何添加节点，如何使它们移动，如何设置流量以及基本的东西。示例 tcl 脚本在 nam(network animator) 中完美运行。我很困惑，要为 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

标签： tclsensorstriangulationns2delaunay

解决方案

像这样的最简单方法是采用您拥有的算法并将其转录，假设棘手的位是由某些命令实现的。然后选择缺少的命令之一并努力实现它。重复直到完成。

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始终以“一致”的形式返回边，否则您将获得非唯一元素polygon; 我建议对边缘中的点进行排序，以便最小坐标在前。毕竟，在该算法中，边​​缘中点的顺序是任意的。）

推荐阅读