Ignore:
Timestamp:
2010-10-25T09:02:22+02:00 (14 years ago)
Author:
extropy
Message:

Improved polygon intersection code.

Location:
applications/editors/josm/plugins/multipoly/src/multipoly
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • applications/editors/josm/plugins/multipoly/src/multipoly/GeometryFunctions.java

    r23771 r23819  
    1515 */
    1616public class GeometryFunctions {
    17         public enum Intersection {INSIDE, OUTSIDE, CROSSING, EQUAL}
    18        
    19     /**
    20      * Finds the intersection of two lines of inifinite length.
    21      * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
    22      */
    23     public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
    24 
    25         // Convert line from (point, point) form to ax+by=c
    26         double a1 = p2.getY() - p1.getY();
    27         double b1 = p1.getX() - p2.getX();
    28         double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
    29 
    30         double a2 = p4.getY() - p3.getY();
    31         double b2 = p3.getX() - p4.getX();
    32         double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
    33 
    34         // Solve the equations
    35         double det = a1 * b2 - a2 * b1;
    36         if (det == 0)
    37             return null; // Lines are parallel
    38 
    39         return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
    40     }
    41 
    42     public static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
    43 
    44         // Convert line from (point, point) form to ax+by=c
    45         double a1 = p2.getY() - p1.getY();
    46         double b1 = p1.getX() - p2.getX();
    47 
    48         double a2 = p4.getY() - p3.getY();
    49         double b2 = p3.getX() - p4.getX();
    50 
    51         // Solve the equations
    52         double det = a1 * b2 - a2 * b1;
    53         return Math.abs(det) < 1e-13;
    54     }
    55 
    56     /**
    57      * Calcualtes closest point to a line segment.
    58      * @param segmentP1
    59      * @param segmentP2
    60      * @param point
    61      * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point,
    62      * a new point if closest point is between segmentP1 and segmentP2.
    63      */
    64     public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) {
    65 
    66         double ldx = segmentP2.getX() - segmentP1.getX();
    67         double ldy = segmentP2.getY() - segmentP1.getY();
    68 
    69         if (ldx == 0 && ldy == 0) //segment zero length
    70             return segmentP1;
    71 
    72         double pdx = point.getX() - segmentP1.getX();
    73         double pdy = point.getY() - segmentP1.getY();
    74 
    75         double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
    76 
    77         if (offset <= 0)
    78             return segmentP1;
    79         else if (offset >= 1)
    80             return segmentP2;
    81         else
    82             return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset);
    83 
    84     }   
    85        
    86     /**
    87      * This method tests if secondNode is clockwise to first node.
    88      * @param commonNode starting point for both vectors
    89      * @param firstNode first vector end node
    90      * @param secondNode second vector end node
    91      * @return true if first vector is clockwise before second vector.
    92      */
    93 
    94     public static boolean angleIsClockwise(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) {
    95         double dy1 = (firstNode.getY() - commonNode.getY());
    96         double dy2 = (secondNode.getY() - commonNode.getY());
    97         double dx1 = (firstNode.getX() - commonNode.getX());
    98         double dx2 = (secondNode.getX() - commonNode.getX());
    99 
    100         return dy1 * dx2 - dx1 * dy2 > 0;
    101     }
    102 
    103 
    104     /**
    105      * Tests if two polygons instersect.
    106      * @param first
    107      * @param second
    108      * @return Inside if second is inside first, Outside, if second is outside first, Crossing, if they cross.
    109      */
    110     public static Intersection polygonIntersection(List<Node> outside, List<Node> inside) {
    111         Set<Node> outsideNodes = new HashSet<Node>(outside);
    112        
    113         boolean nodesInside = false;
    114         boolean nodesOutside = false;
    115        
    116         for (Node insideNode : inside) {
    117             if (!outsideNodes.contains(insideNode)) {
    118                 if (nodeInsidePolygon(insideNode, outside)) {
    119                         nodesInside = true;
    120                 }
    121                 else {
    122                         nodesOutside = true;
    123                 }
    124             }
    125         }
    126 
    127         if (nodesInside) {
    128                 if (nodesOutside){
    129                         return Intersection.CROSSING;
    130                 }
    131                 else {
    132                         return Intersection.INSIDE;
    133                 }
    134         }
    135         else {
    136                 if (nodesOutside){
    137                         return Intersection.OUTSIDE;
    138                 }
    139                 else {
    140                         return Intersection.EQUAL;
    141                 }
    142         }
    143     }
    144 
    145     /**
    146      * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
    147      * @param polygonNodes list of nodes from polygon path.
    148      * @param point the point to test
    149      * @return true if the point is inside polygon.
    150      */
    151     public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
    152         if (polygonNodes.size() < 2)
    153             return false;
    154 
    155         boolean inside = false;
    156         Node p1, p2;
    157 
    158         //iterate each side of the polygon, start with the last segment
    159         Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
    160 
    161         for (Node newPoint : polygonNodes) {
    162             //skip duplicate points
    163             if (newPoint.equals(oldPoint)) {
    164                 continue;
    165             }
    166 
    167             //order points so p1.lat <= p2.lat;
    168             if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
    169                 p1 = oldPoint;
    170                 p2 = newPoint;
    171             } else {
    172                 p1 = newPoint;
    173                 p2 = oldPoint;
    174             }
    175 
    176             //test if the line is crossed and if so invert the inside flag.
    177             if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
    178                     && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
    179                     < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
    180             {
    181                 inside = !inside;
    182             }
    183 
    184             oldPoint = newPoint;
    185         }
    186 
    187         return inside;
    188     }
     17        public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING}
     18
     19        /**
     20         * Finds the intersection of two lines of infinite length.
     21         * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
     22         */
     23        public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
     24
     25                // Convert line from (point, point) form to ax+by=c
     26                double a1 = p2.getY() - p1.getY();
     27                double b1 = p1.getX() - p2.getX();
     28                double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
     29
     30                double a2 = p4.getY() - p3.getY();
     31                double b2 = p3.getX() - p4.getX();
     32                double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
     33
     34                // Solve the equations
     35                double det = a1 * b2 - a2 * b1;
     36                if (det == 0)
     37                        return null; // Lines are parallel
     38
     39                return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
     40        }
     41
     42        public static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
     43
     44                // Convert line from (point, point) form to ax+by=c
     45                double a1 = p2.getY() - p1.getY();
     46                double b1 = p1.getX() - p2.getX();
     47
     48                double a2 = p4.getY() - p3.getY();
     49                double b2 = p3.getX() - p4.getX();
     50
     51                // Solve the equations
     52                double det = a1 * b2 - a2 * b1;
     53                return Math.abs(det) < 1e-13;
     54        }
     55
     56        /**
     57         * Calculates closest point to a line segment.
     58         * @param segmentP1
     59         * @param segmentP2
     60         * @param point
     61         * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point,
     62         * a new point if closest point is between segmentP1 and segmentP2.
     63         */
     64        public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) {
     65
     66                double ldx = segmentP2.getX() - segmentP1.getX();
     67                double ldy = segmentP2.getY() - segmentP1.getY();
     68
     69                if (ldx == 0 && ldy == 0) //segment zero length
     70                        return segmentP1;
     71
     72                double pdx = point.getX() - segmentP1.getX();
     73                double pdy = point.getY() - segmentP1.getY();
     74
     75                double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
     76
     77                if (offset <= 0)
     78                        return segmentP1;
     79                else if (offset >= 1)
     80                        return segmentP2;
     81                else
     82                        return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset);
     83
     84        }
     85
     86        /**
     87         * This method tests if secondNode is clockwise to first node.
     88         * @param commonNode starting point for both vectors
     89         * @param firstNode first vector end node
     90         * @param secondNode second vector end node
     91         * @return true if first vector is clockwise before second vector.
     92         */
     93
     94        public static boolean angleIsClockwise(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) {
     95                double dy1 = (firstNode.getY() - commonNode.getY());
     96                double dy2 = (secondNode.getY() - commonNode.getY());
     97                double dx1 = (firstNode.getX() - commonNode.getX());
     98                double dx2 = (secondNode.getX() - commonNode.getX());
     99
     100                return dy1 * dx2 - dx1 * dy2 > 0;
     101        }
     102
     103
     104        /**
     105         * Tests if two polygons intersect.
     106         * @param first
     107         * @param second
     108         * @return intersection kind
     109         * TODO: test segments, not only points
     110         * TODO: is O(N*M), should use sweep for better performance.
     111         */
     112        public static PolygonIntersection polygonIntersection(List<Node> first, List<Node> second) {
     113                Set<Node> firstSet = new HashSet<Node>(first);
     114                Set<Node> secondSet = new HashSet<Node>(second);
     115
     116                int nodesInsideSecond = 0;
     117                int nodesOutsideSecond = 0;
     118                int nodesInsideFirst = 0;
     119                int nodesOutsideFirst = 0;
     120
     121                for (Node insideNode : first) {
     122                        if (secondSet.contains(insideNode)) {
     123                                continue;
     124                                //ignore touching nodes.
     125                        }
     126
     127                        if (nodeInsidePolygon(insideNode, second)) {
     128                                nodesInsideSecond ++;
     129                        }
     130                        else {
     131                                nodesOutsideSecond ++;
     132                        }
     133                }
     134
     135                for (Node insideNode : second) {
     136                        if (firstSet.contains(insideNode)) {
     137                                continue;
     138                                //ignore touching nodes.
     139                        }
     140
     141                        if (nodeInsidePolygon(insideNode, first)) {
     142                                nodesInsideFirst ++;
     143                        }
     144                        else {
     145                                nodesOutsideFirst ++;
     146                        }
     147                }
     148
     149                if (nodesInsideFirst == 0) {
     150                        if (nodesInsideSecond == 0){
     151                                if (nodesOutsideFirst + nodesInsideSecond > 0) {
     152                                        return PolygonIntersection.OUTSIDE;
     153                                }
     154                                else {
     155                                        //all nodes common
     156                                        return PolygonIntersection.CROSSING;
     157                                }
     158                        }
     159                        else
     160                        {
     161                                return PolygonIntersection.FIRST_INSIDE_SECOND;
     162                        }
     163                }
     164                else
     165                {
     166                        if (nodesInsideSecond == 0) {
     167                                return PolygonIntersection.SECOND_INSIDE_FIRST;
     168                        }
     169                        else
     170                        {
     171                                return PolygonIntersection.CROSSING;
     172                        }
     173                }
     174        }
     175
     176        /**
     177         * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
     178         * @param polygonNodes list of nodes from polygon path.
     179         * @param point the point to test
     180         * @return true if the point is inside polygon.
     181         */
     182        public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
     183                if (polygonNodes.size() < 2)
     184                        return false;
     185
     186                boolean inside = false;
     187                Node p1, p2;
     188
     189                //iterate each side of the polygon, start with the last segment
     190                Node oldPoint = polygonNodes.get(polygonNodes.size() - 1);
     191
     192                for (Node newPoint : polygonNodes) {
     193                        //skip duplicate points
     194                        if (newPoint.equals(oldPoint)) {
     195                                continue;
     196                        }
     197
     198                        //order points so p1.lat <= p2.lat;
     199                        if (newPoint.getEastNorth().getY() > oldPoint.getEastNorth().getY()) {
     200                                p1 = oldPoint;
     201                                p2 = newPoint;
     202                        } else {
     203                                p1 = newPoint;
     204                                p2 = oldPoint;
     205                        }
     206
     207                        //test if the line is crossed and if so invert the inside flag.
     208                        if ((newPoint.getEastNorth().getY() < point.getEastNorth().getY()) == (point.getEastNorth().getY() <= oldPoint.getEastNorth().getY())
     209                                        && (point.getEastNorth().getX() - p1.getEastNorth().getX()) * (p2.getEastNorth().getY() - p1.getEastNorth().getY())
     210                                        < (p2.getEastNorth().getX() - p1.getEastNorth().getX()) * (point.getEastNorth().getY() - p1.getEastNorth().getY()))
     211                        {
     212                                inside = !inside;
     213                        }
     214
     215                        oldPoint = newPoint;
     216                }
     217
     218                return inside;
     219        }
    189220
    190221

  • applications/editors/josm/plugins/multipoly/src/multipoly/Multipolygon.java

    r23773 r23819  
    1010import java.util.Set;
    1111
    12 import multipoly.GeometryFunctions.Intersection;
     12import multipoly.GeometryFunctions.PolygonIntersection;
    1313
    1414import org.openstreetmap.josm.data.osm.Node;
    … …  
    1616import org.openstreetmap.josm.tools.MultiMap;
    1717
    18 public class Multipolygon {     
    19 
    20         /**
    21          * Represents one polygon that consists of multiple ways. 
     18public class Multipolygon {
     19
     20        /**
     21         * Represents one polygon that consists of multiple ways.
    2222         * @author Viesturs
    2323         *
    2424         */
    2525        public static class JoinedPolygon {
    26         public final List<Way> ways;
    27         public final List<Boolean> reversed;
    28         public final List<Node> nodes;
    29                
    30         public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
    31             this.ways = ways;
    32             this.reversed = reversed;
    33             this.nodes = this.getNodes();
    34         }
    35 
    36         /**
    37         * Creates a polygon form single way.
    38         * @param way
    39         */
    40         public JoinedPolygon(Way way) {
    41             this.ways = Collections.singletonList(way);
    42             this.reversed = Collections.singletonList(Boolean.FALSE);
    43             this.nodes = this.getNodes();
    44         }
    45        
    46        
    47         /**
    48         * Builds a list of nodes for this polygon. First node is not duplicated as last node.
    49         * @return
    50         */
    51         private List<Node> getNodes() {
    52             List<Node> nodes = new ArrayList<Node>();
    53            
    54             for(int waypos = 0; waypos < this.ways.size(); waypos ++) {
    55                 Way way = this.ways.get(waypos);
    56                 boolean reversed = this.reversed.get(waypos).booleanValue();
    57                
    58                 if (!reversed){
    59                     for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
    60                         nodes.add(way.getNode(pos));
    61                     }
    62                 }
    63                 else {
    64                     for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
    65                         nodes.add(way.getNode(pos));
    66                     }
    67                 }
    68             }
    69            
    70             return nodes;
    71         }
    72     }
    73        
    74 
    75     /**
    76     * Helper storage class for finding findOuterWays
    77     * @author viesturs
    78     */
    79     static class PolygonLevel {
    80         public final int level; //nesting level , even for outer, odd for inner polygons.     
    81         public final JoinedPolygon outerWay;
    82        
    83         public List<JoinedPolygon> innerWays;
    84 
    85         public PolygonLevel(JoinedPolygon _pol, int _level) {
    86                 this.outerWay = _pol;
    87             this.level = _level;
    88             this.innerWays = new ArrayList<JoinedPolygon>();
    89         }
    90     }
    91        
    92        
     26                public final List<Way> ways;
     27                public final List<Boolean> reversed;
     28                public final List<Node> nodes;
     29
     30                public JoinedPolygon(List<Way> ways, List<Boolean> reversed) {
     31                        this.ways = ways;
     32                        this.reversed = reversed;
     33                        this.nodes = this.getNodes();
     34                }
     35
     36                /**
     37                * Creates a polygon form single way.
     38                * @param way
     39                */
     40                public JoinedPolygon(Way way) {
     41                        this.ways = Collections.singletonList(way);
     42                        this.reversed = Collections.singletonList(Boolean.FALSE);
     43                        this.nodes = this.getNodes();
     44                }
     45
     46
     47                /**
     48                * Builds a list of nodes for this polygon. First node is not duplicated as last node.
     49                * @return
     50                */
     51                private List<Node> getNodes() {
     52                        List<Node> nodes = new ArrayList<Node>();
     53
     54                        for(int waypos = 0; waypos < this.ways.size(); waypos ++) {
     55                                Way way = this.ways.get(waypos);
     56                                boolean reversed = this.reversed.get(waypos).booleanValue();
     57
     58                                if (!reversed){
     59                                        for (int pos = 0; pos < way.getNodesCount() - 1; pos++) {
     60                                                nodes.add(way.getNode(pos));
     61                                        }
     62                                }
     63                                else {
     64                                        for (int pos = way.getNodesCount() - 1; pos > 0; pos--) {
     65                                                nodes.add(way.getNode(pos));
     66                                        }
     67                                }
     68                        }
     69
     70                        return nodes;
     71                }
     72        }
     73
     74
     75        /**
     76        * Helper storage class for finding findOuterWays
     77        * @author viesturs
     78        */
     79        static class PolygonLevel {
     80                public final int level; //nesting level , even for outer, odd for inner polygons.
     81                public final JoinedPolygon outerWay;
     82
     83                public List<JoinedPolygon> innerWays;
     84
     85                public PolygonLevel(JoinedPolygon _pol, int _level) {
     86                        this.outerWay = _pol;
     87                        this.level = _level;
     88                        this.innerWays = new ArrayList<JoinedPolygon>();
     89                }
     90        }
     91
     92
    9393        public List<JoinedPolygon> outerWays;
    9494        public List<JoinedPolygon> innerWays;
    95                
    96        
     95
     96
    9797        public Multipolygon(List<JoinedPolygon> outerWays, List<JoinedPolygon> innerWays){
    9898                this.outerWays = outerWays;
    9999                this.innerWays = innerWays;
    100100        }
    101        
     101
    102102        public Multipolygon(){
    103103                this.outerWays = new ArrayList<JoinedPolygon>(0);
    104104                this.innerWays = new ArrayList<JoinedPolygon>(0);
    105105        }
    106        
     106
    107107        /**
    108108         * Splits ways into inner and outer JoinedWays. Sets innerWays and outerWays to the result.
    … …  
    111111         */
    112112        public String makeFromWays(Collection<Way> ways){
    113                 List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>(); 
    114                
     113                List<JoinedPolygon> joinedWays = new ArrayList<JoinedPolygon>();
     114
    115115                //collect ways connecting to each node.
    116116                MultiMap<Node, Way> nodesWithConnectedWays = new MultiMap<Node, Way>();
    117117                Set<Way> usedWays = new HashSet<Way>();
    118                
     118
    119119                for(Way w: ways) {
    120120                        if (w.getNodesCount() < 2) {
    121121                                return tr("Cannot add a way with only {0} nodes.", w.getNodesCount());
    122122                        }
    123                        
     123
    124124                        if (w.isClosed()) {
    125125                                //closed way, add as is.
    … …  
    133133                        }
    134134                }
    135                
     135
    136136                //process unclosed ways
    137137                for(Way startWay: ways) {
    … …  
    139139                                continue;
    140140                        }
    141                                        
     141
    142142                        Node startNode = startWay.firstNode();
    143143                        List<Way> collectedWays = new ArrayList<Way>();
    … …  
    145145                        Way curWay = startWay;
    146146                        Node prevNode = startNode;
    147                        
     147
    148148                        //find polygon ways
    149149                        while (true) {
    150                                 boolean curWayReverse = prevNode == curWay.lastNode();                         
    151                                 Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();                                                               
     150                                boolean curWayReverse = prevNode == curWay.lastNode();
     151                                Node nextNode = (curWayReverse) ? curWay.firstNode(): curWay.lastNode();
    152152
    153153                                //add cur way to the list
    154154                                collectedWays.add(curWay);
    155155                                collectedWaysReverse.add(Boolean.valueOf(curWayReverse));
    156                                
     156
    157157                                if (nextNode == startNode) {
    158158                                        //way finished
    159159                                        break;
    160160                                }
    161                                
     161
    162162                                //find next way
    163163                                Collection<Way> adjacentWays = nodesWithConnectedWays.get(nextNode);
    164                                
     164
    165165                                if (adjacentWays.size() != 2) {
    166166                                        return tr("Each node must connect exactly 2 ways");
    167167                                }
    168                                
     168
    169169                                Way nextWay = null;
    170170                                for(Way way: adjacentWays){
    171171                                        if (way != curWay){
    172                                                 nextWay = way;                                         
    173                                         }
    174                                 }
    175                                
     172                                                nextWay = way;
     173                                        }
     174                                }
     175
    176176                                //move to the next way
    177                                 curWay = nextWay;                               
     177                                curWay = nextWay;
    178178                                prevNode = nextNode;
    179179                        }
    180                        
    181                         usedWays.addAll(collectedWays);                 
    182                         joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));                 
    183                 }
    184                                
     180
     181                        usedWays.addAll(collectedWays);
     182                        joinedWays.add(new JoinedPolygon(collectedWays, collectedWaysReverse));
     183                }
     184
    185185                //analyze witch way is inside witch outside.
    186186                return makeFromPolygons(joinedWays);
    … …  
    193193         */
    194194        private String makeFromPolygons(List<JoinedPolygon> polygons) {
    195         List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
    196        
    197         if (list == null){
    198                 return tr("There is an intersection between ways.");
    199         }
     195                List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
     196
     197                if (list == null){
     198                        return tr("There is an intersection between ways.");
     199                }
    200200
    201201                this.outerWays = new ArrayList<JoinedPolygon>(0);
    202202                this.innerWays = new ArrayList<JoinedPolygon>(0);
    203        
    204         //take every other level
    205         for (PolygonLevel pol : list) {
    206             if (pol.level % 2 == 0) {
    207                 this.outerWays.add(pol.outerWay);
    208             }
    209             else {
    210                 this.innerWays.add(pol.outerWay);
    211             }
    212         }
    213 
    214         return null;
    215     }
    216 
    217     /**
    218      * Collects outer way and corresponding inner ways from all boundaries.
    219      * @param boundaryWays
    220      * @return the outermostWay, or null if intersection found.
    221      */
    222     private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
    223 
    224         //TODO: bad performance for deep nesting...
    225         List<PolygonLevel> result = new ArrayList<PolygonLevel>();
    226        
    227         for (JoinedPolygon outerWay : boundaryWays) {
    228 
    229             boolean outerGood = true;
    230             List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>();
    231 
    232             for (JoinedPolygon innerWay : boundaryWays) {
    233                 if (innerWay == outerWay) {
    234                     continue;
    235                 }
    236 
    237                 Intersection innerInside = GeometryFunctions.polygonIntersection(outerWay.nodes, innerWay.nodes);
    238                 Intersection outerInside = GeometryFunctions.polygonIntersection(innerWay.nodes, outerWay.nodes);
    239                
    240                 if (outerInside == Intersection.INSIDE) {
    241                     outerGood = false;  // outer is inside another polygon
    242                     break;
    243                 } else if (innerInside == Intersection.INSIDE) {
    244                     innerCandidates.add(innerWay);
    245                 }
    246                 else if (innerInside == Intersection.CROSSING)
    247                 {
    248                         //ways intersect
    249                         return null;
    250                 }
    251             }
    252 
    253             if (!outerGood) {
    254                 continue;
    255             }
    256 
    257             //add new outer polygon
    258             PolygonLevel pol = new PolygonLevel(outerWay, level);
    259            
    260             //process inner ways
    261             if (innerCandidates.size() > 0) {
    262                 List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
    263                 if (innerList == null) {
    264                         return null; //intersection found
    265                 }
    266                
    267                 result.addAll(innerList);
    268 
    269                 for (PolygonLevel pl : innerList) {
    270                     if (pl.level == level + 1) {
    271                         pol.innerWays.add(pl.outerWay);
    272                     }
    273                 }
    274             }
    275 
    276             result.add(pol);
    277         }
    278 
    279         return result;
    280     }
    281 
    282 
    283        
     203
     204                //take every other level
     205                for (PolygonLevel pol : list) {
     206                        if (pol.level % 2 == 0) {
     207                                this.outerWays.add(pol.outerWay);
     208                        }
     209                        else {
     210                                this.innerWays.add(pol.outerWay);
     211                        }
     212                }
     213
     214                return null;
     215        }
     216
     217        /**
     218         * Collects outer way and corresponding inner ways from all boundaries.
     219         * @param boundaryWays
     220         * @return the outermostWay, or null if intersection found.
     221         */
     222        private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
     223
     224                //TODO: bad performance for deep nesting...
     225                List<PolygonLevel> result = new ArrayList<PolygonLevel>();
     226
     227                for (JoinedPolygon outerWay : boundaryWays) {
     228
     229                        boolean outerGood = true;
     230                        List<JoinedPolygon> innerCandidates = new ArrayList<JoinedPolygon>();
     231
     232                        for (JoinedPolygon innerWay : boundaryWays) {
     233                                if (innerWay == outerWay) {
     234                                        continue;
     235                                }
     236
     237                                PolygonIntersection intersection = GeometryFunctions.polygonIntersection(outerWay.nodes, innerWay.nodes);
     238
     239                                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
     240                                        outerGood = false;  // outer is inside another polygon
     241                                        break;
     242                                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
     243                                        innerCandidates.add(innerWay);
     244                                }
     245                                else if (intersection == PolygonIntersection.CROSSING)
     246                                {
     247                                        //ways intersect
     248                                        return null;
     249                                }
     250                        }
     251
     252                        if (!outerGood) {
     253                                continue;
     254                        }
     255
     256                        //add new outer polygon
     257                        PolygonLevel pol = new PolygonLevel(outerWay, level);
     258
     259                        //process inner ways
     260                        if (innerCandidates.size() > 0) {
     261                                List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
     262                                if (innerList == null) {
     263                                        return null; //intersection found
     264                                }
     265
     266                                result.addAll(innerList);
     267
     268                                for (PolygonLevel pl : innerList) {
     269                                        if (pl.level == level + 1) {
     270                                                pol.innerWays.add(pl.outerWay);
     271                                        }
     272                                }
     273                        }
     274
     275                        result.add(pol);
     276                }
     277
     278                return result;
     279        }
     280
     281
     282
    284283}
Note: See TracChangeset for help on using the changeset viewer.