Changeset 6961 in josm


Ignore:
Timestamp:
2014-04-07T11:46:31+02:00 (5 years ago)
Author:
stoecker
Message:

fix #9081 - patch by Balaitous - improve alignment function in case of intersections

File:
1 edited

Legend:

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

    r6894 r6961  
    1919import org.openstreetmap.josm.command.MoveCommand;
    2020import org.openstreetmap.josm.command.SequenceCommand;
     21import org.openstreetmap.josm.data.coor.EastNorth;
    2122import org.openstreetmap.josm.data.osm.Node;
    2223import org.openstreetmap.josm.data.osm.OsmPrimitive;
     
    3031 * therefore need multiple nodes)
    3132 *
     33 * Case 1: Only ways selected, align each ways taking care of intersection.
     34 * Case 2: Single node selected, align this node relative to the surrounding nodes.
     35 * Case 3: Single node and ways selected, align this node relative to the surrounding nodes only parts of selected ways.
     36 * Case 4: Only nodes selected, align these nodes respect to the line passing through the most distant nodes.
     37 *
    3238 * @author Matthew Newton
    3339 */
     
    4147                Shortcut.registerShortcut("tools:alignline", tr("Tool: {0}", tr("Align Nodes in Line")), KeyEvent.VK_L, Shortcut.DIRECT), true);
    4248        putValue("help", ht("/Action/AlignInLine"));
     49    }
     50
     51    /**
     52     * InvalidSelection exception has to be raised when action can't be perform
     53     */
     54    private class InvalidSelection extends Exception {
     55
     56        /**
     57         * Create an InvalidSelection exception with default message
     58         */
     59        public InvalidSelection() {
     60            super(tr("Please select at least three nodes."));
     61        }
     62
     63        /**
     64         * Create an InvalidSelection exception with specific message
     65         * @param msg Message that will be display to the user
     66         */
     67        public InvalidSelection(String msg) {
     68            super(msg);
     69        }
    4370    }
    4471
     
    5380        if(resultOut.length < 2)
    5481            throw new IllegalArgumentException();
    55        
     82
    5683        Node nodea = null;
    5784        Node nodeb = null;
     
    100127    }
    101128
    102     private void showWarning() {
    103         showWarning(tr("Please select at least three nodes."));
    104     }
    105 
    106     private void showWarning(String msg) {
    107         new Notification(msg)
    108             .setIcon(JOptionPane.INFORMATION_MESSAGE)
    109             .show();
    110     }
    111 
    112     private static int indexWrap(int size, int i) {
    113         i = i % size; // -2 % 5 = -2, -7 % 5 = -2, -5 % 5 = 0
    114         if (i < 0) {
    115             i = size + i;
    116         }
    117         return i;
    118     }
    119     // get the node in w at index i relative to refI
    120     private static Node getNodeRelative(Way w, int refI, int i) {
    121         int absI = indexWrap(w.getNodesCount(), refI + i);
    122         if(w.isClosed() && refI + i < 0) {
    123             absI--;  // node duplicated in closed ways
    124         }
    125         return w.getNode(absI);
    126     }
    127 
    128     /**
    129      * The general algorithm here is to find the two selected nodes
    130      * that are furthest apart, and then to align all other selected
    131      * nodes onto the straight line between these nodes.
    132      */
    133 
    134 
    135129    /**
    136130     * Operation depends on the selected objects:
     
    141135            return;
    142136
     137        List<Node> selectedNodes = new ArrayList<Node>(getCurrentDataSet().getSelectedNodes());
     138        List<Way> selectedWays = new ArrayList<Way>(getCurrentDataSet().getSelectedWays());
     139
     140        try {
     141            Command cmd = null;
     142            //// Decide what to align based on selection:
     143
     144            /// Only ways selected -> For each way align their nodes taking care of intersection
     145            if(selectedNodes.isEmpty() && !selectedWays.isEmpty()) {
     146                cmd = alignMultiWay(selectedWays);
     147            }
     148            /// Only 1 node selected -> align this node relative to referers way
     149            else if(selectedNodes.size() == 1) {
     150                Node selectedNode = selectedNodes.get(0);
     151                List<Way> involvedWays = null;
     152                if(selectedWays.isEmpty())
     153                    /// No selected way, all way containing this node are used
     154                    involvedWays = OsmPrimitive.getFilteredList(selectedNode.getReferrers(), Way.class);
     155                else
     156                    /// Selected way, use only these ways
     157                    involvedWays = selectedWays;
     158                List<Line> lines = getInvolvedLines(selectedNode, involvedWays);
     159                if(lines.size() > 2 || lines.isEmpty())
     160                    throw new InvalidSelection();
     161                cmd = alignSingleNode(selectedNodes.get(0), lines);
     162            }
     163            /// More than 3 nodes selected -> align those nodes
     164            else if(selectedNodes.size() >= 3) {
     165                cmd = alignOnlyNodes(selectedNodes);
     166            }
     167            /// All others cases are invalid
     168            else {
     169                throw new InvalidSelection();
     170            }
     171
     172            // Do it!
     173            Main.main.undoRedo.add(cmd);
     174            Main.map.repaint();
     175
     176        } catch (InvalidSelection except) {
     177            new Notification(except.getMessage())
     178                .setIcon(JOptionPane.INFORMATION_MESSAGE)
     179                .show();
     180        }
     181    }
     182
     183    /**
     184     * Align nodes in case that only nodes are selected
     185     *
     186     * The general algorithm here is to find the two selected nodes
     187     * that are furthest apart, and then to align all other selected
     188     * nodes onto the straight line between these nodes.
     189
     190     * @param nodes Nodes to be aligned
     191     * @return Command that perform action
     192     * @throws InvalidSelection
     193     */
     194    private Command alignOnlyNodes(List<Node> nodes) throws InvalidSelection {
    143195        Node[] anchors = new Node[2]; // oh, java I love you so much..
    144 
    145         List<Node> selectedNodes = new ArrayList<Node>(getCurrentDataSet().getSelectedNodes());
    146         Collection<Way> selectedWays = getCurrentDataSet().getSelectedWays();
    147         List<Node> nodes = new ArrayList<Node>();
    148 
    149         //// Decide what to align based on selection:
    150 
    151         /// Only ways selected -> For each way align their nodes taking care of intersection
    152         if(selectedNodes.isEmpty() && !selectedWays.isEmpty()) {
    153             alignMultiWay(selectedWays);
    154             return;
    155         }
    156         /// More than 3 nodes selected -> align those nodes
    157         else if(selectedNodes.size() >= 3) {
    158             nodes.addAll(selectedNodes);
    159             // use the nodes furthest apart as anchors
    160             nodePairFurthestApart(nodes, anchors);
    161         }
    162         /// One node selected -> align that node to the relevant neighbors
    163         else if (selectedNodes.size() == 1) {
    164             Node n = selectedNodes.iterator().next();
    165 
    166             Way w = null;
    167             if(selectedWays.size() == 1) {
    168                 w = selectedWays.iterator().next();
    169                 if (!w.containsNode(n))
    170                     // warning
    171                     return;
    172             } else {
    173                 List<Way> refWays = OsmPrimitive.getFilteredList(n.getReferrers(), Way.class);
    174                 if (refWays.size() == 1) { // node used in only one way
    175                     w = refWays.iterator().next();
    176                 }
    177             }
    178             if (w == null || w.getNodesCount() < 3)
    179                 // warning, need at least 3 nodes
    180                 return;
    181 
    182             // Find anchors
    183             int nodeI = w.getNodes().indexOf(n);
    184             // End-node in non-circular way selected: align this node with the two neighbors.
    185             if ((nodeI == 0 || nodeI == w.getNodesCount()-1) && !w.isClosed()) {
    186                 int direction = nodeI == 0 ? 1 : -1;
    187                 anchors[0] = w.getNode(nodeI + direction);
    188                 anchors[1] = w.getNode(nodeI + direction*2);
    189             } else {
    190                 // o---O---o
    191                 anchors[0] = getNodeRelative(w, nodeI, 1);
    192                 anchors[1] = getNodeRelative(w, nodeI, -1);
    193             }
    194             nodes.add(n);
    195         }
    196 
    197         if (anchors[0] == null || anchors[1] == null) {
    198             showWarning();
    199             return;
    200         }
    201 
    202 
     196        // use the nodes furthest apart as anchors
     197        nodePairFurthestApart(nodes, anchors);
    203198        Collection<Command> cmds = new ArrayList<Command>(nodes.size());
    204 
    205         createAlignNodesCommands(anchors, nodes, cmds);
    206 
    207         // Do it!
    208         Main.main.undoRedo.add(new SequenceCommand(tr("Align Nodes in Line"), cmds));
    209         Main.map.repaint();
    210     }
    211 
    212     private void createAlignNodesCommands(Node[] anchors, Collection<Node> nodes, Collection<Command> cmds) {
    213         Node nodea = anchors[0];
    214         Node nodeb = anchors[1];
    215 
    216         // The anchors are aligned per definition
    217         nodes.remove(nodea);
    218         nodes.remove(nodeb);
    219 
    220         // Find out co-ords of A and B
    221         double ax = nodea.getEastNorth().east();
    222         double ay = nodea.getEastNorth().north();
    223         double bx = nodeb.getEastNorth().east();
    224         double by = nodeb.getEastNorth().north();
    225 
    226         // OK, for each node to move, work out where to move it!
    227         for (Node n : nodes) {
    228             // Get existing co-ords of node to move
    229             double nx = n.getEastNorth().east();
    230             double ny = n.getEastNorth().north();
    231 
    232             if (ax == bx) {
    233                 // Special case if AB is vertical...
    234                 nx = ax;
    235             } else if (ay == by) {
    236                 // ...or horizontal
    237                 ny = ay;
    238             } else {
    239                 // Otherwise calculate position by solving y=mx+c
    240                 double m1 = (by - ay) / (bx - ax);
    241                 double c1 = ay - (ax * m1);
    242                 double m2 = (-1) / m1;
    243                 double c2 = n.getEastNorth().north() - (n.getEastNorth().east() * m2);
    244 
    245                 nx = (c2 - c1) / (m1 - m2);
    246                 ny = (m1 * nx) + c1;
    247             }
    248             double newX = nx - n.getEastNorth().east();
    249             double newY = ny - n.getEastNorth().north();
    250             // Add the command to move the node to its new position.
    251             cmds.add(new MoveCommand(n, newX, newY));
    252         }
     199        Line line = new Line(anchors[0], anchors[1]);
     200        for(Node node: nodes)
     201            if(node != anchors[0] && node != anchors[1])
     202                cmds.add(line.projectionCommand(node));
     203        return new SequenceCommand(tr("Align Nodes in Line"), cmds);
    253204    }
    254205
     
    256207     * Align way in case of multiple way #6819
    257208     * @param ways Collection of way to align
    258      */
    259     private void alignMultiWay(Collection<Way> ways) {
     209     * @return Command that perform action
     210     * @throws InvalidSelection
     211     */
     212    private Command alignMultiWay(Collection<Way> ways) throws InvalidSelection {
    260213        // Collect all nodes and compute line equation
    261214        HashSet<Node> nodes = new HashSet<Node>();
    262215        HashMap<Way, Line> lines = new HashMap<Way, Line>();
    263216        for(Way w: ways) {
    264             if(w.firstNode() == w.lastNode()) {
    265                 showWarning(tr("Can not align a polygon. Abort."));
    266                 return;
    267             }
     217            if(w.firstNode() == w.lastNode())
     218                throw new InvalidSelection(tr("Can not align a polygon. Abort."));
    268219            nodes.addAll(w.getNodes());
    269220            lines.put(w, new Line(w));
     
    283234            else if(referers.size() == 2) {
    284235                Command cmd = lines.get(referers.get(0)).intersectionCommand(n, lines.get(referers.get(1)));
    285                 if(cmd == null) {
    286                     showWarning(tr("Two parallels ways found. Abort."));
    287                     return;
    288                 }
    289236                cmds.add(cmd);
    290237            }
    291             else {
    292                 showWarning(tr("Intersection of three or more ways can not be solved. Abort."));
    293                 return;
    294             }
    295         }
    296         Main.main.undoRedo.add(new SequenceCommand(tr("Align Nodes in Line"), cmds));
    297         Main.map.repaint();
    298     }
    299 
    300     /**
    301      * Class that describe a line
     238            else
     239                throw new InvalidSelection(tr("Intersection of three or more ways can not be solved. Abort."));
     240        }
     241        return new SequenceCommand(tr("Align Nodes in Line"), cmds);
     242    }
     243
     244    /**
     245     * Get lines useful to do alignment of a single node
     246     * @param node Node to be aligned
     247     * @param refWays Ways where useful lines will be searched
     248     * @return List of useful lines
     249     * @throws InvalidSelection
     250     */
     251    private List<Line> getInvolvedLines(Node node, List<Way> refWays) throws InvalidSelection {
     252        ArrayList<Line> lines = new ArrayList<Line>();
     253        ArrayList<Node> neighbors = new ArrayList<Node>();
     254        for(Way way: refWays) {
     255            List<Node> nodes = way.getNodes();
     256            neighbors.clear();
     257            for(int i = 1; i < nodes.size()-1; i++)
     258                if(nodes.get(i) == node) {
     259                    System.out.printf("Find 2 neighbors\n");
     260                    neighbors.add(nodes.get(i-1));
     261                    neighbors.add(nodes.get(i+1));
     262                    //lines.add(new Line(nodes.get(i-1), nodes.get(i+1)));
     263                }
     264            if(neighbors.size() == 0)
     265                continue;
     266            else if(neighbors.size() == 2)
     267                // Non self crossing
     268                lines.add(new Line(neighbors.get(0), neighbors.get(1)));
     269            else if(neighbors.size() == 4) {
     270                // Self crossing, have to make 2 lines with 4 neighbors
     271                // see #9081 comment 6
     272                EastNorth c = node.getEastNorth();
     273                double[] angle = new double[4];
     274                for(int i = 0; i < 4; i++) {
     275                    EastNorth p = neighbors.get(i).getEastNorth();
     276                    angle[i] = Math.atan2(p.north() - c.north(), p.east() - c.east());
     277                }
     278                double[] deltaAngle = new double[3];
     279                for(int i = 0; i < 3; i++) {
     280                    deltaAngle[i] = angle[i+1] - angle[0];
     281                    if(deltaAngle[i] < 0)
     282                        deltaAngle[i] += 2*Math.PI;
     283                }
     284                int nb = 0;
     285                if(deltaAngle[1] < deltaAngle[0]) nb++;
     286                if(deltaAngle[2] < deltaAngle[0]) nb++;
     287                if(nb == 1) {
     288                    // Align along [neighbors[0], neighbors[1]] and [neighbors[0], neighbors[2]]
     289                    lines.add(new Line(neighbors.get(0), neighbors.get(1)));
     290                    lines.add(new Line(neighbors.get(2), neighbors.get(3)));
     291                } else {
     292                    // Align along [neighbors[0], neighbors[2]] and [neighbors[1], neighbors[3]]
     293                    lines.add(new Line(neighbors.get(0), neighbors.get(2)));
     294                    lines.add(new Line(neighbors.get(1), neighbors.get(3)));
     295                }
     296            } else
     297                throw new InvalidSelection();
     298        }
     299        return lines;
     300    }
     301
     302    /**
     303     * Align a single node relative to a set of lines #9081
     304     * @param node Node to be aligned
     305     * @param lines Lines to align node on
     306     * @return Command that perform action
     307     * @throws InvalidSelection
     308     */
     309    private Command alignSingleNode(Node node, List<Line> lines) throws InvalidSelection {
     310        if(lines.size() == 1)
     311            return lines.get(0).projectionCommand(node);
     312        else if(lines.size() == 2)
     313            return lines.get(0).intersectionCommand(node,  lines.get(1));
     314        throw new InvalidSelection();
     315    }
     316
     317    /**
     318     * Class that represent a line
    302319     */
    303320    private class Line {
     
    307324         * Such as a^2 + b^2 = 1, ie (-b, a) is a unit vector of line
    308325         */
    309         private double a, b, c; // Line equation ax+by+c=0
    310         /**
    311          * (xM, yM) are coordinate of a point of the line
    312          */
    313         private double xM, yM; // Coordinate of a point of the line
    314 
    315         /**
    316          * Init a line equation from a way.
    317          * @param way
    318          */
    319         public Line(Way way) {
    320             xM = way.firstNode().getEastNorth().getX();
    321             yM = way.firstNode().getEastNorth().getY();
    322             double xB = way.lastNode().getEastNorth().getX();
    323             double yB = way.lastNode().getEastNorth().getY();
     326        private double a, b, c;
     327        /**
     328         * (xM, yM) are coordinates of a point of the line
     329         */
     330        private double xM, yM;
     331
     332        /**
     333         * Init a line by 2 nodes.
     334         * @param first On point of the line
     335         * @param last Other point of the line
     336         * @throws InvalidSelection
     337         */
     338        public Line(Node first, Node last) throws InvalidSelection {
     339            xM = first.getEastNorth().getX();
     340            yM = first.getEastNorth().getY();
     341            double xB = last.getEastNorth().getX();
     342            double yB = last.getEastNorth().getY();
    324343            a = yB - yM;
    325344            b = xM - xB;
    326345            double norm = Math.sqrt(a*a + b*b);
    327             if (norm == 0) {
    328                 norm = 1;
    329             }
     346            if (norm == 0)
     347                // Nodes have same coordinates !
     348                throw new InvalidSelection();
    330349            a /= norm;
    331350            b /= norm;
     
    334353
    335354        /**
     355         * Init a line equation from a way.
     356         * @param way Use extremity of this way to compute line equation
     357         * @throws InvalidSelection
     358         */
     359        public Line(Way way) throws InvalidSelection {
     360            this(way.firstNode(), way.lastNode());
     361        }
     362
     363        /**
    336364         * Orthogonal projection of a node N along this line.
    337365         * @param n Node to be projected
     
    347375         * @param n Node to move to the intersection
    348376         * @param other Second line for intersection
    349          * @return The command that move the node or null if line are parallels
    350          */
    351         public Command intersectionCommand(Node n, Line other) {
     377         * @return The command that move the node
     378         * @throws InvalidSelection
     379         */
     380        public Command intersectionCommand(Node n, Line other) throws InvalidSelection {
    352381            double d = this.a * other.b - other.a * this.b;
    353             if(d == 0) return null;
     382            if(Math.abs(d) < 10e-6)
     383                // parallels lines
     384                throw new InvalidSelection(tr("Two parallels ways found. Abort."));
    354385            double x = (this.b * other.c - other.b * this.c) / d;
    355386            double y = (other.a * this.c - this.a * other.c) / d;
Note: See TracChangeset for help on using the changeset viewer.