第三章-空间数据模型汇总课件

第三章 空间数据模型主讲：刘瑞娟3.1 地理空间与空间抽象地理空间与空间抽象 一、地理空间与空间实体地理空间（geographic space）：指地球表面及近地表空间，是地球上大气圈、水圈、生物圈、岩石圈和智慧圈交互作用的区域。地理空间实体：对复杂地理事物和现象进行简化和抽象得到的结果。空间位置特征空间位置特征属性特征属性特征时间特征时间特征空间关系特征：拓扑关系、顺序关系、度量关系空间关系特征：拓扑关系、顺序关系、度量关系二、空间认知和抽象概念模型逻辑数据模型物理数据模型3.1 地理空间与空间抽象地理空间与空间抽象3.2 数据概念模型数据概念模型概念模型：概念模型是地理空间中地理事物与现象的抽象概念集，是地理数据的语义解释，是系统抽象的最高层。目前地理空间数据的概念模型大体上分为三类，即对象模型、网络模型和场模型。对象模型象模型网网络模型模型场模型场模型一、对象模型对象模型：也称作要素模型，将研究的整个地理空间看成一个空域，地理现象和空间实体作为独立的对象分布在该空域中。按照其空间特征分为点、线、面、体四种基本对象。适于对具有明确边界的地理现象建模。（单个地理现象）3.2 数据概念模型数据概念模型地理空间空间要素分类几何坐标非空间属性子部分超部分空间关系非空间关系时间关系对象模型对空间要素的描述子类/超类等效二、场模型场模型：也称作域（field）模型，是把地理空间中的现象作为连续的变量或体来看待。如大气污染程度、地表温度二维场 Af(x，y)三维场 Af(x，y，z)3.2 数据概念模型数据概念模型 （a）规则分布的点 （b）不规则分布的点 （c）规则矩形区 （d）不规则多边形区 （e）不规则三角形区 （f）等值线 场模型的6种表示三、网络模型网络模型：从本质上看与对象模型没有本质的区别，因此网络模型也可以看成对象模型的一个特例，它是由点对象和线对象之间的拓扑空间关系构成的。3.2 数据概念模型数据概念模型四、四、概念模型的选择概念模型的选择 地理现象既可以采用对象模型也可以采用场模型建模，其选择主要取决于应用要求和习惯应用要求和习惯。场模型：连续空间变化趋势的现象；对象模型：单个的地理现象。松松树冷杉冷杉槐槐树（0,0）（0,4）（0,7）（3,0）（7,0）x“松松树”，0 x44；4y77f(x,y)=“冷杉冷杉”，0 x33；0y44 “槐槐树”，3x77；0y44多种林分的森林多种林分的森林按按对象模型的林分建模象模型的林分建模(c)按按场模型的林分建模模型的林分建模森林的两类模型对比区域区域ID主要林分主要林分区域区域/边界界FS1松松树(0,4),(7,4),(7,7),(0,7)FS2冷杉冷杉(0,0),(3,0),(3,4),(0,4)FS3槐槐树(3,0),(7,0),(7,4),(3,4)y3.3 基于对象模型的空间关系分析基于对象模型的空间关系分析一、欧氏（Euclidean）空间中地物要素 在对象模型中，所有的地理实体可以抽象成三类地物要素对象，即点对象、线对象和多边形对象。实体点结点面标识点弧段面面xy图3.6 空间数据的抽象表示岛1 1 1 1、点状实体、点状实体、点状实体、点状实体点或节点、点状实体。点或节点、点状实体。点点：有特定位置，维数为：有特定位置，维数为0 0的物体。的物体。4 4）角点、节点角点、节点VertexVertex：表示线段和弧段上的连接点。表示线段和弧段上的连接点。1）实体点实体点：用来代表一个实体。：用来代表一个实体。2）注记点注记点：用于定位注记。：用于定位注记。3）内点内点：用于负载多边形的：用于负载多边形的属性，存在于多边形内。属性，存在于多边形内。2 2 2 2、线状实体、线状实体、线状实体、线状实体1）实体长度：）实体长度：从起点到终点的总长。从起点到终点的总长。2）弯曲度：）弯曲度：用于表示像道路拐弯时弯曲的程度。用于表示像道路拐弯时弯曲的程度。3）方向性：）方向性：如：水流方向，上游如：水流方向，上游下游，下游，公路，单、双向之分。公路，单、双向之分。具有相同属性的点的轨迹，线或折线，由一系列的具有相同属性的点的轨迹，线或折线，由一系列的有序坐标表示，并有如下特性：有序坐标表示，并有如下特性：线状实体包括：线状实体包括：线段，边界、链、弧段、网络等。线段，边界、链、弧段、网络等。3 3 3 3、面状实体（多边形）、面状实体（多边形）、面状实体（多边形）、面状实体（多边形）面状实体的如下特征：面状实体的如下特征：1 1）面积范围面积范围 2 2）周长周长3 3）独立性或与其它地物相邻独立性或与其它地物相邻如中国及其周边国家如中国及其周边国家4 4）内岛屿或锯齿状外形：内岛屿或锯齿状外形：如岛屿的海岸线封闭所围成的区域。如岛屿的海岸线封闭所围成的区域。叠。叠。是对湖泊、岛屿、地块等一类现象的描述。是对湖泊、岛屿、地块等一类现象的描述。在数据库中由一封闭曲线加内点来表示。在数据库中由一封闭曲线加内点来表示。4 4 4 4、实体类型组合、实体类型组合、实体类型组合、实体类型组合 现实世界的各种现象比较复杂，往往由不同的现实世界的各种现象比较复杂，往往由不同的空间单元组合而成，例如根据某些空间单元或几种空间单元组合而成，例如根据某些空间单元或几种空间单元的组合将空间问题表达出来，复杂实体由空间单元的组合将空间问题表达出来，复杂实体由简单实体组合表达。简单实体组合表达。点、线、面按一定的地理意义点、线、面按一定的地理意义组成区域。组成区域。点、线、面两两之间组合表达复杂的空间问题：点、线、面两两之间组合表达复杂的空间问题：如：如：线线-面面 面面-面面 可见，用各要素之间的可见，用各要素之间的空间关系空间关系，可描述诸多空间问题。空间关，可描述诸多空间问题。空间关系是系是GIS数据描述和表达的重要内容，一方面它为数据描述和表达的重要内容，一方面它为GIS数据库的有效建数据库的有效建立，空间查询，空间分析，辅助决策等提供了最基本的关系，另一方立，空间查询，空间分析，辅助决策等提供了最基本的关系，另一方面有助于形成标准的面有助于形成标准的SQL空间查询语言，便于空间特征的存储，提取，空间查询语言，便于空间特征的存储，提取，查询，更新等。查询，更新等。线线线线面面面面返回返回1、区区域域包包含含线线：计计算算区区域域内内线线的的密密度度，某某省省的水系分布情况。的水系分布情况。2、线线通通过过区区域域：公公路路上否通过某县。上否通过某县。3、线线环环绕绕区区域域：区区域域边边界界，搜搜索索左左右右区区域域名名称称，中中国国与与哪哪些些国国家家接接壤。壤。面面面面面面面面1、包含：岛包含：岛,某省的湖泊分布。某省的湖泊分布。2、相相合合：重重叠叠，学学校校服服务务范范围围与与菜菜场场服务范围重叠区。服务范围重叠区。3、相相邻邻：计计算算相相邻邻边边界界性性质质和和长长度度，公共连接边界。公共连接边界。4 4、分离：计算距离。、分离：计算距离。返回返回学校学校菜场菜场邻接相交重合相离包含点点点线点面线面面面线线不同类型空间实体间的空间关系关系三、空间关系三、空间关系拓扑空间关系：用来描述实体间的相邻、连通、包含和相拓扑空间关系：用来描述实体间的相邻、连通、包含和相交等关系；交等关系；方向空间关系：用于描述实体在地理空间上的排列顺序，方向空间关系：用于描述实体在地理空间上的排列顺序，如实体之间前后、上下、左右和东、南、西、北等方位关系；如实体之间前后、上下、左右和东、南、西、北等方位关系；度量空间关系：用于描述空间实体之间的距离远近等关系。度量空间关系：用于描述空间实体之间的距离远近等关系。3.3 基于对象模型的空间关系分析基于对象模型的空间关系分析北北ab1、拓扑关系、拓扑关系u定义：指指图图形形保保持持连连续续状状态态下下变变形形，但但图图形形关关系系不不变变的的性性质。质。将橡皮任意拉伸，压缩，但不能扭转或折叠。将橡皮任意拉伸，压缩，但不能扭转或折叠。3.3 基于对象模型的空间关系分析基于对象模型的空间关系分析拓扑变换拓扑变换（橡皮变换）（橡皮变换）非拓扑属性（几何）非拓扑属性（几何）拓扑属性（没发生变化的属性）拓扑属性（没发生变化的属性）两点间距离两点间距离一点指向另一点的方向一点指向另一点的方向弧段长度、区域周长、弧段长度、区域周长、面积面积 等等一个点在一条弧段的端点一个点在一条弧段的端点 一条弧是一简单弧段（自身不相交）一条弧是一简单弧段（自身不相交）一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部/外部外部一个点在一个环的内一个点在一个环的内/外部外部一个面是一个简单面一个面是一个简单面一个面的连通性一个面的连通性 面内任两点从一点面内任两点从一点可在面的内部走向另一点可在面的内部走向另一点定义定义u种类3.3 基于对象模型的空间关系分析基于对象模型的空间关系分析1）关关联联性性：（不不同同类类要要素素之之间间）结结点点与与弧弧段段：如如V9与与L5,L6,L3多多 边边 形形 与与 弧弧 段段：P2与与L3,L5,L22）邻邻接接性性：(同同类类元元素素之之间间)多边形之间、结点之间。多边形之间、结点之间。邻接矩阵邻接矩阵重重叠叠：-邻邻接接：1不不邻邻接接：0P1P2P3P4P1-111P21-10P311-0P4100-3 3）连通性：）连通性：）连通性：）连通性：与邻接性相类似，指对与邻接性相类似，指对与邻接性相类似，指对与邻接性相类似，指对弧段连接弧段连接弧段连接弧段连接的判别，如用于网络的判别，如用于网络的判别，如用于网络的判别，如用于网络分析中确定路径、街道是否相通。分析中确定路径、街道是否相通。分析中确定路径、街道是否相通。分析中确定路径、街道是否相通。连通矩阵：连通矩阵：重重叠叠：-连连通通：1不连通：不连通：0V1V2V3V1-10V21-1V301-4 4）拓扑包含：）拓扑包含：）拓扑包含：）拓扑包含：指面状实体包含了哪些线、点或面状实体。指面状实体包含了哪些线、点或面状实体。指面状实体包含了哪些线、点或面状实体。指面状实体包含了哪些线、点或面状实体。主要的拓扑关系：拓扑邻接、拓扑关联、拓扑包含。主要的拓扑关系：拓扑邻接、拓扑关联、拓扑包含。P2P1 P1 P2P3P2P1P2拓扑关系具体可由拓扑关系具体可由4个关系表来表示：个关系表来表示：（1）面面-链关系：链关系：面面构成面的弧段构成面的弧段（2）链链-结点关系：结点关系：链链链两端的结点链两端的结点（3）结点结点-链关系：链关系：结点结点通过该结点的链通过该结点的链（4）链链面关系：面关系：链链左面左面右面右面uu拓扑关系的表达拓扑关系的表达拓扑关系的表达拓扑关系的表达面域与弧段的拓扑关系面域与弧段的拓扑关系面域面域弧段弧段P1A1，A2，A7P2A5，A6，A7P3A4P4A2，A3，A5，-A4弧段与弧段与结点的拓扑关系点的拓扑关系弧段弧段始始结点点终结点点A1N2N1A2N1N3A3N1N5A4N4N4A5N3N5A6N5N2A7N3N2结点与弧段的拓扑关系点与弧段的拓扑关系结点点弧段弧段N1A1，A2，A3N2A1，A6，A7N3A2，A5，A7N4A4N5A3，A5，A6弧段与面域的拓扑关系弧段与面域的拓扑关系弧段弧段左左邻面面右右邻面面A1P0P1A2P1P4A3P4P0A4P3P4A5P2P4A6P0P2A7P2P1返回P1P4uu拓扑关系的意义拓扑关系的意义拓扑关系的意义拓扑关系的意义对于数据处理和对于数据处理和GIS空间分析具有重要的意义，因空间分析具有重要的意义，因为：为：1）拓扑关系能）拓扑关系能清楚地反映清楚地反映实体之间的实体之间的逻辑结构关系逻辑结构关系，它比几何关系具有更大的稳定性，不随地图投影而变化它比几何关系具有更大的稳定性，不随地图投影而变化。2）有助于空间要素的查询有助于空间要素的查询，利用拓扑关系可以解决许，利用拓扑关系可以解决许多实际问题。多实际问题。如某县的邻接县，如某县的邻接县，-面面相邻问题。又如面面相邻问题。又如供水管网系统中某段水管破裂找关闭它的阀门，就需要供水管网系统中某段水管破裂找关闭它的阀门，就需要查询该线（管道）与哪些点（阀门）关联。查询该线（管道）与哪些点（阀门）关联。3）根据拓扑关系可）根据拓扑关系可重建地理实体重建地理实体。2、方向空间关系、方向空间关系方向关系又称为方位关系、延伸关系，它定义了地物方向关系又称为方位关系、延伸关系，它定义了地物对象之间的方位对象之间的方位。基准方向基准方向基准方向基准方向基准方向基准方向（a）点点方向关系）点点方向关系（b）点）点线方向方向关系关系（c）点面方向）点面方向关系关系（d）线线方向关系方向关系（e）线面方向关系面方向关系（f）面面方向关系）面面方向关系基准方向基准方向基准方向基准方向基准方向基准方向不同类型实体间的方向关系3、度量空间关系度量空间关系度量空间关系主要指空间实体间的距离关系。包含点/点、点/线、点/面、线/线、线/面、面/面之间的距离。距离的度量可以是定量的，如按欧几里德距离计算得出A实体距离B实体500m，也可以应用与距离概念相关的概念如远近等进行定性地描述。3.4 3.4 空间逻辑数据模型空间逻辑数据模型逻辑数据模型：GIS描述概念模型中实体及其关系的逻辑结构，是系统抽象的中间层。矢量数据模型栅格数据模型矢量栅格一体化数据模型镶嵌数据模型面向对象数据模型一、矢量数据模型矢量数据模型3.4 3.4 空间逻辑数据模型空间逻辑数据模型 矢量数据模型矢量数据模型适合于用对对象模型象模型抽象的地理空间对象。点实体点实体用一对空间坐标表示,二维空间中对应为（x，y）；线实体线实体由一串坐标对组成，二维空间中表示为（x1，y1）,（x2，y2）（xn，yn）；面面由其边界线表示，表示为首尾相连的坐标串，二维空间中对应为（x1，y1）,（x2，y2）（xn，yn）,（x1，y1）。实体体类型型实体体ID类别位置位置点点5电力力塔塔x1,y1点点6电力力塔塔x1,y1线4河流河流x1,y1；x2,y2；xn,yn多多边形形1杨树林林x1,y1；x2,y2；xn,yn;x1,y1多多边形形2杨树林林x1,y1；x2,y2；xn,yn;x1,y1多多边形形3松松树林林x1,y1；x2,y2；xn,yn;x1,y1电力塔力塔空间对象的矢量数据模型56100005810000杨树林林65750006555000松松树林林2314河流河流56二、栅格数据模型二、栅格数据模型 在栅格数据模型中，点实体是一个栅格单元（cell）或像元，线实体由一串彼此相连的像元构成，面实体则由一系列相邻的像元构成，像元的大小是一致的。栅格单元的属性值：栅格单元的属性值：代表地理实体的代表地理实体的属性。地理实体的不同属性分层存属性。地理实体的不同属性分层存储。储。空间分辨率：空间分辨率：栅格单元的大小，指一栅格单元的大小，指一个像元在地面所代表的实际面积大个像元在地面所代表的实际面积大小。小。3.4 3.4 空间逻辑数据模型空间逻辑数据模型空间对象的栅格数据模型点线面栅格数据结构示例（a）点 （b）线 （c）面全栅格数据文件全栅格数据文件qs.txt 9 9 9 9 1 1 1 1 9 9 9 9 1 1 1 1 9 9 9 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 1 7 7 1 1 1 9 9 1 7 7 1 1 1 1 1 1 7 7 1 1 1 1 1 1 7 7 1 1 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 1 1 1 1 7 7 7 7 三、矢栅一体化数据模型三、矢栅一体化数据模型在矢量栅格数据模型中，对地理空间实体同时按矢量数据模型和栅格数据模型来表述：面状实体的边界采用矢量数据模型描述，而其内部采用栅格数据模型表达；线状实体一般采用矢量数据模型表达，同时将线所经过位置以栅格单元进行充填；点实体则同时描述其空间坐标以及栅格单元位置。3.4 3.4 空间逻辑数据模型空间逻辑数据模型四、镶嵌数据模型四、镶嵌数据模型 镶嵌（Tessellation）数据模型采用规则或不规则的小面块集合来逼近自然界不规则的地理单元，适合于用场模型抽象的地理现象1.规则镶嵌数据模型规则镶嵌数据模型规则镶嵌数据模型，即用规则的小面块集合来逼近自然界不规则的地理单元。（栅格数据模型）优点：主要优点在于其数据结构为通常的二维矩阵结构，每个网格单元表示二维空间的一个位置，不管是沿水平方向还是沿垂直方向均能方便地遍历这种结构。3.4 3.4 空间逻辑数据模型空间逻辑数据模型2.不规则镶嵌数据模型不规则镶嵌数据模型不规则镶嵌数据结构是指用来进行镶嵌的小面块具有不规则的形状或边界。最典型的不规则镶嵌数据模型有Voronoi图图（也称作Thiessen多边形或Dirichlet图）和不不规则三角网规则三角网（Triangular Irregular Network，简称TIN）模型3.4 3.4 空间逻辑数据模型空间逻辑数据模型TIN和Voronoi多边形数据模型Voronoi多边形的特点：u组成多边形的边总是与两相邻样点的连线垂直u多边形内的任何位置总是离该多边形内样点的距离最近，离相邻多边形内样点的距离远u每个多边形内包含且仅包含一个样点。小资料：泰森多边形小资料：泰森多边形荷兰气候学家AHThiessen提出了一种根据离散分布的气象站的降雨量来计算平均降雨量的方法，即将所有相邻气象站连成三角形，作这些三角形各边的垂直平分线，于是每个气象站周围的若干垂直平分线便围成一个多边形。用这个多边形内所包含的一个唯一气象站的降雨强度来表示这个多边形区域内的降雨强度，并称这个多边形为泰森多边形。泰森多边形可用于定性分析、统计分析、邻近分析等。例如，可以用离散点的性质来描述泰森多边形区域的性质；可用离散点的数据来计算泰森多边形区域的数据；判断一个离散点与其它哪些离散点相邻时，可根据泰森多边形直接得出，且若泰森多边形是n边形，则就与n个离散点相邻；当某一数据点落入某一泰森多边形中时，它与相应的离散点最邻近，无需计算距离。TIN数据模型数据模型 TIN能较好的表达地理现象的空间变化，三角形大小随样点密度的变化自动变化，所有样点都称为三角形的顶点，当样点密集时生成的三角形小，而样点较稀时则三角形较大。TIN在表示不连续地理现象时也具有优势，如用TIN表示地形的变化3.4 3.4 空间逻辑数据模型空间逻辑数据模型Voronoi图的生成图的生成 Voronoi图有很多种生成方法，矢量方法主要有对偶生成法、图有很多种生成方法，矢量方法主要有对偶生成法、增添法、部件合成法等。增添法、部件合成法等。u对偶生成法对偶生成法 主要是指生成V图时，先生成其对偶元Delaunay三角网，再通过做三角网每一三角形三条边的中垂线，形成以每一三角形顶点为生成元的多边形网。对偶生成法的关键对偶生成法的关键是Delaunay三角网的生成。Delaunay三角网的特性：满足最大空圆准则三角网的特性：满足最大空圆准则u任一三角形外接圆内不包含其他样点；u所有三角形的最小角度的总和是最大的；u使三角网总边长最小；u在确定的n个点上，构造的Delaunay三角网网形唯一。方案二12341234123412341234最大空圆准则方案一小资料：小资料：小资料：小资料：DelaunayDelaunay三角网格的三角网格的三角网格的三角网格的Bowyer-WatsonBowyer-Watson算法自动生成步骤算法自动生成步骤算法自动生成步骤算法自动生成步骤Step 1、建立初始网格：、建立初始网格：假设给定点集，首先找到一个包含该点的外接的外接矩形 称为辅助窗。一般保证矩形边框长度为点集最大边界长度的三倍。当选好辅助窗，就连接其任一条对角线，形成两个三角形，并对它们标号，把它们作为初始Delaunay三角网。Step 2、逐点插入：、逐点插入：假设原先已经有一个Delaunay三角网T，现在欲往里插入一个新点P。此时首先需要找出所有外接圆包含P点的三角形，并删除P点最近的边，开成一个Delaunay腔，随后连接新插入点与空腔的每一个顶点，如图2所示：Step 3、删除计算区域以外的点：、删除计算区域以外的点：当点集中全部的点插入到三角网格后，删除计算区域以外的三角形，并确保界面的正确三角剖分。对于简单的凸单连通区域，删除与辅助窗顶点 相连的所有三角形即可。如图3所示：当删去辅助窗并修正了网格边界后，Delaunay三角网格的核心生成部分即已全部完成。using System;using System.Collections.Generic;using System.Text;using System.Windows.Forms;namespace Delaunaypublic struct dVertexpublic long x;public long y;public long z;public struct dTrianglepublic long vv0;public long vv1;public long vv2;用用C#语言实现的语言实现的Delaunay三角网算法三角网算法public class Delaunaypublic const int MaxVertices=500;public const int MaxTriangles=1000;public dVertex Vertex=new dVertexMaxVertices;public dTriangle Triangle=new dTriangleMaxTriangles;private bool InCircle(long xp,long yp,long x1,long y1,long x2,long y2,long x3,long y3,double xc,double yc,double r)double eps;double m1;double m2;double mx1;double mx2;double my1;double my2;double dx;double dy;double rsqr;double drsqr;eps=0.000000001;if(Math.Abs(y1-y2)eps&Math.Abs(y2-y3)eps)MessageBox.Show(INCIRCUM-F-Points are coincident!);return false;if(Math.Abs(y2-y1)eps)m2=(-(Convert.ToDouble(x3)-Convert.ToDouble(x2)/(Convert.ToDouble(y3)-Convert.ToDouble(y2);mx2=Convert.ToDouble(x2+x3)/2.0);my2=Convert.ToDouble(y2+y3)/2.0);xc=Convert.ToDouble(x2+x1)/2.0);yc=Convert.ToDouble(m2*(xc-mx2)+my2);else if(Math.Abs(y3-y2)eps)m1=(-(Convert.ToDouble(x2)-Convert.ToDouble(x1)/(Convert.ToDouble(y2)-Convert.ToDouble(y1);mx1=Convert.ToDouble(x1+x2)/2.0);my1=Convert.ToDouble(y1+y2)/2.0);xc=Convert.ToDouble(x3+x2)/2.0);yc=Convert.ToDouble(m1*(xc-mx1)+my1);elsem1=(-(Convert.ToDouble(x2)-Convert.ToDouble(x1)/(Convert.ToDouble(y2)-Convert.ToDouble(y1);m2=(-(Convert.ToDouble(x3)-Convert.ToDouble(x2)/(Convert.ToDouble(y3)-Convert.ToDouble(y2);mx1=Convert.ToDouble(x1+x2)/2.0);mx2=Convert.ToDouble(x2+x3)/2.0);my1=Convert.ToDouble(y1+y2)/2.0);my2=Convert.ToDouble(y2+y3)/2.0);xc=Convert.ToDouble(m1*mx1-m2*mx2+my2-my1)/(m1-m2);yc=Convert.ToDouble(m1*(xc-mx1)+my1);dx=(Convert.ToDouble(x2)-Convert.ToDouble(xc);dy=(Convert.ToDouble(y2)-Convert.ToDouble(yc);rsqr=Convert.ToDouble(dx*dx+dy*dy);r=Convert.ToDouble(Math.Sqrt(rsqr);dx=Convert.ToDouble(xp-xc);dy=Convert.ToDouble(yp-yc);drsqr=Convert.ToDouble(dx*dx+dy*dy);if(drsqr 0)return-1;/WhichSide=-1;else if(equation=0)return 0;elsereturn 1;public int Triangulate(int nvert)bool Complete=new boolMaxTriangles;long,Edges=new long3,MaxTriangles*3+1;long Nedge;long xmin;long xmax;long ymin;long ymax;long xmid;long ymid;double dx;double dy;double dmax;int i;int j;int k;int ntri;double xc=0.0;double yc=0.0;double r=0.0;bool inc;xmin=Vertex1.x;ymin=Vertex1.y;xmax=xmin;ymax=ymin;for(i=2;i=nvert;i+)if(Vertexi.x xmax)xmax=Vertexi.x;if(Vertexi.y ymax)ymax=Vertexi.y;dx=Convert.ToDouble(xmax)-Convert.ToDouble(xmin);dy=Convert.ToDouble(ymax)-Convert.ToDouble(ymin);if(dx dy)dmax=dx;elsedmax=dy;xmid=(xmax+xmin)/2;ymid=(ymax+ymin)/2;Vertexnvert+1.x=Convert.ToInt64(xmid-2*dmax);Vertexnvert+1.y=Convert.ToInt64(ymid-dmax);Vertexnvert+2.x=xmid;Vertexnvert+2.y=Convert.ToInt64(ymid+2*dmax);Vertexnvert+3.x=Convert.ToInt64(xmid+2*dmax);Vertexnvert+3.y=Convert.ToInt64(ymid-dmax);Triangle1.vv0=nvert+1;Triangle1.vv1=nvert+2;Triangle1.vv2=nvert+3;Complete1=false;ntri=1;for(i=1;i=nvert;i+)Nedge=0;j=0;doj=j+1;if(Completej!=true)inc=InCircle(Vertexi.x,Vertexi.y,VertexTrianglej.vv0.x,VertexTrianglej.vv0.y,VertexTriangleTrianglej.vv1.x,VertexTrianglej.vv1.y,VertexTrianglej.vv2.x,VertexTrianglej.vv2.y,xc,yc,r);if(inc)Edges1,Nedge+1=Trianglej.vv0;Edges2,Nedge+1=Trianglej.vv1;Edges1,Nedge+2=Trianglej.vv1;Edges2,Nedge+2=Trianglej.vv2;Edges1,Nedge+3=Trianglej.vv2;Edges2,Nedge+3=Trianglej.vv0;Nedge=Nedge+3;Trianglej.vv0=Trianglentri.vv0;Trianglej.vv1=Trianglentri.vv1;Trianglej.vv2=Trianglentri.vv2;Completej=Completentri;j=j-1;ntri=ntri-1;while(j ntri);for(j=1;j=Nedge-1;j+)if(Edges1,j!=0&Edges2,j!=0)for(k=j+1;k=Nedge;k+)if(Edges1,k!=0&Edges2,k!=0)if(Edges1,j=Edges2,k)if(Edges2,j=Edges1,k)Edges1,j=0;Edges2,j=0;Edges1,k=0;Edges2,k=0;for(j=1;j nvert|Trianglei.vv1 nvert|Trianglei.vv2 nvert)Trianglei.vv0=Trianglentri.vv0;Trianglei.vv1=Trianglentri.vv1;Trianglei.vv2=Trianglentri.vv2;i=i-1;ntri=ntri-1;while(i ntri);return ntri;