网站怎么建设?,废旧电脑做网站服务器,奉贤集团网站建设,一个网站多个数据库斯坦纳点
斯坦纳点别名正等角中心、费尔马点、斯坦纳点 在三角形的三边各向其外侧作等边三角形#xff0c;这三个等边三角形的外接圆交于一点T#xff0c;该点T即称为托里拆利点#xff08;Torricelli’s point #xff09;#xff0c;而三个等边三角形的外接圆称为托里拆…斯坦纳点
斯坦纳点别名正等角中心、费尔马点、斯坦纳点 在三角形的三边各向其外侧作等边三角形这三个等边三角形的外接圆交于一点T该点T即称为托里拆利点Torricelli’s point 而三个等边三角形的外接圆称为托里拆利圆。在一定条件下托里拆利点和正等角中心、费尔马点等是一回事。托里拆利点是由意大利物理学家托里拆利发现的。该问题是费马(1601-1665)作为“求一点使它至一三角形三顶点的距离和最小这一著名的极值问题而向意大利物理学家托里拆利(1608-1647)提出并为托里拆利所解决的当三角形内角均小于120°时点K即为所求故称K为托里拆利点也称费马点。以后德国斯太纳((1796-1863)独立提出并推广了它故又称斯太纳问题。
斯坦纳树
斯坦纳树问题是组合优化问题与最小生成树相似是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点使生成的最短网络开销最小。 斯坦纳树问题的定义随着历史的发展在不断的扩展和推广
瑞士数学家斯坦纳J.Steiner1796—1863将问题推广成在平面上求一点使得这一点到平面 上给定的若干个点称为所与点的距离之和最小。这可以看作斯坦纳树问题的雏形。考虑到点的其他相关因素加入了权重的表示。形成的推广定义德国的两位数学家韦伯(H.Weber1842—1913)和维斯菲尔德E.Wieszfeld分别在1909年和1937年将该问题作为工 厂选址问题提出来某地有给定的若干个仓库每个仓库的其他相关因素可以换算成一个权重表示求一建造工厂的合适地点使工厂到每个仓库的距离与权重乘积 的总和最小则这个工厂的地址是最经济、便利的。库朗R.Courant和罗宾斯H.Robbins提出第一个定义中斯坦纳对此问题的推广是一种平庸的推广。要得到一个有意义的推广需要考虑的不是引进一个点而应是引进若干个点使引进的点与原来给定的点 连成的网络最小。他们将此新问题称为斯坦纳树问题。给出的定义为 假设原来已经给定了n个点库朗等指出需要引进的点数至多为n-2此种点称为斯坦纳点。过每一斯坦纳点至多有三条边通过。若为三条边则它们两两交成 120°角若为两条边则此斯坦纳点必为某一已给定的点且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树 记作SMT。若此SMT的斯坦纳点中有等于给定点的点则称此SMT为退化的此给定点称为退化点。
Steiner’s minimal tree
Steiner’s minimal tree problem is this: Find the shortest possible network interconnecting a set of points in the Euclidean plane. If the points are linked directly to each other by straight line segments, we obtain the minimal spanning tree. But Steiner’s problem allows for additional points – now called Steiner points – to be added to the network, yielding Steiner’s minimal tree. This generally results in a reduction of the overall length of the network.
Euclidean Steiner tree
The original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments. It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem.
Rectilinear Steiner tree
The rectilinear Steiner tree problem is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem arises in the physical design of electronic design automation. In VLSI circuits, wire routing is carried out by wires that are often constrained by design rules to run only in vertical and horizontal directions, so the rectilinear Steiner tree problem can be used to model the routing of nets with more than two terminals.
Steiner ratio
The Steiner ratio is the supremum of the ratio of the total length of the minimum spanning tree to the minimum Steiner tree for a set of points in the Euclidean plane.
泰森多边形
荷兰气候学家A·H·Thiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法即将所有相邻气象站连成三角形作这些三角形各边的垂直平分线于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度并称这个多边形为泰森多边形。 如图1其中虚线构成的多边形就是泰森多边形。泰森多边形每个顶点是每个三角形的外接圆圆心。泰森多边形也称为Voronoi图或dirichlet图。 泰森多边形的特性是 1每个泰森多边形内仅含有一个离散点数据。 2泰森多边形内的点到相应离散点的距离最近。 3位于泰森多边形边上的点到其两边的离散点的距离相等。 泰森多边形可用于定性分析、统计分析、邻近分析等。例如可以用离散点的性质来描述泰森多边形区域的性质可用离散点的数据来计算泰森多边形区域的数据判断一个离散点与其它哪些离散点相邻时可根据泰森多边形直接得出且若泰森多边形是n边形则就与n个离散点相邻当某一数据点落入某一泰森多边形中时它与相应的离散点最邻近无需计算距离。 在泰森多边形的构建中首先要将离散点构成三角网。这种三角网称为Delaunay三角网。
Delaulay三角形的构建
Delaunay三角网的构建也称为不规则三角网的构建就是由离散数据点构建三角网如图2即确定哪三个数据点构成一个三角形也称为自动联接三角网。即对于平面上n个离散点其平面坐标为(xiyi)i12…n将其中相近的三点构成最佳三角形使每个离散点都成为三角形的顶点。 自动联接三角网的结果为所有三角形的三个顶点的标号如:1,2,82,8,33,8,7…… 为了获得最佳三角形在构三角网时应尽可能使三角形的三内角均成锐角即符合Delaunay三角形产生的准则 1、任何一个Delaunay三角形的外接圆内不能包含任何其它离散点。 2、相邻两个Delaunay三角形构成凸四边形在交换凸四边形的对角线之后六个内角的最小者不再增大。该性质即为最小角最大准则。 下面介绍Tsai1993提出的在n维欧拉空间中构造Delaunay三角形的通用算法—凸包插值算法。 一、凸包生成 1、求出点集中满足min(x-y)、min(xy)、max(x-y)、max(xy)的四个点并按逆时针方向组成一个点的链表。这4个点是离散点中与包含离散点的外接矩形的4个角点最近的点。这4个点构成的多边形作为初始凸包。 2、对于每个凸包上的点I设它的后续点为J计算矢量线段IJ右侧的所有点到IJ的距离求出距离最大的点K。 3、将K插入I、J之间并将K赋给J。 4、重复2、3步直到点集中没有在线段IJ右侧的点为止。 5、将J赋给IJ取其后续点重复2、3、4步。 6、当凸包中任意相邻两点连线的右侧不存在离散点时结束点集凸包求取过程。 完成这一步后形成了包含所有离散点的多边形凸包如图3所示。 二、环切边界法凸包三角剖分 在凸包链表中每次寻找一个由相邻两条凸包边组成的三角形在该三角形的内部和边界上都不包含凸包上的任何其它点。将这个点去掉后得到新的凸包链表。重复这个过程直到凸包链表中只剩三个离散点为止。将凸包链表中的最后三个离散点构成一个三角形结束凸包三角剖分过程。 完成这一步后将凸包中的点构成了若干Delaunay三角形如图4所示。 三、离散点内插 在对凸包进行三角剖分之后不在凸包上的其余离散点可采用逐点内插的方法进行剖分。基本过程为 1、选择一个尚未构成三角形的离散点 2、在已经生成的三角形中找出该离散点的三角形(离散点在该三角形在内部或者在该三角形的边上) 3、如果离散点在三角形的内部则将该三角形以及三角形的边删除然后将三个顶点以及离散点分别连接形成三个新的三角形。如果离散点在三角形的边上记录点所在的边E根据拓扑关系找出该边的左右相邻三角形T1T2添加四条新边和四个新三角形NT删除T1T2以及边E。 对于新生成的三角形需要挨个对其边进行空外接圆检测。具体做法为对于新生成的三角形的边E找出该边相邻的两个三角形判断该边一侧的对角的顶点是否位于另外一个三角形的外接圆的里面。如果是则将边E删除再将两个对角连接起来形成两个新的三角形。对于新三角形的边同样需要进行空外接圆检测如此继续进行直到所有新生成的三角形都通过空外接圆检测为止。 4、重复1、2、3直到所有非凸壳离散点都插入完为止。完成这一步后就完成了Delaunay三角网的构建如图5所示。 四、泰森多边形的建立步骤 建立泰森多边形算法的关键是对离散数据点合理地连成三角网即构建Delaunay三角网。建立泰森多边形的步骤为 1、离散点自动构建三角网即构建Delaunay三角网。对离散点和形成的三角形编号记录每个三角形是由哪三个离散点构成的。 2、找出与每个离散点相邻的所有三角形的编号并记录下来。这只要在已构建的三角网中找出具有一个相同顶点的所有三角形即可。 图6 泰森多边形的建立 3、对与每个离散点相邻的三角形按顺时针或逆时针方向排序以便下一步连接生成泰森多边形。排序的方法可如图6所示。设离散点为o。找出以o为顶点的一个三角形设为A取三角形A除o以外的另一顶点设为a则另一个顶点也可找出即为f则下一个三角形必然是以of为边的即为三角形F三角形F的另一顶点为e则下一三角形是以oe为边的如此重复进行直到回到oa边。 4、计算每个三角形的外接圆圆心并记录之。 5、根据每个离散点的相邻三角形连接这些相邻三角形的外接圆圆心即得到泰森多边形。对于三角网边缘的泰森多边形可作垂直平分线与图廓相交与图廓一起构成泰森多边形。
https://blog.csdn.net/gdut2015go/article/details/48208983 https://desktop.arcgis.com/zh-cn/arcmap/10.3/tools/coverage-toolbox/how-thiessen-works.htm
