001    // License: GPL. See LICENSE file for details.
002    package org.openstreetmap.josm.data.validation.util;
003    
004    import java.awt.geom.Point2D;
005    import java.util.ArrayList;
006    import java.util.Collections;
007    import java.util.HashSet;
008    import java.util.List;
009    import java.util.Map;
010    import java.util.Set;
011    
012    import org.openstreetmap.josm.data.osm.Node;
013    import org.openstreetmap.josm.data.osm.Way;
014    import org.openstreetmap.josm.data.validation.OsmValidator;
015    
016    /**
017     * Utility class
018     *
019     * @author frsantos
020     */
021    public class ValUtil
022    {
023        /**
024         * Returns the start and end cells of a way.
025         * @param w The way
026         * @param cellWays The map with all cells
027         * @return A list with all the cells the way starts or ends
028         */
029        public static List<List<Way>> getWaysInCell(Way w, Map<Point2D,List<Way>> cellWays) {
030            if (w.getNodesCount() == 0)
031                return Collections.emptyList();
032    
033            Node n1 = w.getNode(0);
034            Node n2 = w.getNode(w.getNodesCount() - 1);
035    
036            List<List<Way>> cells = new ArrayList<List<Way>>(2);
037            Set<Point2D> cellNodes = new HashSet<Point2D>();
038            Point2D cell;
039    
040            // First, round coordinates
041            long x0 = Math.round(n1.getEastNorth().east()  * OsmValidator.griddetail);
042            long y0 = Math.round(n1.getEastNorth().north() * OsmValidator.griddetail);
043            long x1 = Math.round(n2.getEastNorth().east()  * OsmValidator.griddetail);
044            long y1 = Math.round(n2.getEastNorth().north() * OsmValidator.griddetail);
045    
046            // Start of the way
047            cell = new Point2D.Double(x0, y0);
048            cellNodes.add(cell);
049            List<Way> ways = cellWays.get(cell);
050            if (ways == null) {
051                ways = new ArrayList<Way>();
052                cellWays.put(cell, ways);
053            }
054            cells.add(ways);
055    
056            // End of the way
057            cell = new Point2D.Double(x1, y1);
058            if (!cellNodes.contains(cell)) {
059                cellNodes.add(cell);
060                ways = cellWays.get( cell );
061                if (ways == null) {
062                    ways = new ArrayList<Way>();
063                    cellWays.put(cell, ways);
064                }
065                cells.add(ways);
066            }
067    
068            // Then floor coordinates, in case the way is in the border of the cell.
069            x0 = (long) Math.floor(n1.getEastNorth().east()  * OsmValidator.griddetail);
070            y0 = (long) Math.floor(n1.getEastNorth().north() * OsmValidator.griddetail);
071            x1 = (long) Math.floor(n2.getEastNorth().east()  * OsmValidator.griddetail);
072            y1 = (long) Math.floor(n2.getEastNorth().north() * OsmValidator.griddetail);
073    
074            // Start of the way
075            cell = new Point2D.Double(x0, y0);
076            if (!cellNodes.contains(cell)) {
077                cellNodes.add(cell);
078                ways = cellWays.get(cell);
079                if (ways == null) {
080                    ways = new ArrayList<Way>();
081                    cellWays.put(cell, ways);
082                }
083                cells.add(ways);
084            }
085    
086            // End of the way
087            cell = new Point2D.Double(x1, y1);
088            if (!cellNodes.contains(cell)) {
089                cellNodes.add(cell);
090                ways = cellWays.get(cell);
091                if (ways == null) {
092                    ways = new ArrayList<Way>();
093                    cellWays.put(cell, ways);
094                }
095                cells.add(ways);
096            }
097            return cells;
098        }
099    
100        /**
101         * Returns the coordinates of all cells in a grid that a line between 2
102         * nodes intersects with.
103         *
104         * @param n1 The first node.
105         * @param n2 The second node.
106         * @param gridDetail The detail of the grid. Bigger values give smaller
107         * cells, but a bigger number of them.
108         * @return A list with the coordinates of all cells
109         */
110        public static List<Point2D> getSegmentCells(Node n1, Node n2, double gridDetail) {
111            List<Point2D> cells = new ArrayList<Point2D>();
112            double x0 = n1.getEastNorth().east() * gridDetail;
113            double x1 = n2.getEastNorth().east() * gridDetail;
114            double y0 = n1.getEastNorth().north() * gridDetail + 1;
115            double y1 = n2.getEastNorth().north() * gridDetail + 1;
116    
117            if (x0 > x1) {
118                // Move to 1st-4th cuadrants
119                double aux;
120                aux = x0; x0 = x1; x1 = aux;
121                aux = y0; y0 = y1; y1 = aux;
122            }
123    
124            double dx  = x1 - x0;
125            double dy  = y1 - y0;
126            long stepY = y0 <= y1 ? 1 : -1;
127            long gridX0 = (long) Math.floor(x0);
128            long gridX1 = (long) Math.floor(x1);
129            long gridY0 = (long) Math.floor(y0);
130            long gridY1 = (long) Math.floor(y1);
131    
132            long maxSteps = (gridX1 - gridX0) + Math.abs(gridY1 - gridY0) + 1;
133            while ((gridX0 <= gridX1 && (gridY0 - gridY1)*stepY <= 0) && maxSteps-- > 0) {
134                cells.add( new Point2D.Double(gridX0, gridY0));
135    
136                // Is the cross between the segment and next vertical line nearer than the cross with next horizontal line?
137                // Note: segment line formula: y=dy/dx(x-x1)+y1
138                // Note: if dy < 0, must use *bottom* line. If dy > 0, must use upper line
139                double scanY = dy/dx * (gridX0 + 1 - x1) + y1 + (dy < 0 ? -1 : 0);
140                double scanX = dx/dy * (gridY0 + (dy < 0 ? 0 : 1)*stepY - y1) + x1;
141    
142                double distX = Math.pow(gridX0 + 1 - x0, 2) + Math.pow(scanY - y0, 2);
143                double distY = Math.pow(scanX - x0, 2) + Math.pow(gridY0 + stepY - y0, 2);
144    
145                if (distX < distY) {
146                    gridX0 += 1;
147                } else {
148                    gridY0 += stepY;
149                }
150            }
151            return cells;
152        }
153    }