Search

This paper presents a novel approach to handle large amounts of geometric data. A data stream clustering is used to reduce the amount of data and build a hierarchy of clusters. The data stream concept allows for the processing of very large data sets. The cluster hierarchy is then used in a dynamic triangulation to create a multiresolution model. It allows for the interactive selection of a different level of detail in various parts of the data. A method for removal multiple points from Delaunay triangulation is proposed. It is significantly faster than the traditional approach. The clustering and the triangulation are supplemented by an elliptical metric to handle data with anisotropic properties. Compared to the closest competitive method by Isenburg et al., the presented algorithm requires only a single pass over the data and offers a high flexibility. These advantages culminate in a long running time. The method was tested on several large digital elevation maps. The clustering phase can take up to a few hours. Once the cluster hierarchy is built, the terrains can be efficiently manipulated in real time.

Contour lines are an important means of cartographical visualization. If computed automatically on a triangulation, they contain many artefacts. This paper shows the results of their elimination by using constrained edges in the triangulation. Constrained edges can be inserted either manually by an editor - which enables all kinds of detected artefacts to be improved manually - or automatically for some kinds of artefacts only. We present a survey of detected artefacts, evaluation of the Delaunay and greedy triangulations as to the number and kind of contour line artefacts, examples of achievements using manual placement of constrained edges and two algorithms suitable for automatic detection and removal of artefacts caused by flat triangle areas. According to our results, problems are not completely removed but the number of problematic areas is decreased substantially.

Given an input set of planar points, which occupy a non-convex polygon area, possibly with holes, we reconstruct the shape of its boundary domain, without previous knowledge of which points or edges belong to the boundary. Our approach is based on different qualities of the Delaunay triangles inside and outside the domain. This method is heuristic and does not ensure success in all cases but it is very simple and there is no other method for this problem known to us. The method was derived on real GIS data but experiments show that it could also be used for mechanical engineering data, with positive results.

The paper describes a new algorithm for solving the point-in-polygon problem. It is especially suitable when it is necessary to check whether many points are placed inside or outside a polygon. The algorithm works in two steps. First, a grid of cells equal in size is generated, and the polygon is laid on that grid. A heuristic approach is proposed for cell dimensioning. The cells of the grid are marked as being inside, outside, or on the polygon border. A modified flood-fill algorithm is applied for cell classification. In the second step, points are tested individually. If the tested point falls into an inner or an outer cell, the result is returned without any additional calculations. If the cell contains the polygon border, it is possible to determine the local point position. The analysis of time complexity shows that the initialization is finished in O(n n ) time, while the expected time complexity for checking an individual point is O( n ) , where n represents the number of polygon edges. The algorithm works with O ( n ) space complexity. The paper also gives practical results using artificial and real polygons from a GIS environment.