确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想 ,根据输入多边形A ,B之间边的拓扑关系 ,划分A ,B边为内边、外边、重叠边 3种 ,揭示A ,B与它们的交、并、差之间边的本质联系 ,进而描述了确定任意两个简单多边形交、并、差算法 算法的时间复杂度为O((n +m +k)log(n +m +k) ) ,其中n ,m分别是A ,B的顶点数 ,k是两多边形的交点数 算法建立在数学理论基础之上 ,很好地处理了布尔运算的奇异情形 ,比如重叠边 ,边与边相交于边的顶点等情形

基于格网的多边形集合级联求并算法

与传统的多边形集合求并算法相比,级联求并法基于STR-Tree索引优先对相邻的多边形进行求并,提高多边形集合的求并效率,但在数据密度高畸变区域的性能较差。针对该问题,提出一种基于格网的多边形集合级联求并算法。该算法利用格网划分多边形集合,缩小数据密度高畸变区域的范围,进一步提高级联求并法的效率。实验结果表明,该算法有效可行。

确定两个任意多边形的并的算法

目的设计并分析求两个任意多边形的并的一种新算法．方法利用分治思想设计算法，即根据Ｐ，Ｑ凸壳及Ｐ与Ｑ的凸壳的不同位置关系，分６种情况分别求并Ｐ∪Ｑ的边界．结果成功设计出新的算法并分析出该算法的时间复杂性为Ｏ（ｎ＋ｍ）次判断两条线段是否相交，其中ｎ，ｍ分别是多边形Ｐ与Ｑ的顶点数．结论该算法优于逐次判断Ｐ的每条边是否与Ｑ的边相交的方法．

一种凸多边形的交、并求解算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列.提出了以顶点与多边形的空间拓扑关系为基础,将不同拓扑关系的顶点进行重新组合的方法来解决任意2个凸多边形交、并的求解问题.算法易于编程实现,能够较好的求解二维凸多边形区域各种情况的交与并,可为G IS应用中矢量多边形之间的关系计算提供算法基础.

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。

一种在MapXtreme Java中实现多边形叠加的方法

多边形叠加是地理信息系统中一种非常有用的空间分析功能。笔者针对MapXtreme Java中没有提供多边形叠加分析功能这一问题,提出了利用缓冲区分析思想实现多边形叠加中的求多边形之和的一种方法,很好地解决了项目中求多边形之和的问题,同时也为其它开发人员使用MapXtreme Java实现求多边形之和提供了思路。

计算两凸多边形的并集多边形及其面积的计算机算法与实现

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法,并对算法实现给出详细的计算过程。程序实现中,文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向,进而判别平面上一点是否在凸多边形内的方法,简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。

带孔洞多边形的求交算法

为简化已有任意简单多边形求交算法并提高算法效率,首先将交点分类并排序,然后采用不同的遍历方法得到多边形的交集、并集和差集,在该算法的基础上设计带孔洞多边形的求交算法.所有算法均被实现,且复杂度较低,鲁棒性较好.

简单多边形裁剪及交并计算的统一算法

研究发现了简单多边形裁剪和交并计算的内在一致性．从工程角度出发，以解决不规则物体布局问题为最终目的，提出了解决简单多边形裁剪和交并计算的统一的、切实可行的算法，为不规则物体布局问题的解决奠定了基础．

基于STL模型投影轮廓的EPS连续切割技术

针对目前EPS连续切割技术轮廓数据不易直接获取、不同角度轮廓数据之间存在干扰的情况,提出了基于STL模型投影轮廓的EPS连续切割技术.该方法用等距的平行平面直接切分某个角度的STL模型,然后对获得的轮廓求并而得到该角度下的投影轮廓,并配合STL模型固定角度的旋转,获得STL模型各个角度的投影轮廓,最后处理投影轮廓、加工EPS模型.对简单多边形求并的算法作了详细的阐述,对模型的精度也作了简单的分析.实验结果表明,基于投影轮廓的EPS连续切割技术稳定、准确、高效地切割了EPS模型.

中国汽车工业市场结构变迁及其成因

为揭示我国汽车工业的结构演进过程,以更好地引导发展,本文运用产业组织理论对我国汽车工业市场结构变迁及其成因进行了梳理。研究表明,我国汽车工业发展史可分为五个阶段,各阶段的市场结构特点、成因、竞争程度均有很大差异,其中政府和市场影响呈现此消彼长的局面,但政府角色更关键。政府一系列行为旨在塑造由国营车企主导的高集中度市场结构,但行政主导式的高集中寡占型市场结构由于缺乏有效市场竞争,因而市场结构始终与较强的市场势力和不完全竞争相联系。此外,本文还运用博弈论探讨了现阶段"多角联盟"下的企业行为,分析表明该结构下的价格合谋更具稳态性。

