SEARCH · Search NASA

Results for “TRIANGULATION”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records

All sources NASA NTRS DOE OSTI

NASA NTRS1979

A fast, space-efficient average-case algorithm for the 'Greedy' Triangulation of a point set, and a proof that the Greedy Triangulation is not approximately optimal

The paper addresses the problem of how to find the Greedy Triangulation (GT) efficiently in the average case. It is noted that the problem is open whether there exists an efficient approximation algorithm to the Optimum Triangulation. It is first shown how in the worst case, the GT may be obtained in time O(n to the 3) and space O(n). Attention is then given to how the algorithm may be slightly modified to produce a time O(n to the 2), space O(n) solution in the average case. Finally, it is mentioned that Gilbert has found a worst case solution using totally different techniques that require space O(n to the 2) and time O(n to the 2 log n).

Manacher, G. K.↗

NASA NTRS1994

Incremental triangulation by way of edge swapping and local optimization

This document is intended to serve as an installation, usage, and basic theory guide for the two dimensional triangulation software 'HARLEY' written for the Silicon Graphics IRIS workstation. This code consists of an incremental triangulation algorithm based on point insertion and local edge swapping. Using this basic strategy, several types of triangulations can be produced depending on user selected options. For example, local edge swapping criteria can be chosen which minimizes the maximum interior angle (a MinMax triangulation) or which maximizes the minimum interior angle (a MaxMin or Delaunay triangulation). It should be noted that the MinMax triangulation is generally only locally optical (not globally optimal) in this measure. The MaxMin triangulation, however, is both locally and globally optical. In addition, Steiner triangulations can be constructed by inserting new sites at triangle circumcenters followed by edge swapping based on the MaxMin criteria. Incremental insertion of sites also provides flexibility in choosing cell refinement criteria. A dynamic heap structure has been implemented in the code so that once a refinement measure is specified (i.e., maximum aspect ratio or some measure of a solution gradient for the solution adaptive grid generation) the cell with the largest value of this measure is continually removed from the top of the heap and refined. The heap refinement strategy allows the user to specify either the number of cells desired or refine the mesh until all cell refinement measures satisfy a user specified tolerance level. Since the dynamic heap structure is constantly updated, the algorithm always refines the particular cell in the mesh with the largest refinement criteria value. The code allows the user to: triangulate a cloud of prespecified points (sites), triangulate a set of prespecified interior points constrained by prespecified boundary curve(s), Steiner triangulate the interior/exterior of prespecified boundary curve(s), refine existing triangulations based on solution error measures, and partition meshes based on the Cuthill-McKee, spectral, and coordinate bisection strategies.

Wiltberger, N. Lyn↗

NASA NTRS1985

Some properties of n-dimensional triangulations

A number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplicial tessellation, of the convex hull of an arbitrary finite set of points in n-space are described. The principal results achieved are: (1) a set of n+2 points in n-space may be triangulated in at most 2 different ways; (2) the sphere test defined in this report selects a preferred one of these two triangulations; (3) a set of parameters is defined that permits the characterization and enumeration of all sets of n+2 points in n-space that are significantly different from the point of view of their possible triangulation; (4) the local sphere test induces a global sphere test property for a triangulation; and (5) a triangulation satisfying the global sphere property is dual to the n-dimensional Dirichlet tesselation, i.e., it is a Delaunay triangulation.

Lawson, C. L.↗

NASA NTRS1998

Automatic Generation of CFD-Ready Surface Triangulations from CAD Geometry

This paper presents an approach for the generation of closed manifold surface triangulations from CAD geometry. CAD parts and assemblies are used in their native format, without translation, and a part's native geometry engine is accessed through a modeler-independent application programming interface (API). In seeking a robust and fully automated procedure, the algorithm is based on a new physical space manifold triangulation technique which was developed to avoid robustness issues associated with poorly conditioned mappings. In addition, this approach avoids the usual ambiguities associated with floating-point predicate evaluation on constructed coordinate geometry in a mapped space, The technique is incremental, so that each new site improves the triangulation by some well defined quality measure. Sites are inserted using a variety of priority queues to ensure that new insertions will address the worst triangles first, As a result of this strategy, the algorithm will return its 'best' mesh for a given (prespecified) number of sites. Alternatively, the algorithm may be allowed to terminate naturally after achieving a prespecified measure of mesh quality. The resulting triangulations are 'CFD-ready' in that: (1) Edges match the underlying part model to within a specified tolerance. (2) Triangles on disjoint surfaces in close proximity have matching length-scales. (3) The algorithm produces a triangulation such that no angle is less than a given angle bound, alpha, or greater than Pi - 2alpha This result also sets bounds on the maximum vertex degree, triangle aspect-ratio and maximum stretching rate for the triangulation. In addition to tile output triangulations for a variety of CAD parts, tile discussion presents related theoretical results which assert the existence of such all angle bound, and demonstrate that maximum bounds of between 25 deg and 30 deg may be achieved in practice.

