基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发，首次提出窗口顶点编码的新概念。以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域，从而快速完成多边形窗口顶点编码。通过窗口顶点编码与传统的线段编码相结合，无须求交即可快速排除大部分窗外线段；进一步可以直接得到与直线相交的窗口边，加快了求交进程。更有意义的是，通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况：裁剪直线通过多边形的顶点、裁剪直线通过多边形的边。实验结果表明，新算法提高了裁剪效率并具有很好的稳定性。     

基于编码与分类技术的任意多边形裁剪新算法

首次将编码与分类技术引入任意多边形的矩形窗口裁剪,通过编码分类技术根据多边形边与裁剪窗口的相对位置将边分为六类。采用一次编码技术获取一类窗内边,舍弃二类窗外边,得到必须求交的三类边;采用二次编码技术舍弃四类窗外边,得到需要求交的五、六类边;进一步提出裁剪窗口顶点相对于多边形的分类,利用窗口顶点分类和多边形边的编码特征快速处理三类、五类、六类窗口相交边。通过编码分类技术减少了多边形裁剪的运算量,并有效地维护了多边形的拓扑关系。实验结果表明算法稳定可靠,可实现对任意凹凸多边形的裁剪,在多边形与窗口的各种相对位置均具有较高的运算效率。     

基于交点参数的任意多边形窗口对圆裁剪

现有的任意多边形窗口的圆裁剪算法存在算法繁琐等问题,且没有考虑多边形是带内环的情况,本文提出了一种基于交点参数分析的多边形窗口的圆裁剪算法,只需对多边形边与圆的交点在边所在直线的参数值进行比较,即可判断出交点的进出点特性,交点排序后,通过进点?出点组合,即可获得裁剪窗口内的圆弧,完成裁剪.编程实践的实例结果也证明本算法是切实可行的,本文的方法既适用于仅有外环的一般多边形裁剪窗口,也适用于带内环的任意多边形裁剪窗口的圆裁剪,因此,算法更具有通用性.     

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

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

基于圆形窗口的简单多边形填充算法

提出了一种新颖而实用的圆形窗口简单多边形填充算法，它具有快速裁剪与填充双重功能，也可完成单纯地裁剪功能，该算法将多边形的边视为有向线段，通过引入多边形顶点的入边和出边产我点的概念，深入研究了多这形被圆形窗口裁剪后区域的确定性填充问题，使截剪功能隐含于填充过程中，从而节省了填充之前的裁剪过程。     

基于圆形窗口的简单多边形裁剪算法

提出了一种新颖而实用的圆形窗口Ｖ对多边形Ｐ的裁剪算法。它将多边形Ｐ的边视为有向线段，通过引入多边形顶点的入边和出边交点的概念，深入研究了Ｐ被Ｖ裁剪后的区域确定问题，给出了作出Ｐ在Ｖ内部分的定理     

无重迭边的可重入多边形裁剪算法

本文提出一种在标准 Sutherland—Hodgman 多边形裁剪算法基础上扩充的重迭边消去算法。本算法在沿着窗口边沿直线对多边形的各边进行裁剪的时候,建立了一个中间结果顶点队列和一个交点队列,然后通过顶点追溯方法产生出作为裁剪结果的一列子多边形.这些子多边形的定义方式与输入多边形相同,不存在重迭的边,而且仍然保持可重入性.     

C—F填图法—一种集修剪与填充功能于一体的算法

本文提出了一种新的填图算法,其集修剪与填充功能于一体,当阴影线间隔d≥t-b时(t,b分别为窗口的上、下边线值),则可完成单纯的修剪功能.同传统的AET算法不同,本算法着眼于多边形的顶点,且将多边形的边视为有向线段,分别为某一顶点的入边或出边.本文给出了有关的一些定义,及作出多边形P在窗口V之内部分的定理.     

线点包容检测算法

提出的算法是先以快速的方法判断线与多边形是否有交点,如有,则求出线与多边形的各个交点,将交点进行排序,将此线按交点顺序分为多段;如果无交点,则此线只有一段。检测各段中点是否位于多边形内,如果位于内部,则此段在内,否则此段在外。以倾斜射线法检测点的包容性,其特点是此射线不与多边形的顶点或边重合,无须作特殊情况的处理,计算区域小,因而计算量小,对自相交多边形及带孔多边形等多类情况同样适用。通过编写程序计算验证表明,此算法简单有效、稳定可靠,适用于多类情况。     

快速多边形区域三角化算法与实现 *

多边形区域三角化的基本思想是 :首先将简单多边形分解为多个单调多边形 ,然后对每个单调多边形进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型 ,并沿指定方向对顶点进行排序 ,然后顺序取出各顶点 ,根据顶点类型 ,确定准单调多边形的产生、增长或结束 ,最后对所产生的多个单调多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系 ,计算量少、实现简单 ,适用于带有洞、岛的任意简单多边形 ,速度较快。     

勾画式交互的网格模型分割