计算多边形交集、并集面积的算法

平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。

动态计算圆弧并面积的一个新算法

平面上以任意方式放置的Ｎ个圆（Ｎ≥１）所覆盖区域面积的计算问题称为圆弧并面积的计算问题．该问题不仅具有很强的应用背景，而且是计算几何，ＣＡＤ／ＣＡＭ和计算机图形学中的一个基础算法．本文在给出有向多边形区域面积、约束圆弧所对圆心角计算公式的基础上，提出一个基于圆弧求交、平面有向多边形面积、扇形面积计算的动态计算圆弧并面积的一个新算法．该算法具有计算精度高，计算速度快，计算时间与圆的大小和计算精度无关，能统一处理圆弧并面积计算的各种情况，算法适用性和交互性好等特点．

基于多级格网的多边形集合求并算法研究

多边形集合求并效率的高低,关键在于能否根据多边形的相邻程度优化求并顺序.在分析了几种常用求并算法优劣的基础上,提出了基于多级格网的多边形集合求并算法.通过构建多级格网,划分多边形集合,既缩小了多边形畸变区域的范围,也减少了一级格网的密集程度,提高了求并效率.对比实验表明,该算法可行.

基于双向链表操作的多边形求交与并的算法改进

对两个多边形的各边依次求交,根据交点所在边起始点与另一多边形的包含关系确定交点的入出状态,并按交点所在边的序号及距边起始点的距离排序,再插入到双向链表中,利用链表中各交点的入出状态搜索其交集、并集。论文算法中对点重合、边重合等特殊情况,仅需对在求取交点时做简单的特殊处理,其后续操作均使用统一处理方式,相比其它传统的算法,论文提出的算法简单高效。

基于集群MPI的图层级多边形并行合并算法

在集群环境下,基于MPI并行编程模型和OGC简单要素规范进行并行多边形合并时,需要处理叠加图层间要素的"多对多"映射关系,由于空间上相邻的多边形在要素序列上并不一定连续,导致无法按要素序列为子节点分配任务,给并行任务映射带来了困难。本文以集群环境下的并行多边形合并算法为研究对象,通过比较叠加分析中两种多边形映射关系对算法并行化带来的影响,基于R树空间索引、MySQL精确空间查询,以及MPI通信机制,提出了6种不同的并行任务映射策略;通过实验分析和比较了6种策略的优劣。结果显示:基于R树预筛选的直接合并策略,在各算法中具有最高的串行计算效率和优秀的并行性能表现。虽然MySQL精确空间查询的预筛选过程较为耗时,但可有效地过滤掉不真正相交的多边形,从而提高合并操作的效率。因此,在集群MPI环境下,基于R树和MySQL精确空间查询的预筛选策略是解决并行任务映射难题,实现图层级多边形并行合并算法的有效途径。

分治法在GIS多边形快速合并算法中的应用及效率提升评价模型

分治法采用分解-解决-合并的问题处理模式,应用于多边形合并算法能规避结点累积效应,与经典的"滚雪球"处理模式相比能有效提升多边形合并算法的计算效率。本文以多边形合并算法为研究对象,首先通过分析基于Vatti算法实现的多边形合并算子的效率相对于多边形顶点数的变化特征,指出合并过程中的结点累积效应是"滚雪球"多边形合并模式的潜在性能瓶颈和隐患。考虑分治法的"分而治之"思想在解决多边形合并问题上的适用性以及在归并排序算法中表现出的高效率,提出分治法的多边形"树状"合并处理模式,实现了面向要素集合或者要素层的多边形快速合并算法,最后给出了面向多边形合并的算法效率提升评价模型。实验结果显示,当仅有400个多边形时,"滚雪球"模式的时间开销约是"树状"合并模式的26倍,当需要合并11 200个多边形时,前者的时间开销约是后者的926倍。因此,基于分治法的多边形树状合并策略是对多边形合并算法以及应用到多边形合并算法的高级空间分析算法进行优化的可行途径。

鲁棒高效的矢量地图叠加分析算法

提出了一个鲁棒高效的内存矢量地图叠加分析算法,采用改进的平面扫描算法计算交点,解决了重叠边、交点位于端点等所有特殊情形。利用交点及其携带的信息来构造结果环,并且将没有产生交点的输入环忽略,或者增加到结果的外环(或内环)集合中去。所有结果环都带有标识码,增加该标识码信息可以简化后续的两个过程—内外环的匹配以及属性的继承。与一一循环方法相比,本文方法对任何叠加操作可以一次计算得到所有的交点。此外还实现了叠加分析操作,并且用一组真实地理数据的不同操作与ESRI的ArcGIS的叠加分析操作进行了比较,计算结果的要素数完全一致;计算时间耗费约为ArcGIS时间耗费的50%—60%。