Ignore:
Timestamp:
2009-11-09T17:02:00+01:00 (14 years ago)
Author:
bastiK
Message:

relation editor: respect roundabouts when sorting the relation

Location:
trunk/src/org/openstreetmap/josm/gui/dialogs/relation
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java

    • Property svn:eol-style set to native
    r2394 r2421  
     1// License: GPL. For details, see LICENSE file.
    12package org.openstreetmap.josm.gui.dialogs.relation;
    23
    … …  
    569570    }
    570571
     572    /**
     573     * Sort the relation members by the way they are linked.
     574     */
    571575    void sort() {
    572576        RelationNodeMap map = new RelationNodeMap(members);
    573         Vector<LinkedList<Integer>> segments;
    574         LinkedList<Integer> segment;
    575         Node startSearchNode;
    576         Node endSearchNode;
    577         boolean something_done;
    578 
    579         /*
    580          * sort any 2 or more connected elements together may be slow with many unconnected members
    581          */
    582 
    583         if (map.isEmpty())
    584             // empty relation or incomplete members
    585             return;
    586         segments = new Vector<LinkedList<Integer>>();
    587 
    588         while (!map.isEmpty()) {
    589             // find an element for the next segment
    590             // try first element in relation if we just started
    591             // otherwise, or if first element is another relation, just fetch some element from the
    592             // map
    593             Integer next;
    594             if ((segments.size() == 0) && map.remove(0, members.get(0))) {
    595                 next = 0;
    596             } else {
    597                 next = map.pop();
    598                 if (next == null) {
    599                     break;
    600                 }
    601             }
    602 
    603             segment = new LinkedList<Integer>();
    604             segment.add(next);
    605             segments.add(segment);
    606 
    607             do {
    608                 something_done = false;
    609                 startSearchNode = null;
    610                 endSearchNode = null;
    611                 if (segment.size() == 1) {
    612                     // only one element in segment, so try to link against each linkable node of element
    613                     RelationMember m = members.get(segment.getFirst());
    614                     if (m.isWay()) {
    615                         Way w = m.getWay();
    616                         endSearchNode = w.lastNode();
    617                         if (w.lastNode() != w.firstNode())
    618                         {
    619                             startSearchNode = w.firstNode();
    620                         }
    621                     } else if (m.isNode()) {
    622                         Node n = m.getNode();
    623                         endSearchNode = n;
    624                     }
    625                 } else {
    626                     // add unused node of first element and unused node of last element
    627                     // start with the first element (compared to next element)
    628                     startSearchNode = getUnusedNode(members.get(segment.getFirst()), members.get(segment.get(1)));
    629 
    630                     // now the same for the last element (compared to previous element)
    631                     endSearchNode = getUnusedNode(members.get(segment.getLast()), members.get(segment.get(segment.size() - 2)));
    632                 }
    633 
    634                 // let's see if we can find connected elements for endSearchNode and startSearchNode
    635                 if (startSearchNode != null) {
    636                     Integer m2 = map.find(startSearchNode, segment.getFirst());
    637                     if (m2 != null) {
    638                         segment.add(0, m2);
    639                         map.remove(m2, members.get(m2));
    640                         something_done = true;
    641                     }
    642                 }
    643                 if (endSearchNode != null) {
    644                     Integer m2 = map.find(endSearchNode, segment.getLast());
    645                     if (m2 != null) {
    646                         segment.add(segment.size(), m2);
    647                         map.remove(m2, members.get(m2));
    648                         something_done = true;
    649                     }
    650                 }
    651             } while (something_done);
    652 
    653         }
    654 
    655         if (segments.size() > 0) {
    656             // append map.remaining() to segments list (as a single segment)
    657             segment = new LinkedList<Integer>();
    658             segment.addAll(map.getRemaining());
    659             segments.add(segment);
    660 
    661             // now we need to actually re-order the relation members
    662             ArrayList<RelationMember> newmembers = new ArrayList<RelationMember>();
    663             for (LinkedList<Integer> segment2 : segments) {
    664                 for (Integer p : segment2) {
    665                     newmembers.add(members.get(p));
    666                 }
    667             }
    668             members.clear();
    669             members.addAll(newmembers);
    670 
    671             fireTableDataChanged();
    672         }
     577
     578        // List of groups of linked members
     579        //
     580        ArrayList<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>();
     581
     582        // current group of members that are linked among each other
     583        // Two successive members are always linked i.e. have a common node.
     584        //
     585        LinkedList<Integer> group;
     586
     587        Integer first;
     588        while ((first = map.pop()) != null) {
     589            group = new LinkedList<Integer>();
     590            group.add(first);
     591
     592            allGroups.add(group);
     593
     594            Integer next = first;
     595            while ((next = map.popAdjacent(next)) != null) {
     596                group.addLast(next);
     597            }
     598
     599            // The first element need not be in front of the list.
     600            // So the search goes in both directions
     601            //
     602            next = first;
     603            while ((next = map.popAdjacent(next)) != null) {
     604                group.addFirst(next);
     605            }
     606
     607        }
     608
     609        group = new LinkedList<Integer>();
     610        group.addAll(map.getNotSortableMembers());
     611        allGroups.add(group);
     612
     613        ArrayList<RelationMember> newMembers = new ArrayList<RelationMember>();
     614        for (LinkedList<Integer> tmpGroup : allGroups) {
     615            for (Integer p : tmpGroup) {
     616                newMembers.add(members.get(p));
     617            }
     618        }
     619
     620        if (members.size() != newMembers.size()) throw new AssertionError();
     621       
     622        members.clear();
     623        members.addAll(newMembers);
     624        fireTableDataChanged();
    673625    }
    674626
    … …  
    679631     *
    680632     * If both ways are not linked in any way, NONE is returned.
    681      * 
     633     *
    682634     * Else the direction is given as follows:
    683635     * Let the relation be a route of oneway streets, and someone travels them in the given order.
    … …  
    711663        /** the list of nodes the way k can dock to */
    712664        List<Node> refNodes= new ArrayList<Node>();
    713        
     665
    714666        switch (ref_direction) {
    715             case FORWARD: 
     667            case FORWARD:
    716668                refNodes.add(way_ref.lastNode());
    717669                break;
    … …  
    728680            return NONE;
    729681        }
    730        
     682
    731683        for (Node n : refNodes) {
    732684            if (n == null) continue;
    … …  
    752704     * determine, if the way i is a roundabout and if yes, what type of roundabout
    753705     */
    754     private Direction roundaboutType(int i) {
     706    private Direction roundaboutType(int i) { //FIXME
    755707        RelationMember m = members.get(i);
    756708        if (m == null || !m.isWay()) return NONE;
    757709        Way w = m.getWay();
    758         if (w != null &&       
    759                 "roundabout".equals(w.get("junction")) &&
     710        return roundaboutType(w);
     711    }
     712    static Direction roundaboutType(Way w) {
     713        if (w != null &&
     714                "roundabout".equals(w.get("junction")) &&
    760715                w.getNodesCount() < 200 &&
    761716                w.getNodesCount() > 2 &&
    762                 w.getNode(0) != null && 
     717                w.getNode(0) != null &&
    763718                w.getNode(1) != null &&
    764719                w.getNode(2) != null &&
    … …  
    775730            return NONE;
    776731    }
    777    
     732
    778733    private WayConnectionType wayConnection(int i) {
    779734        if (connectionType == null) {

  • trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java

    • Property svn:eol-style set to native
    r2365 r2421  
     1// License: GPL. For details, see LICENSE file.
    12package org.openstreetmap.josm.gui.dialogs.relation;
    23
    34import java.util.ArrayList;
     5import java.util.Iterator;
     6import java.util.List;
     7import java.util.Map;
     8import java.util.TreeMap;
    49import java.util.TreeSet;
    510
    … …  
    813import org.openstreetmap.josm.data.osm.Way;
    914
     15import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.*;
     16
    1017/**
    11  * A mapping from Node positions to elements in a Relation (currently Nodes and Ways only)
     18 * Auxiliary class for relation sorting.
     19 *
     20 * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that
     21 * maps each node to all ways that have this node.
     22 * After construction both maps are consistent, but later on objects that are no longer needed
     23 * are removed from the value sets.
     24 * However the corresponding keys are not deleted even if they map to an empty set.
     25 * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more
     26 * (that are shared by other members).
    1227 *
    1328 * @author Christiaan Welvaart <cjw@time4t.net>
    14  *
     29 * 
    1530 */
    1631public class RelationNodeMap {
     32    /*
     33     * read only list of all relation members
     34     */
     35    private final List<RelationMember> members;
     36    /*
     37     * the maps. (Need TreeMap for efficiency.)
     38     */
     39    private TreeMap<Node, TreeSet<Integer>> nodesMap;
     40    private TreeMap<Integer, TreeSet<Node>> waysMap;
     41    /*
     42     * Used to keep track of what members are done.
     43     */
     44    private TreeSet<Integer> remaining;
     45
    1746    /**
    18      * For each way endpoint, list all ways that share this node
     47     * All members that are incomplete or not a way
    1948     */
    20     private java.util.HashMap<Node, TreeSet<Integer>> points;
    21     /**
    22      * Singleton nodes
    23      */
    24     private java.util.HashMap<Node, Integer> nodes;
    25     private java.util.Vector<Integer> remaining;
    26     /**
    27      * read only list
    28      */
    29     private final ArrayList<RelationMember> members;
     49    private List<Integer> notSortable = new ArrayList<Integer>();
    3050
    3151    RelationNodeMap(ArrayList<RelationMember> members) {
    32         int i;
     52        this.members = members;
    3353
    34         this.members = members;
    35         points = new java.util.HashMap<Node, TreeSet<Integer>>();
    36         nodes = new java.util.HashMap<Node, Integer>();
    37         remaining = new java.util.Vector<Integer>();
     54        nodesMap = new TreeMap<Node, TreeSet<Integer>>();
     55        waysMap = new TreeMap<Integer, TreeSet<Node>>();
    3856
    39         for (i = 0; i < members.size(); ++i) {
     57        for (int i = 0; i < members.size(); ++i) {
    4058            RelationMember m = members.get(i);
    41             if (m.getMember().incomplete)
     59            if (m.getMember().incomplete || !m.isWay())
    4260            {
    43                 remaining.add(Integer.valueOf(i));
     61                notSortable.add(i);
    4462            }
    45             else
    46             {
    47                 add(i, m);
    48             }
    49         }
    50     }
    51 
    52     Integer find(Node node, int current) {
    53         Integer result = null;
    54 
    55         try {
    56             result = nodes.get(node);
    57             if (result == null) {
    58                 result = points.get(node).first();
    59                 if (members.get(current).getMember() == members.get(result).getMember()) {
    60                     result = points.get(node).last();
    61                 }
    62             }
    63         } catch (NullPointerException f) {
    64         } catch (java.util.NoSuchElementException e) {
    65         }
    66 
    67         return result;
    68     }
    69 
    70     void add(int n, RelationMember m) {
    71         if (m.isWay()) {
    72             Way w = m.getWay();
    73             if (w.lastNode() == w.firstNode())
    74             {
    75                 nodes.put(w.firstNode(), n);
    76             }
    77             else
    78             {
    79                 if (!points.containsKey(w.firstNode())) {
    80                     points.put(w.firstNode(), new TreeSet<Integer>());
    81                 }
    82                 points.get(w.firstNode()).add(n);
    83 
    84                 if (!points.containsKey(w.lastNode())) {
    85                     points.put(w.lastNode(), new TreeSet<Integer>());
    86                 }
    87                 points.get(w.lastNode()).add(n);
    88             }
    89         } else if (m.isNode()) {
    90             Node node = m.getNode();
    91             nodes.put(node, n);
    92         } else {
    93             remaining.add(n);
    94         }
    95     }
    96 
    97     boolean remove(int n, RelationMember a) {
    98         boolean result;
    99         if (a.isWay()) {
    100             Way w = a.getWay();
    101             if (w.firstNode() == w.lastNode())
    102             {
    103                 result = (nodes.remove(w.firstNode()) != null);
    104             }
    105             else
    106             {
    107                 result = points.get(w.firstNode()).remove(n);
    108                 result &= points.get(w.lastNode()).remove(n);
    109             }
    110         } else {
    111             result = (nodes.remove(a.getMember()) != null);
    112         }
    113         return result;
    114     }
    115 
    116     // no node-mapped entries left
    117     boolean isEmpty() {
    118         return points.isEmpty() && nodes.isEmpty();
    119     }
    120 
    121     java.util.Vector<Integer> getRemaining() {
    122         return remaining;
    123     }
    124 
    125     Integer pop() {
    126         Node node = null;
    127         Integer result = null;
    128 
    129         if (!nodes.isEmpty()) {
    130             node = nodes.keySet().iterator().next();
    131             result = nodes.get(node);
    132             nodes.remove(node);
    133         } else if (!points.isEmpty()) {
    134             for (TreeSet<Integer> set : points.values()) {
    135                 if (!set.isEmpty()) {
    136                     result = set.first();
    137                     Way w = members.get(result).getWay();
    138                     points.get(w.firstNode()).remove(result);
    139                     points.get(w.lastNode()).remove(result);
    140                     break;
     63            else {
     64                Way w = m.getWay();
     65                if (MemberTableModel.roundaboutType(w) != NONE) {
     66                    for (Node nd : w.getNodes()) {
     67                        addPair(nd, i);
     68                    }
     69                } else {
     70                    addPair(w.firstNode(), i);
     71                    addPair(w.lastNode(), i);
    14172                }
    14273            }
    14374        }
    14475
    145         return result;
     76        remaining = new TreeSet<Integer>();
     77        for (Integer k : waysMap.keySet()) {
     78            remaining.add(k);
     79        }
     80
     81        /*
     82         * Clean up the maps, i.e. remove nodes from roundabouts and dead ends that
     83         * cannot be used in future. (only for performance)
     84         */
     85        Iterator<Map.Entry<Node,TreeSet<Integer>>> it = nodesMap.entrySet().iterator();
     86        while (it.hasNext()) {
     87            Map.Entry<Node,TreeSet<Integer>> nodeLinks = it.next();
     88
     89            if (nodeLinks.getValue().size() < 2) {
     90//                System.err.println("DELETE: "+nodeLinks.getKey()+" "+nodeLinks.getValue());
     91                if (nodeLinks.getValue().size() != 1) throw new AssertionError();
     92
     93                Integer d_way = nodeLinks.getValue().iterator().next();
     94                TreeSet<Node> d_way_nodes = waysMap.get(d_way);
     95                d_way_nodes.remove(nodeLinks.getKey());
     96
     97                it.remove();
     98                continue;
     99            }
     100//            System.err.println(nodeLinks.getKey()+" "+nodeLinks.getValue());
     101
     102        }
     103//        System.err.println("");
     104//        System.err.println(remaining);
     105//        System.err.println("");
     106//        System.err.println(nodesMap);
     107//        System.err.println("");
     108//        System.err.println(waysMap);
     109
     110    }
     111
     112    private void addPair(Node n, int i) {
     113        TreeSet<Integer> ts = nodesMap.get(n);
     114        if (ts == null) {
     115            ts = new TreeSet<Integer>();
     116            nodesMap.put(n, ts);
     117        }
     118        ts.add(i);
     119
     120        TreeSet<Node> ts2 = waysMap.get(i);
     121        if (ts2 == null) {
     122            ts2 = new TreeSet<Node>();
     123            waysMap.put(i, ts2);
     124        }
     125        ts2.add(n);
     126    }
     127
     128    /**
     129     * Return a relation member that is linked to the
     130     * member 'i', but has not been popped jet.
     131     * Return null if there is no such member left.
     132     */
     133    public Integer popAdjacent(Integer i) {
     134//        System.err.print("Adjacent["+i+"]:");
     135        TreeSet<Node> nodes = waysMap.get(i);
     136//        System.err.print(nodes);
     137        for (Node n : nodes) {
     138//            System.err.print(" {"+n.getId()+"} ");
     139            TreeSet<Integer> adj = nodesMap.get(n);
     140            if (!adj.isEmpty()) {
     141                Integer j = adj.iterator().next();
     142                done(j);
     143                waysMap.get(j).remove(n);
     144//                System.err.println(j);
     145                return j;
     146            }
     147        }
     148        return null;
     149    }
     150
     151    /**
     152     * Returns some remaining member or null if
     153     * every sortable member has been processed.
     154     */
     155    public Integer pop() {
     156        if (remaining.isEmpty()) return null;
     157        Integer i = remaining.iterator().next();
     158        done(i);
     159        return i;
     160    }
     161
     162    /**
     163     * This relation member has been processed.
     164     * Remove references in the nodesMap.
     165     */
     166    private void done(Integer i) {
     167        remaining.remove(i);
     168        TreeSet<Node> nodes = waysMap.get(i);
     169        for (Node n : nodes) {
     170            boolean result = nodesMap.get(n).remove(i);
     171            if (!result) throw new AssertionError();
     172        }
     173    }
     174
     175    public List<Integer> getNotSortableMembers() {
     176        return notSortable;
    146177    }
    147178}
Note: See TracChangeset for help on using the changeset viewer.