提出一种基于区域增长的交互三维网格模型分割方法。在区域增长的基础上,首先由用户利用基于勾画的交互方式选定部分顶点作为目标和背景,其余顶点作为未知区域,利用区域增长的方法自动生成目标的边界,从而完成模型的分割。此方法中边界顶点分割结果的好坏直接影响到了最终的分割结果,因此,在利用区域增长方法形成边界时,将既与目标相邻又与背景相邻的顶点标记为特殊点,在其余未知部分分割完成之后,重新对特殊点进行一次区域增长算法。此时由于大部分顶点的状态已经确定,获得的边界将更为准确。实验表明分割结果有了很大程度的改进。     

Control of limit states in absorbing resource networks

This paper studies the properties of resource networks with sink vertices called absorbing resource networks. In the presence of at least two sinks, the resource distribution in the limit state depends on the initial state of the network. We formulate two control problems in such networks. Sinks are treated as goal vertices. Control vertices represent some subset of vertices in the transition component.     

骨粒串主导的自由曲面变形算法

由于目前广泛应用的骨骼子空间变形算法本身固有的缺陷，常常导致生成的曲面出现“塌陷”与“萎缩”，严重影响了生成曲面的真实感．提出一种骨粒串主导的自由曲面变形算法，通过重构曲面模型，将骨骼与曲面相结合，并把虚拟的骨骼实体化，成为可变形的骨粒串．变形时先计算每一骨粒的新坐标，然后计算相应皮肤顶点的新坐标．实验结果表明，该算法有效地消除了“塌陷”与“萎缩”，生成的曲面具有高度真实感．     

Parameterized complexity of firefighting

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b?1$b?1$ firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.     

A review of: “A Manager's Guide to Ergonomics in the Electronic Office. By MARVIN J. DAINOFF and MARILYN HECHT DAINOFF (Chichester John Wiley and Sons, 1987.) [Pp. xii + 230.] £19·95.

When polygon displays are used to represent multiple sources of information, sometimes they can be processed in parallel so that the significant information can be taken in ‘at a glance’. Previous studies found that reaction times (RTs) remained constant as the number of vertices was increased (Greaney and MacRae 1993). However, these studies did not call for the explicit identification of critical vertices and used polygons that were relatively regular. The present study required abnormal vertices to be identified, and it was found that RTs increased as a function of the total number of vertices. In addition, RTs were longer when the variability of the displayed information was greater, that is, when the polygon was more irregular. It was concluded that the polygon display may have more potential as a global warning indicator than as a means of displaying individual parameter values, which must be assessed separately.     

多级划分算法的后处理与评价方法

多级划分算法需要进行多次实验以得到最优值.本文根据网表顶点在多次实验中的倾向性将其分为:活跃点、固定点和亚固定点,并提出只对活跃点重新划分的后处理方法.另外,通过将固定点和亚固定点分配到相应簇中,得到一种算法评价方法.实验表明,本文的后处理方法可有效减小hMetis算法的最小割,而评价方法能够客观评价hMetis算法在不同聚类策略下的划分结果.     

Pebble games for studying storage sharing

Pebble games are played on a directed acyclic graph (dag). Placing a pebble on a vertex may be thought of as entering the value of the subexpression represented by the vertex into accessible storage. In some applications, there are types associated with vertices e.g. some vertices may represent functions, others may represent function values. We are interested in determining if vertices of the same type can share storage. The problem considered is as follows. We are given a labelled dag to be pebbled. A pebble may be placed on a vertex if all sons of the vertex have pebbles—in fact it is legal to move a pebble from a son to a father. Pebbles may be picked up at any time. The objective is to pebble each vertex exactly once. We will be interested in ‘one pebblings of l vertices’ in which there is at most one pebble on vertices with label l, at all times; and ‘stack pebblings of l vertices’ in which the pebbled vertices with label l are along a path, at all times. Results about the existence of such pebblings are presented. The results have applications to testing serializability of database updates, and potential applications to semantics directed compiler generation.     

Hypergraph recovery algorithms from a given vector of vertex degrees

Methods of obtaining certain classes of hypergraphs from a given integer vector of vertex degrees are considered. These classes are as follows: hyperedges with unit weight incident upon k vertices; hyperedges with unit weight incident upon k vertices in the case when the vertices may be non-unique; multiple hyperedges incident upon k vertices; and arbitrary hypergraph in which the edges can contain any set of k vertices. For each of these classes, an algorithm is proposed for constructing the hypergraph from an arbitrary vector. If the construction is impossible, the algorithm determines how much the vector should be reduced so that the hypergraph could be constructed.     

Minimum Degree Orderings

It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called a flat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.     

基于衍生多边形的混合坐标

将多边形三角化,利用三角网格将三角形衍生为点多边形、边多边形和面多边形,再根据已有的重心坐标提出基于衍生多边形的混合坐标.首先在三角网格内根据初始多边形内部一点所在的三角形得到衍生多边形,然后使用调和坐标、局部重心坐标、迭代坐标中任意一种计算衍生多边形的顶点关于初始多边形顶点的重心坐标,再使用迭代坐标计算初始多边形内部...