Search

Abstract: This paper presents a numerically stable solution to a point-in-polygon problem by combining the orientation method and the uniform subdivision technique. We define first a quasi-closest point that can be locally found through the uniform subdivision cells, and then we provide the criteria for determining whether a point lies inside a polygon according to the quasi-closest point. For a large number of points to be tested against the same polygon, the criteria are employed to determine the inclusion property of an empty cell as well as a test point. The experimental tests show that the new method resolves the singularity of a test point on an edge without loss of efficiency. The GIS case study also demonstrates the capability of the method to identify which region contains a test point in a map. [Copyright &y& Elsevier]

Abstract: A novel and efficient quasi-Monte Carlo method for computing the area of a point-sampled surface with associated surface normal for each point is presented. Our method operates directly on the point cloud without any surface reconstruction procedure. Using the Cauchy–Crofton formula, the area of the point-sampled surface is calculated by counting the number of intersection points between the point cloud and a set of uniformly distributed lines generated with low-discrepancy sequences. Based on a clustering technique, we also propose an effective algorithm for computing the intersection points of a line with the point-sampled surface. By testing on a number of point-based models, experiments suggest that our method is more robust and more efficient than those conventional approaches based on surface reconstruction. [Copyright &y& Elsevier]

Abstract: An unstructured tetrahedral mesh generation algorithm for 3D model with constraints is presented. To automatically generate a tetrahedral mesh for model with constraints, an advancing front algorithm is presented based on conforming constrained Delaunay tetrahedralization (CCDT). To reduce the number of visibility tests between vertices with respect to model faces as well as the computation of constrained Delaunay tetrahedra, a sufficient condition for DT (constrained Delaunay tetrahedralization whose simplexes are all Delaunay) existence is presented and utilized coupled to uniform grid and advancing front techniques in our algorithm. The mesh generator is robust and exhibits a linear time complexity for mechanical models with uniform density distribution. [Copyright &y& Elsevier]

The purpose of this paper is to provide yet another solution to a fundamental problem in computer aided geometric design, i.e., constructing a smooth curve satisfying given endpoint (position and tangent) conditions. A new class of curves, called optimized geometric Hermite (OGH) curves, is introduced. An OGH curve is defined by optimizing the magnitudes of the endpoint tangent vectors in the Hermite interpolation process so that the strain energy of the curve is a minimum. An OGH curve is not only mathematically smooth, i.e., with minimum strain energy, but also geometrically smooth, i.e., loop-, cusp- and fold-free if the geometric smoothness conditions and the tangent direction preserving conditions on the tangent angles are satisfied. If the given tangent vectors do not satisfy the tangent angle constraints, one can use a 2-segment or a 3-segment composite optimized geometric Hermite (COH) curve to meet the requirements. Two techniques for constructing 2-segment COH curves and five techniques for constructing 3-segment COH curves are presented. These techniques ensure automatic satisfaction of the tangent angle constraints for each OGH segment and, consequently, mathematical and geometric smoothness of each segment of the curve. The presented OGH and COH curves, combined with symmetry-based extension schemes, cover tangent angles of all possible cases. The new method has been compared with the high-accuracy Hermite interpolation method by de Boor et al. and the Pythagorean-hodograph (PH) curves by Farouki et al. While the other two methods both would generate unpleasant shapes in some cases, the new method generates satisfactory shapes in all the cases. [Copyright &y& Elsevier]

Abstract: Fat arcs form bounding boxes for planar curves. An example on approximation by fat arcs, provided by Qun and Rokne, is corrected. The third derivative of the given curve segment under the polar coordinate system is increasing only at the beginning of the curve segment, and then decreasing, rather than monotonically increasing for the whole curve segment. Some numerical data are corrected as well. [Copyright &y& Elsevier]

Abstract: This paper proposes a second order geometric iteration algorithm for point projection and inversion on parametric surfaces. The iteration starts from an initial projection estimation. In each iteration, we construct a second order osculating torus patch to the parametric surface at the previous projection. Then we project the test point onto the torus patch to compute the next projection and its parameter. This iterative process is terminated when the parameter satisfies the required precision. Experiments demonstrate the convergence speed of our algorithm. [Copyright &y& Elsevier]

Abstract: Dynamic partial differential equation (PDE) parametric curves which can be expressed as a coupled system of two hyperbolic equations are developed. In curve design, dynamic PDE parametric curves can be modified intuitively and are more flexible than ordinary differential equation (ODE) curves. The calculation of dynamic PDE parametric curves must recur to numerical methods and a three-level finite difference scheme is proposed. Approximation and stability properties for the scheme are proved and convergence property is derived. An example of interpolating PDE curves is presented as an application of dynamic PDE parametric curves. [Copyright &y& Elsevier]