GRASS 8 Programmer's Manual 8.6.0dev(2026)-f6f2c534ea
Loading...
Searching...
No Matches
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 */
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++;
60 }
61 if (plus->n_clines != 0) {
62 ntypes++;
64 }
65 if (plus->n_flines != 0) {
66 ntypes++;
67 mtype |= GV_FACE;
68 }
69 if (plus->n_klines != 0) {
70 ntypes++;
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));
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 */
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 */
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 */
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
234 if (!LPoints)
236 if (!LocList) {
238 }
239
240 /* Select first all lines by box */
243 box.B = -PORT_DOUBLE_MAX;
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 */
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 */
283 Vect_list_append(List, line);
284 continue;
285 }
286
287 /* Islands */
288 for (j = 0; j < nisles; j++) {
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
328 if (!BoundList)
330
331 /* Select boundaries by polygon */
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
const char * G_getenv_nofatal(const char *)
Get environment variable.
Definition env.c:405
#define G_malloc(n)
Definition defs/gis.h:139
int G_debug(int, const char *,...) __attribute__((format(printf
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.
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 ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
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:347
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition line.c:45
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
#define GV_LINE
#define GV_POINT
Feature types used in memory on run time (may change)
#define GV_BOUNDARY
#define GV_FACE
#define PORT_DOUBLE_MAX
Limits for portable types.
Definition dig_defines.h:66
#define GV_KERNEL
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:971
int dig_select_lines(struct Plus_head *, const struct bound_box *, struct boxlist *)
Select lines with boxes by box.
Definition spindex.c:759
int dig_select_areas(struct Plus_head *, const struct bound_box *, struct boxlist *)
Select areas with boxes by box.
Definition spindex.c:875
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:668
int dig_line_box(const struct line_pnts *, struct bound_box *)
float Box[8][3]
Vertices for box.
Definition gsd_objs.c:1455
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.
Vector geometry.
char type
Line type.
Basic topology-related info.
plus_t n_klines
Current number of kernels.
struct P_line ** Line
Array of vector geometries.
plus_t n_plines
Current number of points.
plus_t n_blines
Current number of boundaries.
plus_t n_clines
Current number of centroids.
plus_t n_flines
Current number of faces.
plus_t n_llines
Current number of lines.
Bounding box.
Definition dig_structs.h:62
List of bounding boxes with id.
struct bound_box * box
Array of bounding boxes.
List of integers.
Definition gis.h:715
Feature geometry info - coordinates.
Definition manage.h:4