OpenLayers OpenLayers

Changeset 5443

Show
Ignore:
Timestamp:
12/16/07 19:24:34 (1 year ago)
Author:
tschaub
Message:

intersects method for all geometry types - passes all 490 geos intersection tests

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • sandbox/tschaub/geom/examples/intersects.html

    r4888 r5443  
    11<html xmlns="http://www.w3.org/1999/xhtml"> 
    22  <head> 
    3     <title>Vector Formats</title> 
     3    <title>Geometry Intersections</title> 
    44    <style type="text/css"> 
    55        html, body { 

  • sandbox/tschaub/geom/lib/OpenLayers/Geometry/LinearRing.js

    r5290 r5443  
    178178    /** 
    179179     * Method: containsPoint 
    180      * Test if a point is inside a linear ring. 
     180     * Test if a point is inside a linear ring.  For the case where a point 
     181     *     is coincident with a linear ring edge, returns 1.  Otherwise, 
     182     *     returns boolean. 
    181183     * 
    182184     * Parameters: 
    …… 
    184186     * 
    185187     * Returns: 
    186      * {Boolean} The point is inside the linear ring. 
     188     * {Boolean | Number} The point is inside the linear ring.  Returns 1 if 
     189     *     the point is coincident with an edge.  Returns boolean otherwise. 
    187190     */ 
    188191    containsPoint: function(point) { 
    …… 
    193196        } 
    194197        var numSeg = this.components.length - 1; 
    195         var start, end, x1, y1, x2, y2, cx; 
     198        var start, end, x1, y1, x2, y2, cx, cy; 
    196199        var crosses = 0; 
    197200        for(var i=0; i<numSeg; ++i) { 
    …… 
    204207             
    205208            /** 
    206              * The following conditions enforce four edge-crossing rules: 
    207              *    1. an upward edge includes its starting endpoint, and 
     209             * The following conditions enforce five edge-crossing rules: 
     210             *    1. points coincident with edges are considered contained; 
     211             *    2. an upward edge includes its starting endpoint, and 
    208212             *    excludes its final endpoint; 
    209              *    2. a downward edge excludes its starting endpoint, and 
     213             *    3. a downward edge excludes its starting endpoint, and 
    210214             *    includes its final endpoint; 
    211              *    3. horizontal edges are excluded; and 
    212              *    4. the edge-ray intersection point must be strictly right 
     215             *    4. horizontal edges are excluded; and 
     216             *    5. the edge-ray intersection point must be strictly right 
    213217             *    of the point P. 
    214218             */ 
    215219            if(y1 == y2) { 
    216                 // ignore horizontal edges 
     220                // horizontal edge 
     221                if(py == y1) { 
     222                    // point on horizontal line 
     223                    if(x1 <= x2 && (px >= x1 && px <= x2) || // right or vert 
     224                       x1 >= x2 && (px <= x1 && px >= x2)) { // left or vert 
     225                        // point on edge 
     226                        crosses = -1; 
     227                        break; 
     228                    } 
     229                } 
     230                // ignore other horizontal edges 
    217231                continue; 
    218232            } 
    219233            cx = getX(py, x1, y1, x2, y2); 
     234            if(cx == px) { 
     235                // point on line 
     236                if(y1 < y2 && (py >= y1 && py <= y2) || // upward 
     237                   y1 > y2 && (py <= y1 && py >= y2)) { // downward 
     238                    // point on edge 
     239                    crosses = -1; 
     240                    break; 
     241                } 
     242            } 
    220243            if(cx <= px) { 
    221244                // no crossing to the right 
    …… 
    231254            } 
    232255        } 
    233         // even (out) or odd (in) 
    234         return !!(crosses & 1); 
     256        var contained = (crosses == -1) ? 
     257            // on edge 
     258            1 : 
     259            // even (out) or odd (in) 
     260            !!(crosses & 1); 
     261 
     262        return contained; 
    235263    }, 
    236264 

  • sandbox/tschaub/geom/lib/OpenLayers/Geometry/Polygon.js

    r5290 r5443  
    6060    /** 
    6161     * Method: containsPoint 
    62      * Test if a point is inside a polygon. 
     62     * Test if a point is inside a polygon.  Points on a polygon edge are 
     63     *     considered inside. 
    6364     * 
    6465     * Parameters: 
    …… 
    6667     * 
    6768     * Returns: 
    68      * {Boolean} The point is inside the polygon. 
     69     * {Boolean | Number} The point is inside the polygon.  Returns 1 if the 
     70     *     point is on an edge.  Returns boolean otherwise. 
    6971     */ 
    7072    containsPoint: function(point) { 
    …… 
    7274        var contained = false; 
    7375        if(numRings > 0) { 
    74             // check exterior ring 
     76            // check exterior ring - 1 means on edge, boolean otherwise 
    7577            contained = this.components[0].containsPoint(point); 
    76             if(contained && numRings > 1) { 
    77                 // check interior rings 
    78                 var hole; 
    79                 for(var i=1; i<numRings; ++i) { 
    80                     hole = this.components[i].containsPoint(point); 
    81                     if(hole) { 
    82                         contained = false; 
    83                         break; 
     78            if(contained !== 1) { 
     79                if(contained && numRings > 1) { 
     80                    // check interior rings 
     81                    var hole; 
     82                    for(var i=1; i<numRings; ++i) { 
     83                        hole = this.components[i].containsPoint(point); 
     84                        if(hole) { 
     85                            if(hole === 1) { 
     86                                // on edge 
     87                                contained = 1; 
     88                            } else { 
     89                                // in hole 
     90                                contained = false; 
     91                            }                             
     92                            break; 
     93                        } 
    8494                    } 
    8595                } 

  • sandbox/tschaub/geom/tests/test_Geometry.html

    r4947 r5443  
    22<head> 
    33  <script src="../lib/OpenLayers.js"></script> 
    4   <script src="data/geometry-intersects.js"></script> 
    54  <script src="data/geos_wkt_intersects.js"></script> 
    65  <script type="text/javascript"> 
    …… 
    253252        } 
    254253    }     
    255      
    256     function test_Geometry_intersects(t) { 
    257         var geojson = new OpenLayers.Format.GeoJSON(); 
    258         var features = geojson.read(intersectionFeatures); 
    259         var feat1, feat2; 
    260         var failures = []; 
    261         for(var i=0; i<features.length; ++i) { 
    262             features[i].attributes.test = []; 
    263         } 
    264         for(var i=0; i<features.length-1; ++i) { 
    265             feat1 = features[i]; 
    266             for(var j=i+1; j<features.length; ++j) { 
    267                 feat2 = features[j]; 
    268                 intersects12 = feat1.geometry.intersects(feat2.geometry); 
    269                 if(intersects12) { 
    270                     feat1.attributes.test.push("f" + j); 
    271                 } 
    272                 intersects21 = feat2.geometry.intersects(feat1.geometry); 
    273                 if(intersects21) { 
    274                     feat2.attributes.test.push("f" + i); 
    275                 } 
    276                 if(intersects12 != intersects21) { 
    277                     failures.push("trouble with features " + i + " and " + j); 
    278                 } 
    279             } 
    280         } 
    281         t.plan(features.length + failures.length); 
    282         for(i=0; i<features.length; ++i) { 
    283             t.eq(features[i].attributes.intersectsWith, 
    284                  features[i].attributes.test, 
    285                  "correct intersections (" + features[i].attributes.test.length + ") for feature " + i); 
    286         } 
    287         for(i=0; i<failures.length; ++i) { 
    288             t.fail(failures[i]); 
    289         } 
    290         if(features.length == 0) { 
    291             t.fail("no features loaded from data/geometry-intersects.js"); 
    292         } 
    293     } 
    294254 
    295255  </script>