Aftosmis, M. J.↗

NASA NTRS1972

Improvement of a geodetic triangulation through control points established by means of satellite or precision traversing

Whether any significant increment to accuracy could be transferred from a super-control continental net (continental satellite net or super-transcontinental traverse) to the fundamental geodetic net (first-order triangulation) is discussed. This objective was accomplished by evaluating the positional accuracy improvement for a triangulation station, which is near the middle of the investigated geodetic triangulation net, by using various station constraints over its geodetic position. This investigation on a 1858 kilometer long triangulation chain shows that the super-control net can provide a useful constraint to the investigated geodetic triangulation net, and thus can improve it only when the accuracy of super-control net is at least 1 part in 500,000.

Saxena, N. K.↗

NASA NTRS1977

Planimetric Martian triangulations

Narrow-angle photographs, which have severe drawbacks for stereophotogrammetry, have advantages for simple plane triangulations. Rectified narrow-angle pictures corrected for map projection effects can be combined in the map plane in relatively accurate planimetric triangulations. Provided the strict precepts of least squares are not followed, these triangulations can incorporate considerable overdetermination without increase in the labor of solving the equations. These plane triangulations have been used successfully in the cartography of Mars and are illustrated here by a triangulation of the environs of the prime Martian landing site.

Arthur, D. W. G.↗

NASA NTRS1986

Properties of n-dimensional triangulations

This paper establishes a number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplical tessellation of the convex hull of an arbitrary finite set of points in n-space. The principal results of the present paper are: (1) a set of n + 2 points in n-space may be triangulated in at most 2 different ways; (2) the 'sphere test' defined in this paper selects a preferred one of these two triangulations; (3) a set of parameters is defined that permits the characterization and enumeration of all sets on n + 2 points in n-space that are significantly different from the point of view of their possible triangulations; and (4) the local sphere test induces a global sphere test property for a triangulation.

Lawson, Charles L.↗

NASA NTRS1991

Triangulation using synthetic aperture radar images

For the extraction of topographic information about Venus from stereoradar images obtained from the Magellan Mission, a Synthetic Aperture Radar (SAR) compilation system was developed on analytical stereoplotters. The system software was extensively tested by using stereoradar images from various spacecraft and airborne radar systems, including Seasat, SIR-B, ERIM XCL, and STAR-1. Stereomodeling from radar images was proven feasible, and development is on a correct approach. During testing, the software was enhanced and modified to obtain more flexibility and better precision. Triangulation software for establishing control points by using SAR images was also developed through a joint effort with the Defense Mapping Agency. The SAR triangulation system comprises four main programs, TRIDATA, MODDATA, TRISAR, and SHEAR. The first two programs are used to sort and update the data; the third program, the main one, performs iterative statistical adjustment; and the fourth program analyzes the results. Also, input are flight data and data from the Global Positioning System and Inertial System (navigation information). The SAR triangulation system was tested with six strips of STAR-1 radar images on a VAX-750 computer. Each strip contains images of 10 minutes flight time (equivalent to a ground distance of 73.5 km); the images cover a ground width of 22.5 km. All images were collected from the same side. With an input of 44 primary control points, 441 ground control points were produced. The adjustment process converged after eight iterations. With a 6-m/pixel resolution of the radar images, the triangulation adjustment has an average standard elevation error of 81 m. Development of Magellan radargrammetry will be continued to convert both SAR compilation and triangulation systems into digital form.

Wu, Sherman S. C.↗

NASA NTRS1992

Delaunay triangulation and computational fluid dynamics meshes

In aerospace computational fluid dynamics (CFD) calculations, the Delaunay triangulation of suitable quadrilateral meshes can lead to unsuitable triangulated meshes. Here, we present case studies which illustrate the limitations of using structured grid generation methods which produce points in a curvilinear coordinate system for subsequent triangulations for CFD applications. We discuss conditions under which meshes of quadrilateral elements may not produce a Delaunay triangulation suitable for CFD calculations, particularly with regard to high aspect ratio, skewed quadrilateral elements.

Posenau, Mary-Anne K.↗

NASA NTRS1993

Approaches to high aspect ratio triangulations

