GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
remove_duplicates.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/remove_duplicates.c
3 
4  \brief Vector library - clean geometry (remove duplicates)
5 
6  Higher level functions for reading/writing/manipulating vectors.
7 
8  (C) 2001-2009 by the GRASS Development Team
9 
10  This program is free software under the GNU General Public License
11  (>=v2). Read the file COPYING that comes with GRASS for details.
12 
13  \author Radim Blazek
14  */
15 
16 #include <stdlib.h>
17 #include <grass/vector.h>
18 #include <grass/glocale.h>
19 
20 static int cmp_int(const void *a, const void *b)
21 {
22  return (*(int *)a - *(int *)b);
23 }
24 
25 static int boxlist_add_sorted(struct boxlist *list, int id)
26 {
27  int i;
28 
29  if (list->n_values > 0) {
30  if (bsearch(&id, list->id, list->n_values, sizeof(int), cmp_int))
31  return 0;
32  }
33 
34  if (list->n_values == list->alloc_values) {
35  size_t size = (list->n_values + 100) * sizeof(int);
36 
37  list->id = (int *)G_realloc((void *)list->id, size);
38  list->alloc_values = list->n_values + 100;
39  }
40 
41  i = 0;
42  if (list->n_values > 0) {
43  for (i = list->n_values; i > 0; i--) {
44  if (list->id[i - 1] < id)
45  break;
46  list->id[i] = list->id[i - 1];
47  }
48  }
49  list->id[i] = id;
50  list->n_values++;
51 
52  return 1;
53 }
54 
55 /*!
56  \brief Remove duplicate features from vector map.
57 
58  Remove duplicate lines of given types from vector map. Duplicate
59  lines may be optionally written to error map. Input map must be
60  opened on level 2 for update. Categories are merged.
61  GV_BUILD_BASE is sufficient.
62 
63  \param[in,out] Map vector map where duplicate lines will be deleted
64  \param type type of line to be delete
65  \param[out] Err vector map where duplicate lines will be written or NULL
66 
67  \return void
68  */
69 void Vect_remove_duplicates(struct Map_info *Map, int type, struct Map_info *Err)
70 {
71  struct line_pnts *APoints, *BPoints;
72  struct line_cats *ACats, *BCats;
73  int i, c, atype, btype, aline, bline;
74  int nlines, nacats_orig, npoints;
75  int na1, na2, nb1, nb2, nodelines, nline;
76  struct bound_box ABox;
77  struct boxlist *List;
78  int ndupl, is_dupl;
79 
80 
81  APoints = Vect_new_line_struct();
82  BPoints = Vect_new_line_struct();
83  ACats = Vect_new_cats_struct();
84  BCats = Vect_new_cats_struct();
85  List = Vect_new_boxlist(0);
86 
87  nlines = Vect_get_num_lines(Map);
88 
89  G_debug(1, "nlines = %d", nlines);
90  /* Go through all lines in vector, for each line select lines which
91  * overlap with the first vertex of this line and check if a
92  * selected line is identical. If yes, remove the selected line.
93  * If the line vertices are identical with those of any other line,
94  * merge categories and rewrite the current line.
95  */
96 
97  ndupl = 0;
98 
99  for (aline = 1; aline <= nlines; aline++) {
100  G_percent(aline, nlines, 1);
101  if (!Vect_line_alive(Map, aline))
102  continue;
103 
104  atype = Vect_read_line(Map, APoints, ACats, aline);
105  if (!(atype & type))
106  continue;
107 
108  npoints = APoints->n_points;
109  Vect_line_prune(APoints);
110 
111  if (npoints != APoints->n_points) {
112  G_debug(3, "Line %d pruned, %d vertices removed", aline, npoints - APoints->n_points);
113  Vect_rewrite_line(Map, aline, atype, APoints, ACats);
114  nlines = Vect_get_num_lines(Map);
115  continue;
116  }
117 
118  na1 = na2 = -1;
119  if (atype & GV_LINES) {
120  /* faster than Vect_select_lines_by_box() */
121  Vect_reset_boxlist(List);
122  Vect_get_line_nodes(Map, aline, &na1, &na2);
123  nodelines = Vect_get_node_n_lines(Map, na1);
124 
125  for (i = 0; i < nodelines; i++) {
126  nline = abs(Vect_get_node_line(Map, na1, i));
127 
128  if (nline == aline)
129  continue;
130  if (Vect_get_line_type(Map, nline) != atype)
131  continue;
132 
133  boxlist_add_sorted(List, nline);
134  }
135  }
136  else {
137  /* select potential duplicates */
138  ABox.E = ABox.W = APoints->x[0];
139  ABox.N = ABox.S = APoints->y[0];
140  ABox.T = ABox.B = APoints->z[0];
141  Vect_select_lines_by_box(Map, &ABox, atype, List);
142  G_debug(3, " %d lines selected by box", List->n_values);
143  }
144 
145  is_dupl = 0;
146 
147  for (i = 0; i < List->n_values; i++) {
148  bline = List->id[i];
149  G_debug(3, " j = %d bline = %d", i, bline);
150 
151  /* compare aline and bline only once */
152  if (aline <= bline)
153  continue;
154 
155  nb1 = nb2 = -1;
156 
157  if (atype & GV_LINES) {
158  Vect_get_line_nodes(Map, bline, &nb1, &nb2);
159  if ((na1 == nb1 && na2 != nb2) ||
160  (na1 == nb2 && na2 != nb1))
161  continue;
162  }
163 
164  btype = Vect_read_line(Map, BPoints, BCats, bline);
165  Vect_line_prune(BPoints);
166 
167  /* check for duplicate */
168  if (!Vect_line_check_duplicate(APoints, BPoints, Vect_is_3d(Map)))
169  continue;
170 
171  /* bline is identical to aline */
172  if (!is_dupl) {
173  if (Err) {
174  Vect_write_line(Err, atype, APoints, ACats);
175  }
176  is_dupl = 1;
177  }
178  Vect_delete_line(Map, bline);
179 
180  /* merge categories */
181  nacats_orig = ACats->n_cats;
182 
183  for (c = 0; c < BCats->n_cats; c++)
184  Vect_cat_set(ACats, BCats->field[c], BCats->cat[c]);
185 
186  if (ACats->n_cats > nacats_orig) {
187  G_debug(4, "cats merged: n_cats %d -> %d", nacats_orig,
188  ACats->n_cats);
189  }
190 
191  ndupl++;
192  }
193  if (is_dupl) {
194  Vect_rewrite_line(Map, aline, atype, APoints, ACats);
195  nlines = Vect_get_num_lines(Map);
196  G_debug(3, "nlines = %d\n", nlines);
197  }
198  }
199  G_verbose_message(_("Removed duplicates: %d"), ndupl);
200 }
201 
202 /*!
203  \brief Check for duplicate lines
204 
205  Note that lines must be pruned with Vect_line_prune() before passed
206  to Vect_line_check_duplicate(), as done by Vect_remove_duplicates()
207 
208  \param APoints first line geometry
209  \param BPoints second line geometry
210 
211  \return 1 duplicate
212  \return 0 not duplicate
213  */
214 int Vect_line_check_duplicate(const struct line_pnts *APoints,
215  const struct line_pnts *BPoints, int with_z)
216 {
217  int k;
218  int npoints;
219  int forw, backw;
220 
221  if (APoints->n_points != BPoints->n_points)
222  return 0;
223 
224  npoints = APoints->n_points;
225 
226  /* Forward */
227  forw = 1;
228  for (k = 0; k < APoints->n_points; k++) {
229  if (APoints->x[k] != BPoints->x[k] ||
230  APoints->y[k] != BPoints->y[k] ||
231  (with_z && APoints->z[k] != BPoints->z[k])) {
232  forw = 0;
233  break;
234  }
235  }
236 
237  /* Backward */
238  backw = 1;
239  for (k = 0; k < APoints->n_points; k++) {
240  if (APoints->x[k] != BPoints->x[npoints - k - 1] ||
241  APoints->y[k] != BPoints->y[npoints - k - 1] ||
242  (with_z && APoints->z[k] != BPoints->z[npoints - k - 1])) {
243  backw = 0;
244  break;
245  }
246  }
247 
248  if (!forw && !backw)
249  return 0;
250 
251  return 1;
252 }
Bounding box.
Definition: dig_structs.h:65
int * id
Array of ids.
Definition: dig_structs.h:1755
double W
West.
Definition: dig_structs.h:82
plus_t Vect_get_num_lines(const struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:74
off_t Vect_rewrite_line(struct Map_info *, off_t, int, const struct line_pnts *, const struct line_cats *)
Rewrites existing feature (topological level required)
int n_points
Number of points.
Definition: dig_structs.h:1692
double E
East.
Definition: dig_structs.h:78
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
Definition: line.c:281
int n_values
Number of items in the list.
Definition: dig_structs.h:1767
int Vect_get_node_n_lines(const struct Map_info *, int)
Get number of lines for node.
Definition: level_two.c:384
Feature category info.
Definition: dig_structs.h:1702
double N
North.
Definition: dig_structs.h:70
double * x
Array of X coordinates.
Definition: dig_structs.h:1680
int Vect_select_lines_by_box(struct Map_info *, const struct bound_box *, int, struct boxlist *)
Select lines with bounding boxes by box.
Definition: sindex.c:34
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
int Vect_get_node_line(const struct Map_info *, int, int)
Get line id for node line index.
Definition: level_two.c:401
double b
Definition: r_raster.c:39
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
int n_cats
Number of categories attached to element.
Definition: dig_structs.h:1715
int * cat
Array of categories.
Definition: dig_structs.h:1711
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
void Vect_remove_duplicates(struct Map_info *Map, int type, struct Map_info *Err)
Remove duplicate features from vector map.
double B
Bottom.
Definition: dig_structs.h:90
double T
Top.
Definition: dig_structs.h:86
int Vect_reset_boxlist(struct boxlist *)
Reset boxlist structure.
int Vect_get_line_nodes(const struct Map_info *, int, int *, int *)
Get line nodes.
Definition: level_two.c:307
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:62
Vector map info.
Definition: dig_structs.h:1259
double * y
Array of Y coordinates.
Definition: dig_structs.h:1684
int Vect_is_3d(const struct Map_info *)
Check if vector map is 3D.
int alloc_values
Allocated space for items.
Definition: dig_structs.h:1771
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_line_check_duplicate(const struct line_pnts *APoints, const struct line_pnts *BPoints, int with_z)
Check for duplicate lines.
Definition: manage.h:4
List of bounding boxes with id.
Definition: dig_structs.h:1750
double S
South.
Definition: dig_structs.h:74
int Vect_line_alive(const struct Map_info *, int)
Check if feature is alive or dead (topological level required)
#define G_realloc(p, n)
Definition: defs/gis.h:114
double * z
Array of Z coordinates.
Definition: dig_structs.h:1688
#define _(str)
Definition: glocale.h:10
int * field
Array of layers (fields)
Definition: dig_structs.h:1707
#define GV_LINES
Definition: dig_defines.h:192
struct boxlist * Vect_new_boxlist(int)
Creates and initializes a struct boxlist.
void void G_verbose_message(const char *,...) __attribute__((format(printf
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int G_debug(int, const char *,...) __attribute__((format(printf
int Vect_get_line_type(const struct Map_info *, int)
Get line type.
Definition: level_two.c:258
int Vect_cat_set(struct line_cats *, int, int)
Add new field/cat to category structure if doesn&#39;t exist yet.