Changeset 62091

Timestamp:

Sep 26, 2014, 5:52:24 AM (10 years ago)

Author:

mmetz

Message:

v.select: speed up OP_OVERLAP

Location:

grass/trunk/vector/v.select

Files:

• overlap.c (modified) (2 diffs)
• proto.h (modified) (1 diff)
• select.c (modified) (8 diffs)

grass/trunk/vector/v.select/overlap.c

@@ -39 +39 @@
 /* Returns 1 if line1 from Map1 overlaps area2 from Map2,
  *         0 otherwise */
-int line_overlap_area(struct Map_info *LMap, int line, struct Map_info *AMap,
-                      int area, struct bound_box box)
+int line_overlap_area(struct line_pnts *LPoints, struct Map_info *AMap,
+                      int area)
 {
     int i, nisles, isle;
-    static struct line_pnts *LPoints = NULL;
     static struct line_pnts *APoints = NULL;
+    static struct line_pnts **IPoints = NULL;
+    static int isles_alloc = 0;
 
-    G_debug(4, "line_overlap_area line = %d area = %d", line, area);
+    G_debug(4, "line_overlap_area area = %d", area);
 
-    if (!LPoints) {
-        LPoints = Vect_new_line_struct();
+    if (!APoints) {
         APoints = Vect_new_line_struct();
+        isles_alloc = 10;
+        IPoints = G_malloc(isles_alloc * sizeof(struct line_pnts *));
+        for (i = 0; i < isles_alloc; i++)
+            IPoints[i] = Vect_new_line_struct();
     }
 
-    /* Read line coordinates */
-    Vect_read_line(LMap, LPoints, NULL, line);
+    Vect_get_area_points(AMap, area, APoints);
+    nisles = Vect_get_area_num_isles(AMap, area);
+
+    if (nisles >= isles_alloc) {
+        IPoints = G_realloc(IPoints, (nisles + 10) * sizeof(struct line_pnts *));
+        for (i = isles_alloc; i < nisles + 10; i++)
+            IPoints[i] = Vect_new_line_struct();
+        isles_alloc = nisles + 10;
+    }
+
+    for (i = 0; i < nisles; i++) {
+        isle = Vect_get_area_isle(AMap, area, i);
+        Vect_get_isle_points(AMap, isle, IPoints[i]);
+    }
 
     /* Try if any of line vertices is within area */
     for (i = 0; i < LPoints->n_points; i++) {
-        if (Vect_point_in_area(LPoints->x[i], LPoints->y[i], AMap, area, &box)) {
-            G_debug(4, "  -> line vertex inside area");
-            return 1;
+
+        if (Vect_point_in_poly(LPoints->x[i], LPoints->y[i], APoints)) {
+            int inside = 1;
+            
+            for (isle = 0; isle < nisles; isle++) {
+                if (Vect_point_in_poly(LPoints->x[i], LPoints->y[i], IPoints[isle])) {
+                    inside = 0;
+                    break;
+                }
+            }
+            if (inside) {
+                G_debug(4, "  -> line vertex inside area");
+                return 1;
+            }
         }
     }
@@ -70 +97 @@
     /* Try intersections of line with area/isles boundary */
     /* Outer boundary */
-    Vect_get_area_points(AMap, area, APoints);
 
-    if (Vect_line_check_intersection(LPoints, APoints, 0)) {
+    if (Vect_line_check_intersection2(LPoints, APoints, 0)) {
         G_debug(4, "  -> line intersects outer area boundary");
         return 1;
     }
 
-    nisles = Vect_get_area_num_isles(AMap, area);
+    for (i = 0; i < nisles; i++) {
 
-    for (i = 0; i < nisles; i++) {
-        isle = Vect_get_area_isle(AMap, area, i);
-        Vect_get_isle_points(AMap, isle, APoints);
-
-        if (Vect_line_check_intersection(LPoints, APoints, 0)) {
+        if (Vect_line_check_intersection2(LPoints, IPoints[i], 0)) {
             G_debug(4, "  -> line intersects area island boundary");
             return 1;

grass/trunk/vector/v.select/proto.h

@@ -43 +43 @@
 /* overlap.c */
 void add_aarea(struct Map_info *, int, int *);
-int line_overlap_area(struct Map_info *, int, struct Map_info *, int, struct bound_box);
+int line_overlap_area(struct line_pnts *, struct Map_info *, int);
 
 /* write.c */

grass/trunk/vector/v.select/select.c

@@ -35 +35 @@
 
     nalines = Vect_get_num_lines(aIn);
-    if (operator == OP_OVERLAP)
-        G_message("Using GRASS GIS operator...");
-    else
-        G_message("Using GEOS operator...");
     
     /* Lines in A. Go through all lines and mark those that meets condition */
@@ -44 +40 @@
         G_message(_("Processing features..."));
         
+        G_percent(0, nalines, 2);
         for (aline = 1; aline <= nalines; aline++) {
             struct bound_box abox;
@@ -110 +107 @@
                         Vect_read_line(bIn, BPoints, NULL, bline);
 
-                        if (Vect_line_check_intersection(APoints, BPoints, 0)) {
+                        if (Vect_line_check_intersection2(APoints, BPoints, 0)) {
                             found = 1;
                             break;
@@ -148 +145 @@
                     }
                     else {
-                        if (line_overlap_area(aIn, aline, bIn, barea, List->box[i])) {
+                        if (line_overlap_area(APoints, bIn, barea)) {
                             ALines[aline] = 1;
                             break;
@@ -172 +169 @@
         naareas = Vect_get_num_areas(aIn);
 
+        G_percent(0, naareas, 2);
         for (aarea = 1; aarea <= naareas; aarea++) {
             struct bound_box abox;
 
-            G_percent(aarea, naareas, 2);       /* must be before any continue */
+            G_percent(aarea, naareas, 1);
 
             if (Vect_get_area_cat(aIn, aarea, afield) < 0) {
@@ -220 +218 @@
                     }
                     else {
-                        if (line_overlap_area(bIn, bline, aIn, aarea, abox)) {
+                        Vect_read_line(bIn, BPoints, NULL, bline);
+
+                        if (line_overlap_area(BPoints, aIn, aarea)) {
                             add_aarea(aIn, aarea, ALines);
                             continue;
@@ -262 +262 @@
 
                     aline = abs(LList->value[i]);
+                    Vect_read_line(aIn, APoints, NULL, aline);
 
                     for (j = 0; j < TmpList->n_values; j++) {
@@ -303 +304 @@
                             
                             /* Check intersectin of lines from List with area B */
-                            if (line_overlap_area(aIn, aline,
-                                                  bIn, barea, TmpList->box[j])) {
+                            if (line_overlap_area(APoints, bIn, barea)) {
                                 found = 1;
                                 break;