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 }