The extraction of partition lines from long and narrow patches is a key part of thematic data generalization and a challenging endeavor. Existing methods for extracting partition lines have limitations, such as jitter, nonhomogeneous topologies, and inconsistent geometries. Therefore, an approach to extracting partition lines that addresses these issues is proposed. Firstly, the jitter is categorized as types by analyzing the jitter causes, and the corresponding algorithm is herein presented. By employing the connection nodal points of the adjacent polygon boundary as a constraint, the compensation algorithm for partition lines is established. The partition line is then pruned according to its topological infrastructure to make it natural and smooth. An evaluation was conducted in which partition lines of typical long and narrow water and road patches were extracted from survey data under the geographical conditions of China's Guizhou province. The results verified that the proposed approach is feasible and reasonable.
of convex polygons
Ai (2000) was the first to introduce a boundary-constrained Delaunay triangulation method to extract polygon
skeletons for solving the integration issue of polygonal planar objects.
The existing skeleton extraction methods based on Delaunay triangular meshes have specific advantages. Nevertheless, when used for long and narrow patches, these methods have the following problems. (1) When long and narrow patches with two approximately-parallel sides or multiple forks are processed, the extracted skeletons show jitter containing many “zigzags.” (2) Internal skeletons fail to extend to the patch outline, or external skeletons are unable to mount to intra-plane skeletons, leading to topological anisomorphism of extracted skeletons with respect to the original graphs. (3) Extracted frontal points and endpoints are not adequately smooth, making the shape features of extracted skeletons inconsistent with those of original graphs.
To address the above issues, we propose a jitter removal (“de-jitter”) and compensation method for patch partition lines of long and narrow patches in national geographical condition data. In this method, we identify long and narrow patches using patch-width constraints. In addition, the classic Delaunay triangular mesh method is employed to extract skeletons of long and narrow patches. The scenarios of extracted skeletons showing jitter, topological anisomorphism, or shape feature inconsistency are hence classified. Moreover, we propose corresponding partition line de-jitter and compensation methods to obtain smooth and natural skeletons as the partition lines of the long and narrow patches. To verify the feasibility and rationality of the proposed approach, we employed real patch data from a national geographic condition database. The results verified the effectiveness for extracting partition lines from long and narrow objects. 2 2.1
Long and narrow patches refer to the long and narrow objects among patches, such as long and thin planar rivers,
low-grade planar paths and roads, farmland borders, and ditches. Long and narrow patches usually connect to
several types of surface object patches and are crucial for maintaining their topological connectivity. When the scale
decreases, long and narrow patches show dimensionality reduction, changing from two-dimensional (2D) planar
objects to one-dimensional (1D) linear objects because of the narrowing width. The width of a long and narrow
patch can be defined according to the following formula
Skeletons are curves that have the same connectivity and topological structure as the original shape, reflecting the primary extension direction and main shape features of a planar patch. Generating skeletons in the Delaunay triangular meshes is the basic idea for partitioning long and narrow patches. To ensure that the constructed triangular meshes do not transgress the patch boundaries, we use discrete boundary points as computation objects inside the patch. Additionally, we employ point-by-point insertion to preliminarily construct boundary-constrained Delaunay triangular meshes.
The classic Delaunay triangular mesh method classifies triangles into three categories according to the number of
adjacent triangles in a polygon
Type-I triangles: They have only one adjacent triangle. Two sides of type-I triangles are the boundaries of polygons. As shown by △ABG, △CDE and △EFG in Figure 1, all vertexes, A, D and F, are those of skeletons.
Type-II triangles: They have two adjacent triangles and are the backbone structure of a skeleton, thereby describing the extension direction of the skeleton. As shown by △BCE in Figure 1, the extension direction of skeletons in this type of triangle is unique.
Type-III triangles: They have two adjacent triangles and are the junction of skeletons as well as the starting point of the extension in three directions. As shown by △BEG in Figure 1, the extension proceeds in three directions at point L.
The classic boundary-constrained Delaunay triangular mesh method extracts the central axes of the three types of triangles based on the three approaches described below. In addition, it connects the central axes to form skeletons, with the common side of two adjacent triangles being referred to as an adjacent side.
Type-I triangles: The middle point of the only adjacent side is connected to its corresponding vertex, such as the lines AH, DJ, and FK in Figure 1.
Type-II triangles: The middle points of two adjacent sides are connected, such as the line IJ in Figure 1.
Type-III triangles: The center of gravity is connected to the middle points of the three sides, such as the lines LI, LK and LH. 3
The partition lines of long and narrow patches extracted with the boundary-constrained Delaunay triangular mesh method is subject to the jitter of skeletons. According to the position of the jitter in the triangular meshes, the jitter may be classified into two types: end jitter and middle jitter. 3.1
The type-I triangles are usually present in the terminal part of a patch. In extraction of primary partition lines, the central axis of a type-I triangle is determined with the middle point of its only adjacent side and the corresponding vertex. This makes the partition lines in the terminal part of a patch unable to accurately reflect the object trend, causing jitter to appear in the partition line extension, as shown in Figure 2.
In particular, points C and D are the middle points of the boundaries of the terminal triangles, E is the vertex of
the terminal triangles, and A and B are the first and second points of the skeletons, respectively. According to the
automatic recognition rule for river flow direction proposed by
As shown in Figure 2, According to the above 180-degree rule and with respect to end jitter, we calculate the degrees of ∠ABC, ∠ABD and ∠ABE, respectively, and determine that the degree of ∠ABC is closest to 180o. We therefore select point C as the starting point of the skeletons. Accordingly, we can obtain relatively smooth starting and ending lines. 3.2
As shown by the skeletons of the Delaunay triangular meshes, the skeletons of type-I and type-II triangles have definite extension directions, whereas type-III triangles comprise a junction of partition line branches and are associated with three sides via the center of gravity. Therefore, when long and narrow patches with two approximately parallel sides or multiple forks are processed, the partition lines of type-III triangles show jitter, causing the partition lines to have several “zigzags,” as shown in Figure 3.
(a) “—” shape patch jitter (b) “T” shape patch jitter
(c) “+” shape patch jitter
The jitter of skeletons of type-III triangles causes the extracted patch partition lines to fail in conforming to the distribution rule of geographical phenomena. Therefore, it is necessary to conduct an adjustment to partition lines showing middle jitter.
(1) Jitter adjustment algorithm for “—”shape patches
As shown in Figure 3(a), the main reason that the partition lines of “—” shape patches show jitter is that the centroid of a type-III triangle is used as the center of gravity. In the case of an acute triangle, the position of the center of gravity causes the partition lines to deviate from their original extension directions. Therefore, it is necessary to find and use another point in a triangle as the centroid replace the center of gravity. In this paper, we propose a centroid search algorithm as follows.
First, we sort the three sides of a triangle in the order from the shortest side (SS) to the middle side (MS), and then to the longest side (LS). Provided that SS and MS have a similar length (SS≈MS), we label LS for the calculation. Provided that MS and LS have a similar length (MS≈LS), we label SS for the calculation and connect the center of the labeled side to its corresponding vertex as the centroid of type-III triangles. If the three sides are similar in their lengths, we connect the centers of each side in the patch extension direction, as shown in Figure 4 (see Sections 4.2 and 4.3 for the processing of tiny and lumpy partition lines on patch boundaries).
S S MS
LS
F
Figure 4 Adjustment result of “—” pattern (2) Jitter adjustment algorithm for “T” shape patches
As opposed to the partition line jitter generation in “—” shape patches, the partition lines of “T” shape patches appear to have branches. Therefore, it is necessary to determine the hierarchical structure of the partition lines in the patch before a jitter adjustment.
The hierarchical structure of the partition lines can be obtained by establishing a stroke characteristic curve under
the constraints of length, area, and trend. In particular, the area constraint of a partition line denotes the area sum of
the triangles through which the line travels, with the trend as the included angle of each arc
Step 1: Randomly select a dangling nodal point of a partition line as the starting nodal point of tracking, such as point A in Figure 5(a). With the associated arc of the starting nodal point as a tracking arc (e.g., arc segment AO), we obtain another nodal point of the arc, namely point O, which is then used as a tracking nodal point.
Step 2: The arc associated with the tracking nodal point is used as a stroke candidate set R{AO}. If there is only one associated arc, we continue tracking forward until a nodal point fork is reached, such as point P in Figure 5(a), thereby generating a stroke candidate set R{PM, PN} and arc included angles {∠SPM,∠SPN}.
Step 3: Establish the stroke in the priority order from the partition line arc length to the area, and then to the trend
Step 4: Repeat Steps 2 and 3 until it is not possible to obtain a tracking arc. The processing of tracking nodal point P is then considered complete.
Step 5: The above tracking arcs comprise a stroke constraint curve (SpotStroke) for point P. Meanwhile, we record the subsequent tracking nodal points.
Step 6: Repeat Steps 1 to 4 for the tracking nodal points obtained in Step 5 until there is no tracking nodal point. (a) Before adjustment (b) After adjustment (a) Before adjustment (b) After adjustment
The above-mentioned dangling nodal point on the arc in the algorithm denotes a nodal point that connects to no other arc. An arc containing a dangling nodal point is referred to as a dangling arc. The hierarchical structure of the partition lines is hidden in the iterative process of establishing the SpotStroke. A level-1 partition line is the optimal arc set under the constraints of length, area, and trend, such as curve AOTSPNQ in Figure 5(a). Other levels of partition lines can be subsequently obtained.
First, we process the type-III triangles on the primary partition lines by exploring the type-II triangles before and after the type-III triangles on the primary partition lines. We connect the middle points of the adjacent sides of two triangles, such as arc NS in Figure 5(b), and obtain a new primary partition line, OTSNQ. The partition lines of the “T” shape patches are obtained with the “reverse extension method” discussed in Section 3.2. In the graph of Figure 5(b), the end jitter had been adjusted with the method discussed in Section 2.1.
(3) Jitter adjustment algorithm for “+” shape patches
Compared with partition lines of “T” shape patches, the partition lines of “+” shape patches have more branches and a less apparent hierarchical structure. With respect to this difference, we conduct a nodal point fitting via spatial clustering to adjust the jitter in partition lines of “+” shape patches.
As depicted in Figure 6(a), the jitter in partition lines of “+” shape patches show an obvious “工” shape feature, with two or more nodal points that connect in three directions of confluence at the junctions in the patches. According to this feature, we establish a partition line topological structure to detect jitter-containing regions (the confluence regions of the branches) and record all type-II and type-III triangles in these regions. Next, we determine the range of nodal points to be fit. In this process, we consider that the skeletons of type-II triangles have the skeletal structures of partition lines because the skeletons of type-III triangles were used for describing the branch structures of partition lines. Therefore, we proposed that, when a partition line length of a type-II triangle in a jitter-containing region is less than the width threshold value (Table 1), the nodal points associated with this partition line must be fitted.
In Figure 6(a), the jitter-containing region does not contain type-II triangles. Therefore, the skeletal partition lines
have a length of 0, which is less than the threshold value of 0.4 mm, thereby indicating that nodal points O1, O2 and
P should be fit. We further consider the spatial proximity of each nodal point object and use the Euclidean distance
between point objects as a similarity measurement index for performing k-means clustering
Lastly, we track type-II triangles outside the jitter-containing region associated with type-III triangles. We connect the fitted nodal point to the middle points of adjacent sides. Then, according to the 180-degree rule, we perform a proper correction leading to a new partition line, as shown by arcs RON and SOM in Figure 6(b) (the end jitter in this graph was adjusted with the method discussed in Section 2.1). 4
To achieve a seamless subdivision of long and narrow patches, it is necessary to consider the constraints of connecting points of adjacent polygonal boundaries on the partition lines, which include the following scenarios. (1) Each endpoint of a partition line is at the boundary nodal point of an adjacent polygon. (2) Each polygonal boundary nodal point matches a partition line endpoint. A direct extraction of partition lines from the Delaunay meshes inside a polygon causes the internal skeletons to fail to extend to the patch outline, or the external skeletons fail to mount to the intra-plane skeletons. These conditions lead to the topological anisomorphism of the extracted skeleton with respect to the original graphs, and the partition lines should thus be compensated. 4.1
In normal cases, a nodal point on a planar polygonal patch is associated only with two connected arcs on the same polygon. Moreover, it affects only the connection between the two arcs in an extension direction. Such a nodal point is referred to as the single nodal point of the polygon, as shown in Fig 7(a), where nodal point A is the single nodal point of polygon P1. In Figure 7(b), nodal points A and B are the single nodal points of polygon P2. It is obvious that the partition lines at the single nodal points in Figure 7 do not meet the constraints of boundary connection points of adjacent polygons on the partition lines.
(a) Partition line perpendicular to the boundary of an adjacent polygon (b) Partition line at a
certain angle with respect to the boundary of an adjacent polygon Figure 7 Lack of partition lines.
(a) Closest point method (b) Reverse extension
method
Given that the Delaunay triangular meshes are established under boundary constraints, the boundary connection
point between the adjacent polygons and the polygon to be subdivided—such as A in Figure 7(a), or A and B in Fig
7(b)—will definitely be a vertex of the Delaunay triangle. Nevertheless, those connection points do not connect to
the partition lines, thereby making it necessary to compensate for the partition lines by adding new partition lines.
The commonly used method for adding new partition lines is the closest point method
Therefore, we propose the use of the so-called “reverse extension method” as a complement to the closest point method to add new partition lines. This process involves determining the extension direction of the polygonal boundary according to the position between the two nodal points that were inside the adjacent polygon and close to the patch. The boundary is thereby extended in a reverse direction and can thus intersect with the patch partition line. Accordingly, a new partition line is generated by connecting the boundary nodal point to the intersection point.
As shown in Figure 8(a), the boundary of an adjacent polygon is extended in reverse from nodal point A to B, adding new partition line AB, as shown in Figure 7(a). In Figure 8(b), the boundary of an adjacent polygon is extended in reverse from nodal points A and B to nodal points C1 and D1, respectively, thereby adding new partition lines AC1 and BD1, as shown in Figure 7(b). 4.2
The planar polygonal data obtained with a national geographical condition survey have a variety of shapes, and self-connection of graphs may occur at times. Therefore, some nodal points may be shared by boundaries that are not extendable, as shown in Figure 9(a), where nodal point O is located on, and shared by, both arcs COD and AOB. It is evident that using conventional methods to extract the partition line of a polygon, as shown in Figure 9, results in a different topological structure of the partition lines than that of the original graph. Therefore, it is also necessary to conduct partition line compensation for such shared nodal points.
First, we establish a topological structure of the original graph. According to the association between nodal points and arcs, as well as the connection among arcs, it is possible to identify the shared nodal points. As opposed to a single nodal point, any point that is associated with an even number (>2) of connected arcs is a shared nodal point. For nodal points, we can produce partition line compensation with “rotation about a point,” as elaborated below.
Step 1: With point O as the origin, we sort the arcs associated with point O in an counterclockwise (or clockwise) sequence and obtain the adjacent arcs before and after each arc, such as arcs OA and OD as the adjacent arcs of arc OB.
Step 2: Randomly select an arc and judge the spatial relationship of Area<Arc, AdjArc>, the region between the arc and its adjacent arcs (AdjArc), with the polygons.
(1) If this region is still inside the polygon, and there exists a partition line associated with point O, no processing is required.
(2) If this region is inside a polygon and there exists no partition line associated with point O, the closest point method is used to compensate for the partition line of this region.
(3) If this region is outside the polygon, no processing is required.
As shown in Figure 9(a), Area<OC,OD> is inside the polygon and there is no partition line. We therefore must compensate for partition line OE. As shown in Figure 9(b), Area<OC,OD> is inside the polygon and there exists a partition line; thus, no processing is needed. 4.3
After the addition of a new partition line, redundant skeleton braches, such as CE and DF in Figure 8(b), should be removed. The main procedure for the removal is iteratively deleting the dangling arcs in the topological structure of skeletons (while retaining the new added partition line) until there is no longer a dangling arc. We can thus obtain the final partition line, as shown in Figure 10. 5
With the WJ-III map workstation developed by Chinese Academy of Surveying and Mapping, we implemented the proposed partition line extraction method for long and narrow patches. In addition, we identified long and narrow patches and achieved adjustment optimization of partition lines under a C++ environment. 5.1
The experimental object was a polygonal water patch (Figure 11(a)) in the thematic data of the national geographical condition survey of a city in Guizhou Province, China, with a 1:50,000 scale.
(1) As shown in Table 1, for a mapping scale of 1:50,000, the width standard of long and narrow patches is 0.4 mm × 5 × 104 = 20 m. According to formula (1), we calculated the approximate average width of each patch, with BL—the longest baseline—obtained via the skeletons. Long and narrow patches were selected according to the threshold value of 20 mm, with a long and narrow patch depicted in Figure 11(a). (2) The classic boundary-constrained Delaunay triangular mesh method was used to extract the partition lines of this long and narrow patch, as shown in Figure 11(b).
(3) By using a stroke curve under the constraints of length, area, and trend, we obtained the primary skeletons of this long and narrow patch. We then removed the jitter in the partition line according to the hierarchical structure and the 180-degree rule, as shown in Figure 11(c).
(4) Considering the constraints of boundary nodal points of adjacent polygons on the partition lines, we employed the closest point method and the reverse extension method to add new partition lines for connecting the boundary nodal points of adjacent polygons, as shown in Figure 11(d).
(5) After iteratively deleting the dangling arcs in the topological structure of skeletons, we conducted “pruning” of the partition lines, and we obtained a final partition line that has the same topological relation and geometric shape as the original graph, as shown in Figure 11(e). (a) Extraction of a long and narrow patch.
(b) Basic partition line.
(c) De-jittering the partition line.
(d) Partition line compensation.
(e) Final partition line.
Partition line extraction in long and narrow patches is a fundamental yet challenging part of the integration of thematic data of national geographical condition survey. The spatial features of full patch data coverage without overlapping, the geometric feature of natural smoothness, and the topological features all must be considered and maintained. This study was based on the idea of extracting skeletons with the Delaunay triangular mesh method. Accordingly, we examined the problems of extracted partition lines showing jitter, topological anisomorphism, and geometric incongruence. Based on our findings, we proposed de-jitter and compensation methods for partition lines in a variety of scenarios.
The proposed methods were verified by thematic data of a national geographical condition survey. Our method was shown to reasonably extract partition lines of long and narrow patches. The extracted partition lines were naturally smooth and showed good connectivity and topological congruence, thereby effectively conforming to human perception of planar surface objects. Moreover, the proposed approach compensated for the partition lines at single nodal points and shared nodal points and was not influenced by the bending and rotation of original graphs. It thereby maintained topological isomorphism with respect to the original graphs. Based on the adjacent patches examined in this study, a follow-up study will further investigate patch merging based on topological and semantic proximity.
This research was supported by the National Surveying and Mapping Projects (A1705).