Changeset 6976 in josm


Ignore:
Timestamp:
2014-04-14T21:22:20+02:00 (6 years ago)
Author:
Balaitous
Message:

fix #7959: join areas exception

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java

    r6913 r6976  
    160160            return nodes;
    161161        }
     162
     163        /**
     164         * Inverse inside and outside
     165         */
     166        public void reverse() {
     167            for(WayInPolygon way: ways)
     168                way.insideToTheRight = !way.insideToTheRight;
     169            Collections.reverse(ways);
     170        }
    162171    }
    163172
     
    194203        }
    195204
    196         public boolean hasWays() {
    197             return !availableWays.isEmpty();
    198         }
    199 
    200         public WayInPolygon startNewWay(WayInPolygon way) {
     205        public void removeWay(WayInPolygon way) {
     206            availableWays.remove(way);
     207        }
     208
     209        public void setStartWay(WayInPolygon way) {
    201210            lastWay = way;
    202             lastWayReverse = !lastWay.insideToTheRight;
    203 
    204             return lastWay;
     211            lastWayReverse = !way.insideToTheRight;
    205212        }
    206213
     
    216223        }
    217224
    218 
    219         public  WayInPolygon advanceNextLeftmostWay() {
    220             return advanceNextWay(false);
    221         }
    222 
    223         public  WayInPolygon advanceNextRightmostWay() {
    224             return advanceNextWay(true);
    225         }
    226 
    227         private WayInPolygon advanceNextWay(boolean rightmost) {
    228 
     225        /**
     226         * Get the next way creating a clockwise path, ensure it is the most right way. #7959
     227         * @return The next way.
     228         */
     229        public  WayInPolygon walk() {
    229230            Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
    230231            Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
    231232
     233            double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(),
     234                    headNode.getEastNorth().north() - prevNode.getEastNorth().north());
     235            double bestAngle = 0;
     236
    232237            //find best next way
    233238            WayInPolygon bestWay = null;
    234             Node bestWayNextNode = null;
    235239            boolean bestWayReverse = false;
    236240
    237241            for (WayInPolygon way : availableWays) {
    238                 if (way.way.firstNode().equals(headNode)) {
    239                     //start adjacent to headNode
    240                     Node nextNode = way.way.getNode(1);
    241 
    242                     if (nextNode.equals(prevNode))
    243                     {
    244                         //this is the path we came from - ignore it.
    245                     }
    246                     else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
    247                         //the new way is better
    248                         bestWay = way;
    249                         bestWayReverse = false;
    250                         bestWayNextNode = nextNode;
    251                     }
    252                 }
    253 
    254                 if (way.way.lastNode().equals(headNode)) {
    255                     //end adjacent to headNode
    256                     Node nextNode = way.way.getNode(way.way.getNodesCount() - 2);
    257 
    258                     if (nextNode.equals(prevNode)) {
    259                         //this is the path we came from - ignore it.
    260                     }
    261                     else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
    262                         //the new way is better
    263                         bestWay = way;
    264                         bestWayReverse = true;
    265                         bestWayNextNode = nextNode;
    266                     }
     242                Node nextNode;
     243
     244                // Check for a connected way
     245                if (way.way.firstNode().equals(headNode) && way.insideToTheRight) {
     246                    nextNode = way.way.getNode(1);
     247                } else if (way.way.lastNode().equals(headNode) && !way.insideToTheRight) {
     248                    nextNode = way.way.getNode(way.way.getNodesCount() - 2);
     249                } else {
     250                    continue;
     251                }
     252
     253                if(nextNode == prevNode) {
     254                    // go back
     255                    lastWay = way;
     256                    lastWayReverse = !way.insideToTheRight;
     257                    return lastWay;
     258                }
     259
     260                double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(),
     261                        nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle;
     262                if(angle > Math.PI)
     263                    angle -= 2*Math.PI;
     264                if(angle <= -Math.PI)
     265                    angle += 2*Math.PI;
     266
     267                // Now we have a valid candidate way, is it better than the previous one ?
     268                if (bestWay == null || angle > bestAngle) {
     269                    //the new way is better
     270                    bestWay = way;
     271                    bestWayReverse = !way.insideToTheRight;
     272                    bestAngle = angle;
    267273                }
    268274            }
     
    272278
    273279            return lastWay;
    274         }
    275 
    276         public boolean isLastWayInsideToTheRight() {
    277             return lastWayReverse != lastWay.insideToTheRight;
    278         }
    279 
    280         public Node getLastWayStartNode() {
    281             return lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
    282         }
    283 
    284         public Node getLastWayEndNode() {
    285             return lastWayReverse ? lastWay.way.firstNode() : lastWay.way.lastNode();
    286280        }
    287281    }
     
    318312        LinkedList<Way> ways = new LinkedList<Way>(Main.main.getCurrentDataSet().getSelectedWays());
    319313        addedRelations.clear();
    320        
     314
    321315        if (ways.isEmpty()) {
    322316            new Notification(
     
    381375                }
    382376                commitCommands(tr("Move tags from ways to relations"));
    383                
     377
    384378                List<Way> allWays = new ArrayList<Way>();
    385379                for (Multipolygon pol : result.polygons) {
     
    969963        //first find all discardable ways, by getting outer shells.
    970964        //this will produce incorrect boundaries in some cases, but second pass will fix it.
    971 
    972965        List<WayInPolygon> discardedWays = new ArrayList<WayInPolygon>();
    973         Set<WayInPolygon> processedWays = new HashSet<WayInPolygon>();
    974         WayTraverser traverser = new WayTraverser(multigonWays);
    975 
    976         for (WayInPolygon startWay : multigonWays) {
    977             if (processedWays.contains(startWay)) {
    978                 continue;
    979             }
    980 
    981             traverser.startNewWay(startWay);
    982 
    983             List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
    984             WayInPolygon lastWay = startWay;
    985 
    986             while (true) {
    987                 boundary.add(lastWay);
    988 
    989                 WayInPolygon bestWay = traverser.advanceNextLeftmostWay();
    990                 boolean wayInsideToTheRight = bestWay == null ? false : traverser.isLastWayInsideToTheRight();
    991 
    992                 if (bestWay == null || processedWays.contains(bestWay) || !wayInsideToTheRight) {
    993                     //bad segment chain - proceed to discard it
    994                     lastWay = null;
     966
     967        // In multigonWays collection, some way are just a point (i.e. way like nodeA-nodeA)
     968        // This seems to appear when is apply over invalid way like #9911 test-case
     969        // Remove all of these way to make the next work.
     970        ArrayList<WayInPolygon> cleanMultigonWays = new ArrayList<WayInPolygon>();
     971        for(WayInPolygon way: multigonWays)
     972            if(way.way.getNodesCount() == 2 && way.way.firstNode() == way.way.lastNode())
     973                discardedWays.add(way);
     974            else
     975                cleanMultigonWays.add(way);
     976
     977        WayTraverser traverser = new WayTraverser(cleanMultigonWays);
     978        List<AssembledPolygon> result = new ArrayList<AssembledPolygon>();
     979
     980        WayInPolygon startWay;
     981        while((startWay = traverser.startNewWay()) != null) {
     982            ArrayList<WayInPolygon> path = new ArrayList<WayInPolygon>();
     983            path.add(startWay);
     984            while(true) {
     985                WayInPolygon nextWay = traverser.walk();
     986                if(nextWay == null)
     987                    throw new RuntimeException("Join areas internal error.");
     988                if(path.get(0) == nextWay) {
     989                    AssembledPolygon ring = new AssembledPolygon(path);
     990                    if(ring.getNodes().size() <= 2) {
     991                        // Invalid ring (2 nodes) -> remove
     992                        traverser.removeWays(path);
     993                        for(WayInPolygon way: path)
     994                            discardedResult.add(way.way);
     995                    } else {
     996                        // Close ring -> add
     997                        result.add(ring);
     998                        traverser.removeWays(path);
     999                    }
    9951000                    break;
    996                 } else if (boundary.contains(bestWay)) {
    997                     //traversed way found - close the way
    998                     lastWay = bestWay;
    999                     break;
     1001                }
     1002                if(path.contains(nextWay)) {
     1003                    // Inner loop -> remove
     1004                    int index = path.indexOf(nextWay);
     1005                    while(path.size() > index) {
     1006                        WayInPolygon currentWay = path.get(index);
     1007                        discardedResult.add(currentWay.way);
     1008                        traverser.removeWay(currentWay);
     1009                        path.remove(index);
     1010                    }
     1011                    traverser.setStartWay(path.get(index-1));
    10001012                } else {
    1001                     //proceed to next segment
    1002                     lastWay = bestWay;
    1003                 }
    1004             }
    1005 
    1006             if (lastWay != null) {
    1007                 //way good
    1008                 processedWays.addAll(boundary);
    1009 
    1010                 //remove junk segments at the start
    1011                 while (boundary.get(0) != lastWay) {
    1012                     discardedWays.add(boundary.get(0));
    1013                     boundary.remove(0);
    1014                 }
    1015             } else {
    1016                 //way bad
    1017                 discardedWays.addAll(boundary);
    1018                 processedWays.addAll(boundary);
    1019             }
    1020         }
    1021 
    1022         //now we have removed junk segments, collect the real result ways
    1023 
    1024         traverser.removeWays(discardedWays);
    1025 
    1026         List<AssembledPolygon> result = new ArrayList<AssembledPolygon>();
    1027 
    1028         while (traverser.hasWays()) {
    1029 
    1030             WayInPolygon startWay = traverser.startNewWay();
    1031             List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
    1032             WayInPolygon curWay = startWay;
    1033 
    1034             do {
    1035                 boundary.add(curWay);
    1036                 curWay = traverser.advanceNextRightmostWay();
    1037 
    1038                 //should not happen
    1039                 if (curWay == null || !traverser.isLastWayInsideToTheRight())
    1040                     throw new RuntimeException("Join areas internal error.");
    1041 
    1042             } while (curWay != startWay);
    1043 
    1044             //build result
    1045             traverser.removeWays(boundary);
    1046             result.add(new AssembledPolygon(boundary));
    1047         }
    1048 
    1049         for (WayInPolygon way : discardedWays) {
    1050             discardedResult.add(way.way);
    1051         }
    1052 
    1053         //split inner polygons that have several touching parts.
    1054         result = fixTouchingPolygons(result);
    1055 
    1056         return result;
     1013                    path.add(nextWay);
     1014                }
     1015            }
     1016        }
     1017
     1018        return fixTouchingPolygons(result);
    10571019    }
    10581020
     
    10611023     * @param polygons the polygons to process.
    10621024     */
    1063     public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons)
    1064     {
     1025    public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons) {
    10651026        List<AssembledPolygon> newPolygons = new ArrayList<AssembledPolygon>();
    10661027
    1067         for (AssembledPolygon innerPart : polygons) {
    1068             WayTraverser traverser = new WayTraverser(innerPart.ways);
    1069 
    1070             while (traverser.hasWays()) {
    1071 
    1072                 WayInPolygon startWay = traverser.startNewWay();
    1073                 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
    1074                 WayInPolygon curWay = startWay;
    1075 
    1076                 Node startNode = traverser.getLastWayStartNode();
    1077                 boundary.add(curWay);
    1078 
    1079                 while (startNode != traverser.getLastWayEndNode()) {
    1080                     curWay = traverser.advanceNextLeftmostWay();
    1081                     boundary.add(curWay);
    1082 
    1083                     //should not happen
    1084                     if (curWay == null || !traverser.isLastWayInsideToTheRight())
     1028        for (AssembledPolygon ring : polygons) {
     1029            ring.reverse();
     1030            WayTraverser traverser = new WayTraverser(ring.ways);
     1031            WayInPolygon startWay;
     1032
     1033            while((startWay = traverser.startNewWay()) != null) {
     1034                List<WayInPolygon> simpleRingWays = new ArrayList<WayInPolygon>();
     1035                simpleRingWays.add(startWay);
     1036                WayInPolygon nextWay;
     1037                while((nextWay = traverser.walk()) != startWay) {
     1038                    if(nextWay == null)
    10851039                        throw new RuntimeException("Join areas internal error.");
    1086                 }
    1087 
    1088                 //build result
    1089                 traverser.removeWays(boundary);
    1090                 newPolygons.add(new AssembledPolygon(boundary));
     1040                    simpleRingWays.add(nextWay);
     1041                }
     1042                traverser.removeWays(simpleRingWays);
     1043                AssembledPolygon simpleRing = new AssembledPolygon(simpleRingWays);
     1044                simpleRing.reverse();
     1045                newPolygons.add(simpleRing);
    10911046            }
    10921047        }
Note: See TracChangeset for help on using the changeset viewer.