In aerospace computational fluid dynamics calculations, high aspect ratio, or stretched, triangulations are necessary to adequately resolve the features of a viscous flow around bodies. In this paper, we explore alternatives to the Delaunay triangulation which can be used to generate high aspect ratio triangulations of point sets. The method is based on a variation of the lifting map concept which derives Delaunay triangulations from convex hull calculations.

Posenau, M.-A.↗

DOE OSTI2014

Extending particle tracking capability with Delaunay triangulation

Here, particle tracking, the analysis of individual moving elements in time series of microscopic images, enables burgeoning new applications, but there is need to better resolve conformation and dynamics. Here we describe the advantages of Delaunay triangulation to extend the capabilities of particle tracking in three areas: (1) discriminating irregularly shaped objects, which allows one to track items other than point features; (2) combining time and space to better connect missing frames in trajectories; and (3) identifying shape backbone. To demonstrate the method, specific examples are given, involving analyzing the time-dependent molecular conformations of actin filaments and λ-DNA. The main limitation of this method, shared by all other clustering techniques, is the difficulty to separate objects when they are very close. This can be mitigated by inspecting locally to remove edges that are longer than their neighbors and also edges that link two objects, using methods described here, so that the combination of Delaunay triangulation with edge removal can be robustly applied to processing large data sets. As common software packages, both commercial and open source, can construct Delaunay triangulation on command, the methods described in this paper are both computationally efficient and easy to implement.

36 MATERIALS SCIENCE↗

DOE OSTI2014

Tracking the CME-driven shock wave on 2012 March 5 and radio triangulation of associated radio emission

We present a multiwavelength study of the 2012 March 5 solar eruptive event, with an emphasis on the radio triangulation of the associated radio bursts. The main points of the study are reconstruction of the propagation of shock waves driven by coronal mass ejections (CMEs) using radio observations and finding the relative positions of the CME, the CME-driven shock wave, and its radio signatures. For the first time, radio triangulation is applied to different types of radio bursts in the same event and performed in a detailed way using goniopolarimetric observations from STEREO/Waves and WIND/Waves spacecraft. The event on 2012 March 5 was associated with a X1.1 flare from the NOAA AR 1429 situated near the northeast limb, accompanied by a full halo CME and a radio event comprising long-lasting interplanetary type II radio bursts. The results of the three-dimensional reconstruction of the CME (using SOHO/LASCO, STEREO COR, and HI observations), and modeling with the ENLIL cone model suggest that the CME-driven shock wave arrived at 1 AU at about 12:00 UT on March 7 (as observed by SOHO/CELIAS). The results of radio triangulation show that the source of the type II radio burst was situated on the southern flank of the CME. We suggest that the interaction of the shock wave and a nearby coronal streamer resulted in the interplanetary type II radio emission.

79 ASTRONOMY AND ASTROPHYSICS↗

NASA NTRS1973

Triangulation Error Analysis for the Barium Ion Cloud Experiment

The triangulation method developed specifically for the Barium Ion Cloud Project is discussed. Expression for the four displacement errors, the three slope errors, and the curvature error in the triangulation solution due to a probable error in the lines-of-sight from the observation stations to points on the cloud are derived. The triangulation method is then used to determine the effect of the following on these different errors in the solution: the number and location of the stations, the observation duration, east-west cloud drift, the number of input data points, and the addition of extra cameras to one of the stations. The pointing displacement errors, and the pointing slope errors are compared. The displacement errors in the solution due to a probable error in the position of a moving station plus the weighting factors for the data from the moving station are also determined.

Long, S. A. T.↗

NASA NTRS1992

An advancing front Delaunay triangulation algorithm designed for robustness

A new algorithm is described for generating an unstructured mesh about an arbitrary two-dimensional configuration. Mesh points are generated automatically by the algorithm in a manner which ensures a smooth variation of elements, and the resulting triangulation constitutes the Delaunay triangulation of these points. The algorithm combines the mathematical elegance and efficiency of Delaunay triangulation algorithms with the desirable point placement features, boundary integrity, and robustness traditionally associated with advancing-front-type mesh generation strategies. The method offers increased robustness over previous algorithms in that it cannot fail regardless of the initial boundary point distribution and the prescribed cell size distribution throughout the flow-field.

Mavriplis, D. J.↗

NASA NTRS1993

An advancing front Delaunay triangulation algorithm designed for robustness

Mavriplis, D. J.↗

NASA NTRS1988

A stereo triangulation system for structural identification: Analytical and experimental results

