GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-8828094037
sindex.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/sindex.c
3 
4  \brief Vector library - select vector features
5 
6  Higher level functions for reading/writing/manipulating vectors.
7 
8  (C) 2001-2011 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, Markus Metz
14  */
15 
16 #include <stdlib.h>
17 #include <grass/vector.h>
18 
19 /*!
20  \brief Select lines with bounding boxes by box.
21 
22  Select lines whose boxes overlap specified box!!! It means that
23  selected line may or may not overlap the box.
24 
25  \param Map vector map
26  \param Box bounding box
27  \param type line type
28  \param[out] list output list, must be initialized
29 
30  \return number of lines
31  */
32 int Vect_select_lines_by_box(struct Map_info *Map, const struct bound_box *Box,
33  int type, struct boxlist *list)
34 {
35  int i, line, nlines, ntypes, mtype;
36  struct Plus_head *plus;
37  struct P_line *Line;
38  static struct boxlist *LocList = NULL;
39 
40  G_debug(3, "Vect_select_lines_by_box()");
41  G_debug(3, " Box(N,S,E,W,T,B): %e, %e, %e, %e, %e, %e", Box->N, Box->S,
42  Box->E, Box->W, Box->T, Box->B);
43  plus = &(Map->plus);
44 
46 
47  ntypes = mtype = 0;
48  /* count the number of different primitives in Map */
49  if (plus->n_plines != 0) {
50  ntypes++;
51  mtype |= GV_POINT;
52  }
53  if (plus->n_llines != 0) {
54  ntypes++;
55  mtype |= GV_LINE;
56  }
57  if (plus->n_blines != 0) {
58  ntypes++;
59  mtype |= GV_BOUNDARY;
60  }
61  if (plus->n_clines != 0) {
62  ntypes++;
63  mtype |= GV_CENTROID;
64  }
65  if (plus->n_flines != 0) {
66  ntypes++;
67  mtype |= GV_FACE;
68  }
69  if (plus->n_klines != 0) {
70  ntypes++;
71  mtype |= GV_KERNEL;
72  }
73 
74  if (ntypes == 1) {
75  /* there is only one type in Map */
76  if (mtype & type)
77  return dig_select_lines(plus, Box, list);
78  return 0;
79  }
80 
81  if (ntypes == 0)
82  /* empty vector */
83  return 0;
84 
85  if (!LocList) {
86  LocList = (struct boxlist *)G_malloc(sizeof(struct boxlist));
87  dig_init_boxlist(LocList, 1);
88  }
89 
90  nlines = dig_select_lines(plus, Box, LocList);
91  G_debug(3, " %d lines selected (all types)", nlines);
92 
93  /* Remove lines of not requested types */
94  for (i = 0; i < nlines; i++) {
95  line = LocList->id[i];
96  if (plus->Line[line] == NULL)
97  continue; /* Should not happen */
98  Line = plus->Line[line];
99  if (!(Line->type & type))
100  continue;
101  dig_boxlist_add(list, line, &LocList->box[i]);
102  }
103 
104  G_debug(3, " %d lines of requested type", list->n_values);
105 
106  return list->n_values;
107 }
108 
109 /*!
110  \brief Select areas with bounding boxes by box.
111 
112  Select areas whose boxes overlap specified box!!!
113  It means that selected area may or may not overlap the box.
114 
115  \param Map vector map
116  \param Box bounding box
117  \param[out] output list, must be initialized
118 
119  \return number of areas
120  */
121 int Vect_select_areas_by_box(struct Map_info *Map, const struct bound_box *Box,
122  struct boxlist *list)
123 {
124  int i;
125  static int debug_level = -1;
126 
127  if (debug_level == -1) {
128  const char *dstr = G_getenv_nofatal("DEBUG");
129 
130  if (dstr != NULL)
131  debug_level = atoi(dstr);
132  else
133  debug_level = 0;
134  }
135 
136  G_debug(3, "Vect_select_areas_by_box()");
137  G_debug(3, "Box(N,S,E,W,T,B): %e, %e, %e, %e, %e, %e", Box->N, Box->S,
138  Box->E, Box->W, Box->T, Box->B);
139 
140  dig_select_areas(&(Map->plus), Box, list);
141  G_debug(3, " %d areas selected", list->n_values);
142  /* avoid loop when not debugging */
143  if (debug_level > 2) {
144  for (i = 0; i < list->n_values; i++) {
145  G_debug(3, " area = %d pointer to area structure = %p",
146  list->id[i], (void *)Map->plus.Area[list->id[i]]);
147  }
148  }
149 
150  return list->n_values;
151 }
152 
153 /*!
154  \brief Select isles with bounding boxes by box.
155 
156  Select isles whose boxes overlap specified box!!!
157  It means that selected isle may or may not overlap the box.
158 
159  \param Map vector map
160  \param Box bounding box
161  \param[out] list output list, must be initialized
162 
163  \return number of isles
164  */
165 int Vect_select_isles_by_box(struct Map_info *Map, const struct bound_box *Box,
166  struct boxlist *list)
167 {
168  G_debug(3, "Vect_select_isles_by_box()");
169  G_debug(3, "Box(N,S,E,W,T,B): %e, %e, %e, %e, %e, %e", Box->N, Box->S,
170  Box->E, Box->W, Box->T, Box->B);
171 
172  dig_select_isles(&(Map->plus), Box, list);
173  G_debug(3, " %d isles selected", list->n_values);
174 
175  return list->n_values;
176 }
177 
178 /*!
179  \brief Select nodes by box.
180 
181  \param Map vector map
182  \param Box bounding box
183  \param[out] list output list, must be initialized
184 
185  \return number of nodes
186  */
187 int Vect_select_nodes_by_box(struct Map_info *Map, const struct bound_box *Box,
188  struct ilist *list)
189 {
190  struct Plus_head *plus;
191 
192  G_debug(3, "Vect_select_nodes_by_box()");
193  G_debug(3, "Box(N,S,E,W,T,B): %e, %e, %e, %e, %e, %e", Box->N, Box->S,
194  Box->E, Box->W, Box->T, Box->B);
195 
196  plus = &(Map->plus);
197 
199 
200  dig_select_nodes(plus, Box, list);
201  G_debug(3, " %d nodes selected", list->n_values);
202 
203  return list->n_values;
204 }
205 
206 /*!
207  \brief Select lines by Polygon with optional isles.
208 
209  Polygons should be closed, i.e. first and last points must be identical.
210 
211  \param Map vector map
212  \param Polygon outer ring
213  \param nisles number of islands or 0
214  \param Isles array of islands or NULL
215  \param type line type
216  \param[out] list output list, must be initialised
217 
218  \return number of lines
219  */
221  struct line_pnts *Polygon, int nisles,
222  struct line_pnts **Isles, int type,
223  struct ilist *List)
224 {
225  int i;
226  struct bound_box box;
227  static struct line_pnts *LPoints = NULL;
228  static struct boxlist *LocList = NULL;
229 
230  /* TODO: this function was not tested with isles */
231  G_debug(3, "Vect_select_lines_by_polygon() nisles = %d", nisles);
232 
233  Vect_reset_list(List);
234  if (!LPoints)
235  LPoints = Vect_new_line_struct();
236  if (!LocList) {
237  LocList = Vect_new_boxlist(0);
238  }
239 
240  /* Select first all lines by box */
241  dig_line_box(Polygon, &box);
243  box.B = -PORT_DOUBLE_MAX;
244  Vect_select_lines_by_box(Map, &box, type, LocList);
245  G_debug(3, " %d lines selected by box", LocList->n_values);
246 
247  /* Check all lines if intersect the polygon */
248  for (i = 0; i < LocList->n_values; i++) {
249  int j, line, intersect = 0;
250 
251  line = LocList->id[i];
252  /* Read line points */
253  Vect_read_line(Map, LPoints, NULL, line);
254 
255  /* Check if any of line vertices is within polygon */
256  for (j = 0; j < LPoints->n_points; j++) {
257  if (Vect_point_in_poly(LPoints->x[j], LPoints->y[j], Polygon) >=
258  1) { /* inside polygon */
259  int k, inisle = 0;
260 
261  for (k = 0; k < nisles; k++) {
262  if (Vect_point_in_poly(LPoints->x[j], LPoints->y[j],
263  Isles[k]) >= 1) { /* in isle */
264  inisle = 1;
265  break;
266  }
267  }
268 
269  if (!inisle) { /* inside polygon, outside isles -> select */
270  intersect = 1;
271  break;
272  }
273  }
274  }
275  if (intersect) {
276  Vect_list_append(List, line);
277  continue;
278  }
279 
280  /* Check intersections of the line with area/isles boundary */
281  /* Outer boundary */
282  if (Vect_line_check_intersection(LPoints, Polygon, 0)) {
283  Vect_list_append(List, line);
284  continue;
285  }
286 
287  /* Islands */
288  for (j = 0; j < nisles; j++) {
289  if (Vect_line_check_intersection(LPoints, Isles[j], 0)) {
290  intersect = 1;
291  break;
292  }
293  }
294  if (intersect) {
295  Vect_list_append(List, line);
296  }
297  }
298 
299  G_debug(4, " %d lines selected by polygon", List->n_values);
300 
301  return List->n_values;
302 }
303 
304 /*!
305  \brief Select areas by Polygon with optional isles.
306 
307  Polygons should be closed, i.e. first and last points must be identical.
308 
309  \param Map vector map
310  \param Polygon outer ring
311  \param nisles number of islands or 0
312  \param Isles array of islands or NULL
313  \param[out] list output list, must be initialised
314 
315  \return number of areas
316  */
318  struct line_pnts *Polygon, int nisles,
319  struct line_pnts **Isles, struct ilist *List)
320 {
321  int i, area;
322  static struct ilist *BoundList = NULL;
323 
324  /* TODO: this function was not tested with isles */
325  G_debug(3, "Vect_select_areas_by_polygon() nisles = %d", nisles);
326 
327  Vect_reset_list(List);
328  if (!BoundList)
329  BoundList = Vect_new_list();
330 
331  /* Select boundaries by polygon */
332  Vect_select_lines_by_polygon(Map, Polygon, nisles, Isles, GV_BOUNDARY,
333  BoundList);
334 
335  /* Add areas on left/right side of selected boundaries */
336  for (i = 0; i < BoundList->n_values; i++) {
337  int line, left, right;
338 
339  line = BoundList->value[i];
340 
341  Vect_get_line_areas(Map, line, &left, &right);
342  G_debug(4, "boundary = %d left = %d right = %d", line, left, right);
343 
344  if (left > 0) {
345  Vect_list_append(List, left);
346  }
347  else if (left < 0) { /* island */
348  area = Vect_get_isle_area(Map, abs(left));
349  G_debug(4, " left island -> area = %d", area);
350  if (area > 0)
351  Vect_list_append(List, area);
352  }
353 
354  if (right > 0) {
355  Vect_list_append(List, right);
356  }
357  else if (right < 0) { /* island */
358  area = Vect_get_isle_area(Map, abs(right));
359  G_debug(4, " right island -> area = %d", area);
360  if (area > 0)
361  Vect_list_append(List, area);
362  }
363  }
364 
365  /* But the Polygon may be completely inside the area (only one), in that
366  * case we find the area by one polygon point and add it to the list */
367  area = Vect_find_area(Map, Polygon->x[0], Polygon->y[0]);
368  if (area > 0)
369  Vect_list_append(List, area);
370 
371  G_debug(3, " %d areas selected by polygon", List->n_values);
372 
373  return List->n_values;
374 }
#define NULL
Definition: ccmath.h:32
#define G_malloc(n)
Definition: defs/gis.h:94
int G_debug(int, const char *,...) __attribute__((format(printf
const char * G_getenv_nofatal(const char *)
Get environment variable.
Definition: env.c:405
int Vect_reset_boxlist(struct boxlist *)
Reset boxlist structure.
struct boxlist * Vect_new_boxlist(int)
Creates and initializes a struct boxlist.
int Vect_list_append(struct ilist *, int)
Append new item to the end of list if not yet present.
int Vect_read_line(struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int Vect_line_check_intersection(struct line_pnts *, struct line_pnts *, int)
Check if 2 lines intersect.
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
int Vect_point_in_poly(double, double, const struct line_pnts *)
Determines if a point (X,Y) is inside a polygon.
Definition: Vlib/poly.c:824
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
int Vect_get_line_areas(struct Map_info *, int, int *, int *)
Get area id on the left and right side of the boundary.
Definition: level_two.c:346
int Vect_reset_list(struct ilist *)
Reset ilist structure.
int Vect_find_area(struct Map_info *, double, double)
Find the nearest area.
int Vect_get_isle_area(struct Map_info *, int)
Returns area id for isle.
#define GV_CENTROID
Definition: dig_defines.h:186
#define GV_LINE
Definition: dig_defines.h:184
#define GV_POINT
Feature types used in memory on run time (may change)
Definition: dig_defines.h:183
#define GV_BOUNDARY
Definition: dig_defines.h:185
#define GV_FACE
Definition: dig_defines.h:187
#define PORT_DOUBLE_MAX
Limits for portable types.
Definition: dig_defines.h:66
#define GV_KERNEL
Definition: dig_defines.h:188
int dig_init_boxlist(struct boxlist *, int)
int dig_select_isles(struct Plus_head *, const struct bound_box *, struct boxlist *)
Select isles with boxes by box.
Definition: spindex.c:972
int dig_select_lines(struct Plus_head *, const struct bound_box *, struct boxlist *)
Select lines with boxes by box.
Definition: spindex.c:760
int dig_select_areas(struct Plus_head *, const struct bound_box *, struct boxlist *)
Select areas with boxes by box.
Definition: spindex.c:876
int dig_boxlist_add(struct boxlist *, int, const struct bound_box *)
int dig_select_nodes(struct Plus_head *, const struct bound_box *, struct ilist *)
Select nodes by bbox.
Definition: spindex.c:669
int dig_line_box(const struct line_pnts *, struct bound_box *)
float Box[8][3]
Vertices for box.
Definition: gsd_objs.c:1395
int Vect_select_lines_by_box(struct Map_info *Map, const struct bound_box *Box, int type, struct boxlist *list)
Select lines with bounding boxes by box.
Definition: sindex.c:32
int Vect_select_areas_by_box(struct Map_info *Map, const struct bound_box *Box, struct boxlist *list)
Select areas with bounding boxes by box.
Definition: sindex.c:121
int Vect_select_lines_by_polygon(struct Map_info *Map, struct line_pnts *Polygon, int nisles, struct line_pnts **Isles, int type, struct ilist *List)
Select lines by Polygon with optional isles.
Definition: sindex.c:220
int Vect_select_areas_by_polygon(struct Map_info *Map, struct line_pnts *Polygon, int nisles, struct line_pnts **Isles, struct ilist *List)
Select areas by Polygon with optional isles.
Definition: sindex.c:317
int Vect_select_nodes_by_box(struct Map_info *Map, const struct bound_box *Box, struct ilist *list)
Select nodes by box.
Definition: sindex.c:187
int Vect_select_isles_by_box(struct Map_info *Map, const struct bound_box *Box, struct boxlist *list)
Select isles with bounding boxes by box.
Definition: sindex.c:165
Vector map info.
Definition: dig_structs.h:1243
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1270
Vector geometry.
Definition: dig_structs.h:1553
char type
Line type.
Definition: dig_structs.h:1564
Basic topology-related info.
Definition: dig_structs.h:769
plus_t n_klines
Current number of kernels.
Definition: dig_structs.h:906
struct P_line ** Line
Array of vector geometries.
Definition: dig_structs.h:871
plus_t n_plines
Current number of points.
Definition: dig_structs.h:886
plus_t n_blines
Current number of boundaries.
Definition: dig_structs.h:894
struct P_area ** Area
Array of areas.
Definition: dig_structs.h:875
plus_t n_clines
Current number of centroids.
Definition: dig_structs.h:898
plus_t n_flines
Current number of faces.
Definition: dig_structs.h:902
plus_t n_llines
Current number of lines.
Definition: dig_structs.h:890
Bounding box.
Definition: dig_structs.h:64
double T
Top.
Definition: dig_structs.h:84
double B
Bottom.
Definition: dig_structs.h:88
List of bounding boxes with id.
Definition: dig_structs.h:1723
int * id
Array of ids.
Definition: dig_structs.h:1727
struct bound_box * box
Array of bounding boxes.
Definition: dig_structs.h:1731
int n_values
Number of items in the list.
Definition: dig_structs.h:1739
List of integers.
Definition: gis.h:709
int n_values
Number of values in the list.
Definition: gis.h:717
int * value
Array of values.
Definition: gis.h:713
Feature geometry info - coordinates.
Definition: dig_structs.h:1651
double * y
Array of Y coordinates.
Definition: dig_structs.h:1659
double * x
Array of X coordinates.
Definition: dig_structs.h:1655
int n_points
Number of points.
Definition: dig_structs.h:1667
Definition: manage.h:4