Changeset 2210 in josm


Ignore:
Timestamp:
2009-09-29T06:56:50+02:00 (12 years ago)
Author:
Gubaer
Message:

fixed #3608: Combining ways with many nodes takes very long to process
fixed #3609: StackOverflowError while combining large ways

File:
1 edited

Legend:

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

    r2202 r2210  
    88import java.util.ArrayList;
    99import java.util.Collection;
     10import java.util.Collections;
    1011import java.util.HashMap;
    1112import java.util.HashSet;
     
    509510        private Set<NodePair> edges;
    510511        private int numUndirectedEges = 0;
    511 
    512         protected void computeNumEdges() {
     512        private HashMap<Node, List<NodePair>> successors;
     513        private HashMap<Node, List<NodePair>> predecessors;
     514
     515
     516        protected void rememberSuccessor(NodePair pair) {
     517            if (successors.containsKey(pair.getA())) {
     518                if (!successors.get(pair.getA()).contains(pair)) {
     519                    successors.get(pair.getA()).add(pair);
     520                }
     521            } else {
     522                ArrayList<NodePair> l = new ArrayList<NodePair>();
     523                l.add(pair);
     524                successors.put(pair.getA(), l);
     525            }
     526        }
     527
     528        protected void rememberPredecessors(NodePair pair) {
     529            if (predecessors.containsKey(pair.getB())) {
     530                if (!predecessors.get(pair.getB()).contains(pair)) {
     531                    predecessors.get(pair.getB()).add(pair);
     532                }
     533            } else {
     534                ArrayList<NodePair> l = new ArrayList<NodePair>();
     535                l.add(pair);
     536                predecessors.put(pair.getB(), l);
     537            }
     538        }
     539
     540        protected boolean isTerminalNode(Node n) {
     541            if (successors.get(n) == null) return false;
     542            if (successors.get(n).size() != 1) return false;
     543            if (predecessors.get(n) == null) return true;
     544            if (predecessors.get(n).size() == 1) {
     545                NodePair p1 = successors.get(n).iterator().next();
     546                NodePair p2 = predecessors.get(n).iterator().next();
     547                return p1.equals(p2.swap());
     548            }
     549            return false;
     550        }
     551
     552        protected void prepare() {
    513553            Set<NodePair> undirectedEdges = new HashSet<NodePair>();
     554            successors = new HashMap<Node, List<NodePair>>();
     555            predecessors = new HashMap<Node, List<NodePair>>();
     556
    514557            for (NodePair pair: edges) {
    515558                if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
    516559                    undirectedEdges.add(pair);
    517560                }
     561                rememberSuccessor(pair);
     562                rememberPredecessors(pair);
    518563            }
    519564            numUndirectedEges = undirectedEdges.size();
     
    537582
    538583        protected Node getStartNode() {
    539             return edges.iterator().next().getA();
     584            Set<Node> nodes = getNodes();
     585            for (Node n: nodes) {
     586                if (successors.get(n) != null && successors.get(n).size() ==1)
     587                    return n;
     588            }
     589            return null;
     590        }
     591
     592        protected Set<Node> getTerminalNodes() {
     593            Set<Node> ret = new HashSet<Node>();
     594            for (Node n: getNodes()) {
     595                if (isTerminalNode(n)) {
     596                    ret.add(n);
     597                }
     598            }
     599            return ret;
    540600        }
    541601
     
    550610
    551611        protected List<NodePair> getOutboundPairs(NodePair pair) {
    552             LinkedList<NodePair> outbound = new LinkedList<NodePair>();
    553             for (NodePair candidate:edges) {
    554                 if (candidate.equals(pair)) {
    555                     continue;
    556                 }
    557                 if (candidate.isSuccessorOf(pair)) {
    558                     outbound.add(candidate);
    559                 }
    560             }
    561             return outbound;
     612            return getOutboundPairs(pair.getB());
    562613        }
    563614
    564615        protected List<NodePair> getOutboundPairs(Node node) {
    565             LinkedList<NodePair> outbound = new LinkedList<NodePair>();
    566             for (NodePair candidate:edges) {
    567                 if (candidate.getA() == node) {
    568                     outbound.add(candidate);
    569                 }
    570             }
    571             return outbound;
     616            List<NodePair> l = successors.get(node);
     617            return l == null ? Collections.EMPTY_LIST : l;
    572618        }
    573619
     
    585631        }
    586632
    587 
    588         protected boolean advance(Stack<NodePair> path) {
    589             // found a spanning path ?
    590             //
    591             if (isSpanningWay(path))
    592                 return true;
    593 
    594             // advance with one of the possible follow up nodes
    595             //
    596             Stack<NodePair> nextPairs = new Stack<NodePair>();
    597             nextPairs.addAll(getOutboundPairs(path.peek()));
    598             while(!nextPairs.isEmpty()) {
    599                 NodePair next = nextPairs.pop();
    600                 if (path.contains(next) || path.contains(next.swap())) {
    601                     continue;
    602                 }
    603                 path.push(next);
    604                 if (advance(path)) return true;
    605                 path.pop();
    606             }
    607             return false;
    608         }
    609 
    610633        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
    611634            LinkedList<Node> ret = new LinkedList<Node>();
     
    617640        }
    618641
     642        /**
     643         * Tries to find a spanning path starting from node <code>startNode</code>.
     644         *
     645         * Traverses the path in depth-first order.
     646         *
     647         * @param startNode the start node
     648         * @return the spanning path; null, if no path is found
     649         */
    619650        protected List<Node> buildSpanningPath(Node startNode) {
    620651            if (startNode == null)
    621652                return null;
    622653            Stack<NodePair> path = new Stack<NodePair>();
    623             // advance with one of the possible follow up nodes
    624             //
    625654            Stack<NodePair> nextPairs  = new Stack<NodePair>();
    626655            nextPairs.addAll(getOutboundPairs(startNode));
    627656            while(!nextPairs.isEmpty()) {
    628                 path.push(nextPairs.pop());
    629                 if (advance(path))
    630                     return buildPathFromNodePairs(path);
    631                 path.pop();
     657                NodePair cur= nextPairs.pop();
     658                if (! path.contains(cur) && ! path.contains(cur.swap())) {
     659                    while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
     660                        path.pop();
     661                    }
     662                    path.push(cur);
     663                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
     664                    nextPairs.addAll(getOutboundPairs(path.peek()));
     665                }
    632666            }
    633667            return null;
    634668        }
    635669
     670        /**
     671         * Tries to find a path through the graph which visits each edge (i.e.
     672         * the segment of a way) exactly one.
     673         *
     674         * @return the path; null, if no path was found
     675         */
    636676        public List<Node> buildSpanningPath() {
    637             computeNumEdges();
    638             for (Node n : getNodes()) {
     677            prepare();
     678            // try to find a path from each "terminal node", i.e. from a
     679            // node which is connected by exactly one undirected edges (or
     680            // two directed edges in opposite direction) to the graph. A
     681            // graph built up from way segments is likely to include such
     682            // nodes, unless all ways are closed.
     683            // In the worst case this loops over all nodes which is
     684            // very slow for large ways.
     685            //
     686            Set<Node> nodes = getTerminalNodes();
     687            nodes = nodes.isEmpty() ? getNodes() : nodes;
     688            for (Node n: nodes) {
    639689                List<Node> path = buildSpanningPath(n);
    640690                if (path != null)
Note: See TracChangeset for help on using the changeset viewer.