1 /* ****************************************************************************
2 *
3 * MODULE: v.overlay
4 *
5 * AUTHOR(S): Radim Blazek, Markus Metz
6 *
7 ******************************************************************************/
8 #include <stdlib.h>
9 #include <string.h>
10 #include <stdio.h>
11 #include <grass/gis.h>
12 #include <grass/dbmi.h>
13 #include <grass/vector.h>
14 #include <grass/glocale.h>
15 #include "local.h"
16
17 /* compare category structures
18 * return 0 identical
19 * return 1 not identical
20 */
compare_cats(struct line_cats * ACats,struct line_cats * BCats)21 static int compare_cats(struct line_cats *ACats, struct line_cats *BCats)
22 {
23 int i, j;
24
25 if (ACats->n_cats == 0 || BCats->n_cats == 0) {
26 if (ACats->n_cats == 0 && BCats->n_cats == 0)
27 return 0;
28
29 if (ACats->n_cats == 0 && BCats->n_cats > 0)
30 return 1;
31
32 if (ACats->n_cats > 0 && BCats->n_cats == 0)
33 return 1;
34 }
35
36 for (i = 0; i < ACats->n_cats; i++) {
37 int found = 0;
38
39 for (j = 0; j < BCats->n_cats; j++) {
40 if (ACats->cat[i] == BCats->cat[j] &&
41 ACats->field[i] == BCats->field[j]) {
42 found = 1;
43 break;
44 }
45 }
46 if (!found)
47 return 1;
48 }
49
50 return 0;
51 }
52
53 /* merge a given line with all other lines of the same type and
54 * with the same categories */
merge_line(struct Map_info * Map,int line,struct line_pnts * MPoints,struct line_cats * MCats)55 static int merge_line(struct Map_info *Map, int line,
56 struct line_pnts *MPoints, struct line_cats *MCats)
57 {
58 int nlines, i, first, last, next_line, curr_line;
59 int merged = 0, newl = 0;
60 int next_node, direction, node_n_lines, type, ltype, lines_type;
61 static struct ilist *List = NULL;
62 static struct line_pnts *Points = NULL;
63 static struct line_cats *Cats = NULL;
64 type = GV_LINE;
65
66 nlines = Vect_get_num_lines(Map);
67
68 if (!Points)
69 Points = Vect_new_line_struct();
70 if (!Cats)
71 Cats = Vect_new_cats_struct();
72 if (!List)
73 List = Vect_new_list();
74
75 Vect_reset_line(Points);
76 Vect_reset_cats(Cats);
77 Vect_reset_cats(MCats);
78 Vect_reset_list(List);
79
80 if (!Vect_line_alive(Map, line))
81 return 0;
82
83 ltype = Vect_get_line_type(Map, line);
84
85 if (!(ltype & type))
86 return 0;
87
88 Vect_read_line(Map, MPoints, MCats, line);
89
90 /* special cases:
91 * - loop back to start boundary via several other boundaries
92 * - one boundary forming closed loop
93 * - node with 3 entries but only 2 boundaries, one of them connecting twice,
94 * the other one must then be topologically incorrect in case of boundary */
95
96 /* go backward as long as there is only one other line/boundary at the current node */
97 G_debug(3, "go backward");
98 Vect_get_line_nodes(Map, line, &next_node, NULL);
99
100 first = -line;
101 while (1) {
102 node_n_lines = Vect_get_node_n_lines(Map, next_node);
103 /* count lines/boundaries at this node */
104 lines_type = 0;
105 next_line = first;
106 for (i = 0; i < node_n_lines; i++) {
107 curr_line = Vect_get_node_line(Map, next_node, i);
108 if ((Vect_get_line_type(Map, abs(curr_line)) & GV_LINES))
109 lines_type++;
110 if ((Vect_get_line_type(Map, abs(curr_line)) == ltype)) {
111 if (abs(curr_line) != abs(first)) {
112 Vect_read_line(Map, NULL, Cats, abs(curr_line));
113
114 /* catgories must be identical */
115 if (compare_cats(MCats, Cats) == 0)
116 next_line = curr_line;
117 }
118 }
119 }
120 if (lines_type == 2 && abs(next_line) != abs(first) &&
121 abs(next_line) != line) {
122 first = next_line;
123
124 if (first < 0) {
125 Vect_get_line_nodes(Map, -first, &next_node, NULL);
126 }
127 else {
128 Vect_get_line_nodes(Map, first, NULL, &next_node);
129 }
130 }
131 else
132 break;
133 }
134
135 /* go forward as long as there is only one other line/boundary at the current node */
136 G_debug(3, "go forward");
137
138 /* reverse direction */
139 last = -first;
140
141 if (last < 0) {
142 Vect_get_line_nodes(Map, -last, &next_node, NULL);
143 }
144 else {
145 Vect_get_line_nodes(Map, last, NULL, &next_node);
146 }
147
148 Vect_reset_list(List);
149 while (1) {
150 G_ilist_add(List, last);
151 node_n_lines = Vect_get_node_n_lines(Map, next_node);
152 lines_type = 0;
153 next_line = last;
154 for (i = 0; i < node_n_lines; i++) {
155 curr_line = Vect_get_node_line(Map, next_node, i);
156 if ((Vect_get_line_type(Map, abs(curr_line)) & GV_LINES))
157 lines_type++;
158 if ((Vect_get_line_type(Map, abs(curr_line)) == ltype)) {
159 if (abs(curr_line) != abs(last)) {
160 Vect_read_line(Map, NULL, Cats, abs(curr_line));
161
162 if (compare_cats(MCats, Cats) == 0)
163 next_line = curr_line;
164 }
165 }
166 }
167
168 if (lines_type == 2 && abs(next_line) != abs(last) &&
169 abs(next_line) != abs(first)) {
170 last = next_line;
171
172 if (last < 0) {
173 Vect_get_line_nodes(Map, -last, &next_node, NULL);
174 }
175 else {
176 Vect_get_line_nodes(Map, last, NULL, &next_node);
177 }
178 }
179 else
180 break;
181 }
182
183 /* merge lines */
184 G_debug(3, "merge %d lines", List->n_values);
185 Vect_reset_line(MPoints);
186
187 for (i = 0; i < List->n_values; i++) {
188 Vect_reset_line(Points);
189 Vect_read_line(Map, Points, Cats, abs(List->value[i]));
190 direction = (List->value[i] < 0 ? GV_BACKWARD : GV_FORWARD);
191 Vect_append_points(MPoints, Points, direction);
192 MPoints->n_points--;
193 Vect_delete_line(Map, abs(List->value[i]));
194 }
195 MPoints->n_points++;
196 merged += List->n_values;
197 newl++;
198
199 return merged;
200 }
201
202 /* Check if point is inside area with category of given field. All cats are set in
203 * Cats with original field.
204 * returns number of cats.
205 */
point_area(struct Map_info * Map,int field,double x,double y,struct line_cats * Cats)206 int point_area(struct Map_info *Map, int field, double x, double y,
207 struct line_cats *Cats)
208 {
209 int i, area, centr;
210 static struct line_cats *CCats = NULL;
211
212 Vect_reset_cats(Cats);
213 area = Vect_find_area(Map, x, y);
214 G_debug(4, " area = %d", area);
215
216 if (!area)
217 return 0;
218
219 centr = Vect_get_area_centroid(Map, area);
220
221 if (centr <= 0)
222 return 0;
223
224 if (!CCats)
225 CCats = Vect_new_cats_struct();
226 Vect_read_line(Map, NULL, CCats, centr);
227
228 for (i = 0; i < CCats->n_cats; i++) {
229 if (CCats->field[i] == field) {
230 Vect_cat_set(Cats, field, CCats->cat[i]);
231 }
232 }
233
234 return Cats->n_cats;
235 }
236
line_area(struct Map_info * In,int * field,struct Map_info * Tmp,struct Map_info * Out,struct field_info * Fi,dbDriver * driver,int operator,int * ofield,ATTRIBUTES * attr,struct ilist * BList)237 int line_area(struct Map_info *In, int *field, struct Map_info *Tmp,
238 struct Map_info *Out, struct field_info *Fi,
239 dbDriver * driver, int operator, int *ofield,
240 ATTRIBUTES * attr, struct ilist *BList)
241 {
242 int i, line, nlines, ncat;
243 struct line_pnts *Points;
244 struct line_cats *Cats, *ACats, *OCats;
245 double x, y;
246
247 char buf[1000];
248 dbString stmt;
249
250 Points = Vect_new_line_struct();
251 Cats = Vect_new_cats_struct();
252 ACats = Vect_new_cats_struct();
253 OCats = Vect_new_cats_struct();
254 db_init_string(&stmt);
255
256 G_message(_("Breaking lines..."));
257 Vect_break_lines_list(Tmp, NULL, BList, GV_LINE | GV_BOUNDARY, NULL);
258
259 /*
260 G_message(_("Merging lines..."));
261 Vect_merge_lines(Tmp, GV_LINE, NULL, NULL);
262 */
263
264 nlines = Vect_get_num_lines(Tmp);
265
266 /* Warning!: cleaning process (break) creates new vertices which are usually slightly
267 * moved (RE), to compare such new vertex with original input is a problem?
268 *
269 * TODO?: would it be better to copy centroids also and query output map?
270 */
271
272 /* Check if the line is inside or outside binput area */
273 G_message(_("Selecting lines..."));
274 ncat = 1;
275 for (line = 1; line <= nlines; line++) {
276 int ltype;
277
278 G_percent(line, nlines, 1); /* must be before any continue */
279
280 if (!Vect_line_alive(Tmp, line))
281 continue;
282
283 ltype = Vect_get_line_type(Tmp, line);
284
285 if (ltype == GV_BOUNDARY) { /* No more needed */
286 continue;
287 }
288
289 /* Now the type should be only GV_LINE */
290
291 /* Decide if the line is inside or outside the area. In theory:
292 * 1) All vertices outside
293 * - easy, first vertex must be outside
294 * 2) All vertices inside
295 * 3) All vertices on the boundary, we take it as inside (attention,
296 * result of Vect_point_in_area() for points on segments between vertices may be both
297 * inside or outside, because of representation of numbers)
298 * 4) One or two end vertices on the boundary, all others outside
299 * 5) One or two end vertices on the boundary, all others inside
300 *
301 */
302
303 /* Note/TODO: the test done is quite simple, check the point in the middle of segment.
304 * If the line overlaps the boundary, the result may be both outside and inside
305 * this should be solved (check angles?)
306 * This should not happen if Vect_break_lines_list() works correctly
307 * The problem is the middle of the segment. Use line vertices
308 * if possible, avoid calculating middle of the segment
309 */
310
311 /* merge here */
312 merge_line(Tmp, line, Points, Cats);
313
314 G_debug(3, "line = %d", line);
315
316 if (Points->n_points < 2)
317 continue;
318
319 if (Points->n_points == 2) {
320 /* only 2 vertices, must use mid-segment point */
321 x = (Points->x[0] + Points->x[1]) / 2;
322 y = (Points->y[0] + Points->y[1]) / 2;
323 point_area(&(In[1]), field[1], x, y, ACats);
324 }
325 else {
326 /* more than 2 vertices
327 * find a point that is really outside any area
328 * this skips points that are on the boundary
329 * do not calculate mid-segment points because of RE
330 */
331
332 int ret;
333
334 i = (Points->n_points - 1) / 2;
335 x = Points->x[i];
336 y = Points->y[i];
337 ret = point_area(&(In[1]), field[1], x, y, ACats);
338 if (ret && Points->n_points > 3) {
339
340 i++;
341 x = Points->x[i];
342 y = Points->y[i];
343 ret = point_area(&(In[1]), field[1], x, y, ACats);
344 if (!ret)
345 G_warning(_("Ambiguous line %d: not all vertices are really outside any area"),
346 line);
347 }
348 }
349
350 if ((ACats->n_cats > 0 && operator == OP_AND) ||
351 (ACats->n_cats == 0 && operator == OP_NOT)) {
352
353 /* Point is inside */
354 G_debug(3, "OK, write line, line ncats = %d area ncats = %d",
355 Cats->n_cats, ACats->n_cats);
356
357 Vect_reset_cats(OCats);
358
359 if (ofield[0] > 0) {
360 /* rewrite with all combinations of acat - bcat (-1 in cycle for null) */
361 for (i = -1; i < Cats->n_cats; i++) { /* line cats */
362 int j;
363
364 if (i == -1 && Cats->n_cats > 0)
365 continue; /* no need to make null */
366
367 for (j = -1; j < ACats->n_cats; j++) {
368 if (j == -1 && ACats->n_cats > 0)
369 continue; /* no need to make null */
370
371 if (ofield[0] > 0)
372 Vect_cat_set(OCats, ofield[0], ncat);
373
374 /* Attributes */
375 if (driver) {
376 ATTR *at;
377
378 sprintf(buf, "insert into %s values ( %d", Fi->table,
379 ncat);
380 db_set_string(&stmt, buf);
381
382 /* cata */
383 if (i >= 0) {
384 if (attr[0].columns) {
385 at = find_attr(&(attr[0]), Cats->cat[i]);
386 if (!at)
387 G_fatal_error(_("Attribute not found"));
388
389 if (at->values)
390 db_append_string(&stmt, at->values);
391 else
392 db_append_string(&stmt,
393 attr[0].null_values);
394 }
395 else {
396 sprintf(buf, ", %d", Cats->cat[i]);
397 db_append_string(&stmt, buf);
398 }
399 }
400 else {
401 if (attr[0].columns) {
402 db_append_string(&stmt, attr[0].null_values);
403 }
404 else {
405 sprintf(buf, ", null");
406 db_append_string(&stmt, buf);
407 }
408 }
409
410 /* catb */
411 if (j >= 0) {
412 if (attr[1].columns) {
413 at = find_attr(&(attr[1]), ACats->cat[j]);
414 if (!at)
415 G_fatal_error(_("Attribute not found"));
416
417 if (at->values)
418 db_append_string(&stmt, at->values);
419 else
420 db_append_string(&stmt,
421 attr[1].null_values);
422 }
423 else {
424 sprintf(buf, ", %d", ACats->cat[j]);
425 db_append_string(&stmt, buf);
426 }
427 }
428 else {
429 if (attr[1].columns) {
430 db_append_string(&stmt, attr[1].null_values);
431 }
432 else {
433 sprintf(buf, ", null");
434 db_append_string(&stmt, buf);
435 }
436 }
437
438 db_append_string(&stmt, " )");
439
440 G_debug(3, "%s", db_get_string(&stmt));
441
442 if (db_execute_immediate(driver, &stmt) != DB_OK)
443 G_warning(_("Unable to insert new record: '%s'"),
444 db_get_string(&stmt));
445 }
446
447 ncat++;
448 }
449 }
450 }
451
452 /* Add cats from input vectors */
453 if (ofield[1] > 0 && field[0] > 0) {
454 for (i = 0; i < Cats->n_cats; i++) {
455 if (Cats->field[i] == field[0])
456 Vect_cat_set(OCats, ofield[1], Cats->cat[i]);
457 }
458 }
459
460 if (ofield[2] > 0 && field[1] > 0 && ofield[1] != ofield[2]) {
461 for (i = 0; i < ACats->n_cats; i++) {
462 if (ACats->field[i] == field[1])
463 Vect_cat_set(OCats, ofield[2], ACats->cat[i]);
464 }
465 }
466
467 Vect_write_line(Out, ltype, Points, OCats);
468 }
469 }
470
471 return 0;
472 }
473