Designed TINs arise in engineering and surveying models, whereas derived TINs are typically programmatically generated from grid-based datasets (digital elevation models or DEMs).Īlthough such TINs could be generated by selecting vertices using key feature extraction and surface modeling, a simpler and faster approach is to systematically divide the entire region into more and more triangles based on simple subdivision rules. The nodes or vertices of these triangles can be placed closer together where landscape detail is more complex and further apart where surfaces are simpler. Areas that have similar slope could be better represented and stored using a series of inter-connected triangles forming an irregular mesh or network (a TIN). Regular lattices such as grids provide a very inefficient means of storing details of surface topography. The set of lines (edges) that belongs to all possible furthest site Delaunay triangulations is known as a Delaunay diagram, and has important applications in network analysis (see further, Chapter 7, Network and Location Analysis).įigure 4‑32 Delaunay triangulation of spot height locations If all points included in the Delaunay triangulation of a set P also lie on the convex hull of P the result is known as a furthest point Delaunay triangulation. For example, when modeling a surface there may be important breaks of surface continuity or surveyed transects which it is highly desirable to include within the dataset, which are not captured by simple Delaunay-type procedures (as noted in Section 4.2.13, Boundaries and zone membership) this procedure is by no means the only, or necessarily the best method of triangulation for all purposes.here) may lie outside the triangle in question, as is the case with one of the circles illustrated.the center of the circumscribing circle (marked with a.long thin triangles with acute angles do occur using this procedure, although the number and severity of these is minimized compared to other triangulations.four points at the corners of a square or rectangle) multiple Delaunay triangulations are possible, hence to this extent it is not unique However, with some point set arrangements (e.g. this triangulation is unique in the sense that it is the only triangulation of the point set that satisfies the rule described above.Worboys and Duckham (2004, pp 202-207) provide a useful discussion of triangulation algorithms.Ī number of other observations should be made about this process: The circles illustrate how the circle circumscribing each triangle has no other points from the set within it. Many programs support the creation of the triangulation required, for example the delaunay( x, y) function in MATLab where x, and y are n x1 vectors containing the coordinates of all the points, or (as here) the Grid Data operation in Surfer, using the option to export the triangulation used as a base map. Each location is represented by an ( x,y) pair. Figure 4‑32, below, illustrates this process for a set of spot height locations in a small area south of Edinburgh in Scotland (GB Ordnance Survey tile NT04). This states that three points form a Delaunay Triangulation if and only if ( iff) a circle which passes through all three points contains no other points in the set. To ensure the triangulation will have the best chance of meeting the characteristics desired, a construction rule was devised by the mathematician Delaunay. It has also been found that a desirable characteristic of such triangulations is that long thin triangles with very acute internal angles are to be avoided in order to provide the best framework for measurement and analysis. It has long been known that triangulation provides a secure method for locating points on the Earth’s surface by field survey. Given a set of points in the plane, P, lines may be drawn between these points to create a complete set of non-overlapping triangles (a triangulation) with the outer boundary being the convex hull of the point set. GIS does make extensive use of irregular triangular tessellations, both for division of plane regions and as an efficient means of representing surfaces. Regular triangular and hexagonal grids are also possible in the plane but are rarely implemented in software packages. Within GIS regular tiles are almost always either square or rectangular, and form a (continuous) grid structure. As we noted in Table 1‑1 a (regular or irregular) tessellation of a plane involves the subdivision of the plane into polygonal tiles that completely cover it. A region may be divided into a set of non-overlapping areas in many ways.
0 Comments
Leave a Reply. |