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