Identification of large space structures' distributed mass, stiffness, and energy dissipation characteristics poses formidable analytical, numerical, and implementation difficulties. Development of reliable on-orbit structural identification methods is important for implementing active vibration suppression concepts which are under widespread study in the large space structures community. Near the heart of the identification problem lies the necessity of making a large number of spatially distributed measurements of the structure's vibratory response and the associated force/moment inputs with sufficient spatial and frequency resolution. In the present paper, we discuss a method whereby tens of active or passive (retro-reflecting) targets on the structure are tracked simultaneously by the focal planes of two or more video cameras mounted on an adjacent platform. Triangulation (optical ray intersection) of the conjugate image centroids yield inertial trajectories of each target on the structure. Given the triangulated motion of the targets, we apply and extend methodology developed by Creamer, Junkins, and Juang to identify the frequencies, mode shapes, and updated estimates for the mass/stiffness/damping parameterization of the structure. The methodology is semi-automated, for example, the post experiment analysis of the video imagery to determine the inertial trajectories of the targets typically requires less than thirty minutes of real time. Using methodology discussed herein, the frequency response of a large number of points on the structure (where reflective targets are mounted) on the structure can be determined from optical measurements alone. For comparison purposes, we also utilize measurements from accelerometers and a calibrated impulse hammer. While our experimental work remains in a research stage of development, we have successfully tracked and stereo triangulated 20 targets (on a vibrating cantilevered grid structure) at a sample frequency of 200 HZ, and have established conclusively the feasibility and desirability of this approach. We discuss, in summary, recent advances in analog and digital video processing methodology, actuation methods, and bring them to bear on the structural identification problem. We include a brief discussion of our experimental hardware and some recent experimental results which support the practical feasibility of this structural vibration sensing approach.

Junkins, J. L.↗

NASA NTRS1995

Algorithms for high aspect ratio oriented triangulations

Grid generation plays an integral part in the solution of computational fluid dynamics problems for aerodynamics applications. A major difficulty with standard structured grid generation, which produces quadrilateral (or hexahedral) elements with implicit connectivity, has been the requirement for a great deal of human intervention in developing grids around complex configurations. This has led to investigations into unstructured grids with explicit connectivities, which are primarily composed of triangular (or tetrahedral) elements, although other subdivisions of convex cells may be used. The existence of large gradients in the solution of aerodynamic problems may be exploited to reduce the computational effort by using high aspect ratio elements in high gradient regions. However, the heuristic approaches currently in use do not adequately address this need for high aspect ratio unstructured grids. High aspect ratio triangulations very often produce the large angles that are to be avoided. Point generation techniques based on contour or front generation are judged to be the most promising in terms of being able to handle complicated multiple body objects, with this technique lending itself well to adaptivity. The eventual goal encompasses several phases: first, a partitioning phase, in which the Voronoi diagram of a set of points and line segments (the input set) will be generated to partition the input domain; second, a contour generation phase in which body-conforming contours are used to subdivide the partition further as well as introduce the foundation for aspect ratio control, and; third, a Steiner triangulation phase in which points are added to the partition to enable triangulation while controlling angle bounds and aspect ratio. This provides a combination of the advancing front/contour techniques and refinement. By using a front, aspect ratio can be better controlled. By using refinement, bounds on angles can be maintained, while attempting to minimize the number of Steiner points.

Posenau, Mary-Anne K.↗

NASA NTRS1998

A Parallel Non-Overlapping Domain-Decomposition Algorithm for Compressible Fluid Flow Problems on Triangulated Domains

This paper considers an algebraic preconditioning algorithm for hyperbolic-elliptic fluid flow problems. The algorithm is based on a parallel non-overlapping Schur complement domain-decomposition technique for triangulated domains. In the Schur complement technique, the triangulation is first partitioned into a number of non-overlapping subdomains and interfaces. This suggests a reordering of triangulation vertices which separates subdomain and interface solution unknowns. The reordering induces a natural 2 x 2 block partitioning of the discretization matrix. Exact LU factorization of this block system yields a Schur complement matrix which couples subdomains and the interface together. The remaining sections of this paper present a family of approximate techniques for both constructing and applying the Schur complement as a domain-decomposition preconditioner. The approximate Schur complement serves as an algebraic coarse space operator, thus avoiding the known difficulties associated with the direct formation of a coarse space discretization. In developing Schur complement approximations, particular attention has been given to improving sequential and parallel efficiency of implementations without significantly degrading the quality of the preconditioner. A computer code based on these developments has been tested on the IBM SP2 using MPI message passing protocol. A number of 2-D calculations are presented for both scalar advection-diffusion equations as well as the Euler equations governing compressible fluid flow to demonstrate performance of the preconditioning algorithm.

Barth, Timothy J.↗