共查询到19条相似文献,搜索用时 31 毫秒
1.
2.
本文论述了与给定切线多边形相切的有理二次Bézier曲线,构造曲线是曲率连续的,具有局部可调性,且对切线多边形是保形的;跟三次(四次)Bézier曲线或B样条曲线方法相比,具有切点的变动范围更大、曲线次数低、结构简单、计算量少、显示更快的特点。最后,通过实例加以说明。 相似文献
3.
4.
梁锡坤 《计算机工程与应用》2010,46(7):155-157
针对代数曲线分段逼近的误差函数;展开深入的理论分析;给出了由误差公式确定误差界的一般算法。定义了一种新型误差;它具有几何意义直观、计算比较简单的特征。结合数值实例;验证了新型误差的实用价值。 相似文献
5.
二次曲线的多项式逼近 总被引:4,自引:4,他引:4
研究用B啨zier曲线或样条逼近任意长二次曲线弧的方法 对不同曲线类型 ,均得到具有 6阶逼近精度的误差函数 并且相邻的B啨zier曲线间GC1连续 最后给出任意二次曲线弧近似多项式或多项式样条参数化的算法 相似文献
6.
针对Bézier曲线不能精确表示圆弧,导致在基于Bézier曲线曲面造型的CAD系统中存在圆弧的Bézier曲线逼近问题,提出一种用四次Bézier曲线逼近圆弧的方法.根据圆弧与Bézier曲线都具有的对称性确定带待定参数的Bézier曲线的控制顶点;再由误差函数的零点分布情况确定待定参数,给出控制顶点的计算公式、误差的解析表达式和逼近阶.与采用已有方法得到的最好结果相比较,文中方法的逼近阶虽然也是8,但系数不到已有方法的一半,因而具有更好的逼近精度. 相似文献
7.
用三次PH曲线构造平面Bézier曲线的等距线算法 总被引:7,自引:3,他引:7
通过加入参数节点离散B啨zier曲线 ,根据原B啨zier曲线的始末端点及其切向量 ,加入节点构造一条G1 连续的三次PH样条曲线 ,以此作为原B啨zier曲线的逼近曲线 ,并进一步产生等距线 估计了原B啨zier曲线与PH样条曲线的整体逼近误差和等距线误差 相似文献
8.
9.
根据平面曲线的应变能极小原则构造了一条分段二次B啨zier样条曲线插值给定的一系列平面型值点列和端点几何约束条件 为了改进插值曲线的整体光顺性 ,提出了确定插值二次B啨zier样条曲线在每一个型值点处的最优切矢方向的一种方法 相似文献
10.
为深入挖掘有理二次Bézier曲线在[0,1]外的拓展性质,针对其标准型,研究参数趋向于∞时的极限.首先计算出极限点的位置;然后分别在椭圆和双曲线的情况下,通过比较极限点与已知点的位置、计算有理形式分母的零点、考察极限点处的切向,来探讨极限点的性质;进而得出极限点与中心、肩点共线,以及切线方向与首末控制顶点连线方向平行等结论.实例结果表明,极限点可以作为拓展部分曲线的控制顶点,从而用于整个椭圆的表示. 相似文献
11.
基于B样条的平面轮廓重构闭合曲面算法 总被引:3,自引:2,他引:3
由一组平行轮廓线重构三维闭合表面是三维可视化研究的主要内容之一.文中通过对B样条插值算法的研究,提出了一种新的公共节点矢量确定方法,利用该方法首先对经过预处理的CT牙齿图片提取轮廓线获得三维数据点,之后对轮廓线数据点进行B样条曲线的拟合,在每条拟合曲线上根据所确定的节点矢量值重新采样,由重新采样的三维数据点利用B样条曲面插值算法构造闭合曲面,所构造的闭合曲面是对原始轮廓数据的拟合.通过实例验证可看出该方法可获得较好的拟合曲面,经过误差分析检测,满足拟合条件,因此该方法可以保证几何重建的准确性. 相似文献
12.
由一组平行轮廓线重构三维闭合表面是三维可视化研究的主要内容之一。文中通过对B样条插值算法的研究,提出了一种新的公共节点矢量确定方法,利用该方法首先对经过预处理的CT牙齿图片提取轮廓线获得三维数据点,之后对轮廓线数据点进行B样条曲线的拟合,在每条拟合曲线上根据所确定的节点矢量值重新采样,由重新采样的三维数据点利用B样条曲面插值算法构造闭合曲面.所构造的闭合曲面是对原始轮廓数据的拟合。通过实例验证可看出该方法可获得较好的拟合曲面,经过误差分析检测,满足拟合条件,因此该方法可以保证几何重建的准确性。 相似文献
13.
类螺旋特征测点数据的闭曲面建模方法研究 总被引:1,自引:0,他引:1
复杂曲面及海量点云测量数据的曲面建模已成为通用CAD/CAM软件的重要功能;然而,对于复杂的闭曲面建模方法,仍然存在许多技术上的难题,至今尚未能很好的解决,比如,基于海量的测量数据,如何进行闭曲面特征点识别,如何进行区域分割与处理,这一切都使得闭曲面建模过程中很难采用已经成熟的自由曲面建模技术和方法.通过研究异步仿形测量原理以及测量数据类型,针对鞋楦测量形成的空间螺旋线数据特征,提出一种闭曲面建模方法.该方法包括如下步骤:首先对测量点数据处理;并以特征螺旋线数据为基础对曲面进行三角分割;最后,以三角Bezier曲面为基础进行曲面构造,并将各曲面进行拼接、裁剪,形成完整的曲面.采用该方法对鞋楦测量数据的建模实例说明,能够有效地对具有空间螺旋线数据特征的闭曲面进行数据处理、曲面重构,提高了产品建模效率. 相似文献
14.
We prove that any subset of ℝ2 parametrized by a C
1 periodic function and its derivative is the Euclidean invariant signature of a closed planar curve. This solves a problem
posed by Calabi et al. (Int. J. Comput. Vis. 26:107–135, 1998). Based on the proof of this result, we then develop some cautionary examples concerning the application of signature curves
for object recognition and symmetry detection as proposed by Calabi et al.
相似文献
Lorenzo NicolodiEmail: |
15.
Huaming Zhang 《Algorithmica》2010,57(2):381-397
We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular
exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations
between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium
on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik,
Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph
Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph
algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an
example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph
with n vertices in a grid of size bounded by W×H, where
W £ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor
, and
W+H £ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor
. It uses at most
?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor
bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline
drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts
in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2). 相似文献
16.
Abstract. We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance. 相似文献
17.
Eric Allender David A. Mix Barrington Tanmoy Chakraborty Samir Datta Sambuddha Roy 《Theory of Computing Systems》2009,45(4):675-723
We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for
. In particular, we focus on different classes of planar graphs, of which grid graphs are an important special case. Our main results are:
E. Allender supported in part by NSF Grant CCF-0514155.
D.A. Mix Barrington supported in part by NSF Grant CCR-9988260.
S. Roy supported in part by NSF Grant CCF-0514155. 相似文献
• | Reachability in graphs of genus one is logspace-equivalent to reachability in grid graphs (and in particular it is logspace-equivalent to both reachability and non-reachability in planar graphs). |
• | Many of the natural restrictions on grid-graph reachability (GGR) are equivalent under reductions (for instance, undirected GGR, outdegree-one GGR, and indegree-one-outdegree-one GGR are all equivalent). These problems are all equivalent to the problem of determining whether a completed game position in HEX is a winning position, as well as to the problem of reachability in mazes studied by Blum and Kozen (IEEE Symposium on Foundations of Computer Science (FOCS), pp. 132–142, [1978]). These problems provide natural examples of problems that are hard for under reductions but are not known to be hard for ; they thus give insight into the structure of . |
• | Reachability in layered planar graphs is logspace-equivalent to layered grid graph reachability (LGGR). We show that LGGR lies in (a subclass of ). |
• | Series-Parallel digraphs (on which reachability was shown to be decidable in logspace by Jakoby et al.) are a special case of single-source-single-sink planar directed acyclic graphs (DAGs); reachability for such graphs logspace reduces to single-source-single-sink acyclic grid graphs. We show that reachability on such grid graphs reduces to undirected GGR. |
• | We build on this to show that reachability for single-source multiple-sink planar DAGs is solvable in . |
18.
19.
We present a new scheme for storing a planar graph in external memory so that any online path can be traversed in an I-O efficient way. Our storage scheme significantly improves the previous results for planar graphs with bounded face size. We also prove an upper bound on I-O efficiency of any storage scheme for well-shaped triangulated meshes. For these meshes, our storage scheme achieves optimal performance. 相似文献