I just realized that the last patch didn't include tests for the ray casting code. Please find the updated patch attached. Cheers, Ben Ben Konrath wrote:
Hi,
A patch that will create a POI in various areas if they don't already have one is attached. This is very useful for me here in Costa Rica where most streets aren't named and addresses are given based on points of references like buildings, parks, etc rather than street names.
This replaces Bernhard Heibler's patch from last week which does a similar thing for only buildings. As with Bernhard's patch, if you want a POI in a given area, you have to make sure that the style system will create a Garmin polygon by putting a suitable line in resources/styles/default/polygons.
POIs are only made for areas which I thought made sense. Here is the code that describes the current mappings from Garmin polygon to Garmin point:
+ map.put(0x04, 0x640b); // Military + map.put(0x05, 0x2f0b); // Car Park + map.put(0x06, 0x2f0b); // Parking Garage + map.put(0x07, 0x2f04); // Airport + map.put(0x08, 0x2e04); // Shopping Centre + map.put(0x09, 0x2f09); // Marina + map.put(0x0a, 0x6410); // University + map.put(0x0b, 0x6408); // Hospital + map.put(0x13, 0x6400); // Man made area + map.put(0x17, 0x2c06); // City Park + map.put(0x18, 0x2d05); // Golf + map.put(0x19, 0x2c0a); // Sport + map.put(0x1a, 0x6403); // Cemetery
Please let me know if you think something is missing or wrong here.
The patch adds a new command line argument '--add-pois-to-areas' which enables this feature. The only thing left to do is calculate a better position for the POIs - currently they are placed in the centre of the polygon but that doesn't work for cases like 'Museo Nacional de Costa Rica' as shown here:
http://openstreetmap.org/?lat=9.932949&lon=-84.071649&zoom=18&layers=B000FTF
Comments and testing are appreciated.
Cheers, Ben
diff --git a/resources/help/en/options b/resources/help/en/options index 1f556d8..ad0bae1 100644 --- a/resources/help/en/options +++ b/resources/help/en/options @@ -117,6 +117,11 @@ Misc options: Generate a POI for each named road. By default, the POIs' Garmin type code is 0x640a. If desired, a different type code can be specified with this option. + +--add-pois-to-areas + Generate a POI for each area. The POIs are created after the style + is applied and only for polygon types that have a reasonable point + equivalent. --tdbfile Write a .tdb file. diff --git a/src/uk/me/parabola/mkgmap/general/MapShape.java b/src/uk/me/parabola/mkgmap/general/MapShape.java index 9811ff7..6496d8d 100644 --- a/src/uk/me/parabola/mkgmap/general/MapShape.java +++ b/src/uk/me/parabola/mkgmap/general/MapShape.java @@ -15,6 +15,11 @@ */ package uk.me.parabola.mkgmap.general; +import java.util.ArrayList; +import java.util.List; + +import uk.me.parabola.imgfmt.app.Coord; + /** * A shape or polygon is just the same as a line really as far as I can tell. * There are some things that you cannot do with them semantically. @@ -38,5 +43,148 @@ public class MapShape extends MapLine {// So top code can link objects from here throw new IllegalArgumentException( "can't set a direction on a polygon"); } + + /** + * Checks if a point is contained within this shape. Points on the + * edge of the shape are considered inside. + * + * @param co point to check + * @return true if point is in shape, false otherwise + */ + public boolean contains(Coord co) { + return contains(this.getPoints(), co, true); + } + + /* + * Checks if a point is contained within a shape. + * + * @param points points that define the shape + * @param target point to check + * @param onLineIsInside if a point on the line should be considered inside the shape + * @return true if point is contained within the shape, false if the target point is outside the shape + */ + private static boolean contains(List<Coord> points, Coord target, boolean onLineIsInside) { + // implementation of the Ray casting algorithm as described here: + // http://en.wikipedia.org/wiki/Point_in_polygon + // with inspiration from: + // http://www.visibone.com/inpoly/ + boolean inside = false; + if (points.size() < 3) + return false; + + // complete the shape if we're dealing with a MapShape that is not closed + Coord start = points.get(0); + Coord end = points.get(points.size() - 1); + if (!start.equals(end)) { + // make copy of the shape's geometry + List<Coord> pointsTemp = new ArrayList<Coord>(points.size() + 1); + for (Coord coord : points) { + pointsTemp.add(new Coord(coord.getLatitude(), coord.getLongitude())); + } + pointsTemp.add(new Coord(start.getLatitude(), start.getLongitude())); + points = pointsTemp; + } + + int xtarget = target.getLatitude(); + int ytarget = target.getLongitude(); + + for (int i = 0; i < points.size() - 1; i++) { + + // apply transformation points to change target point to (0,0) + int x0 = points.get(i).getLatitude() - xtarget; + int y0 = points.get(i).getLongitude() - ytarget; + int x1 = points.get(i+1).getLatitude() - xtarget; + int y1 = points.get(i+1).getLongitude() - ytarget; + + // ensure that x0 is smaller than x1 so that we can just check to see if the line intersects the y axis easily + if (x0 > x1) { + int xtemp = x0; + int ytemp = y0; + x0 = x1; + y0 = y1; + x1 = xtemp; + y1 = ytemp; + } + // use (0,0) as target because points already transformed + if (isPointOnLine(x0, y0, x1, y1, 0, 0)) + return onLineIsInside; + + // explanation of if statement + // + // (x0 < 0 && x1 >= 0): + // are the x values between the y axis? only include points from the right + // with this check so that corners aren't counted twice + // + // (y0 * (x1 - x0) > (y1 - y0) * x0): + // from y = mx + b: + // => b = y0 ((y1 - y0) / (x1 - x0)) * x0 + // for intersection, b > 0 + // from y = mx + b, b = y - mx + // => y - mx > 0 + // => y0 - ((y1 - y0) / (x1 - x0)) * x0 > 0 + // => y0 > ((y1 - y0) / (x1 - x0)) * x0 + // from 'if (x0 > x1)', x1 >= x0 + // => x1 - x0 >=0 + // => y0 * (x1 - x0) > (y1 - y0) * x0 + if ((x0 < 0 && x1 >= 0) && (y0 * (x1 - x0)) > ((y1 - y0) * x0)) + inside = !inside; + } + + return inside; + } + + /* + * Checks if a point is on a line. + * + * @param x0 x value of first point in line + * @param y0 y value of first point in line + * @param x1 x value of second point in line + * @param y1 y value of second point in line + * @param xt x value of target point + * @param yt y value of target point + * @return return true if point is on the line, false if the point isn't on the line + */ + private static boolean isPointOnLine(int x0, int y0, int x1, int y1, int xt, int yt) { + // this implementation avoids using doubles + // apply transformation points to change target point to (0,0) + x0 = x0 - xt; + y0 = y0 - yt; + x1 = x1 - xt; + y1 = y1 - yt; + + // ensure that x0 is smaller than x1 so that we can just check to see if the line intersects the y axis easily + if (x0 > x1) { + int xtemp = x0; + int ytemp = y0; + x0 = x1; + y0 = y1; + x1 = xtemp; + y1 = ytemp; + } + + // if a point is on the edge of shape (on a line), it's considered outside the shape + // special case if line is on y-axis + if (x0 == 0 && x1 == 0) { + // ensure that y0 is smaller than y1 so that we can just check if the line intersects the x axis + if (y0 > y1) { + int xtemp = x0; + int ytemp = y0; + x0 = x1; + y0 = y1; + x1 = xtemp; + y1 = ytemp; + } + // test to see if we have a vertical line touches x-axis + if (y0 <= 0 && y1 >= 0) + return true; + // checks if point is on the line, see comments in contain() for derivation of similar + // formula - left as an exercise to the reader ;) + } else if ((x0 <= 0 && x1 >= 0) && (y0 * (x1 - x0)) == ((y1 - y0) * x0)) { + return true; + } + return false; + } + + } diff --git a/src/uk/me/parabola/mkgmap/main/MapMaker.java b/src/uk/me/parabola/mkgmap/main/MapMaker.java index b93b4bc..548d068 100644 --- a/src/uk/me/parabola/mkgmap/main/MapMaker.java +++ b/src/uk/me/parabola/mkgmap/main/MapMaker.java @@ -36,6 +36,7 @@ import uk.me.parabola.mkgmap.build.MapBuilder; import uk.me.parabola.mkgmap.general.LoadableMapDataSource; import uk.me.parabola.mkgmap.general.MapLine; import uk.me.parabola.mkgmap.general.MapPoint; +import uk.me.parabola.mkgmap.general.MapShape; import uk.me.parabola.mkgmap.reader.plugin.MapReader; /** @@ -50,6 +51,7 @@ public class MapMaker implements MapProcessor { try { LoadableMapDataSource src = loadFromFile(args, filename); makeRoadNamePOIS(args, src); + makeAreaPOIs(args, src); return makeMap(args, src); } catch (FormatException e) { System.err.println("Bad file format: " + filename); @@ -135,6 +137,58 @@ public class MapMaker implements MapProcessor { return src; } + private void makeAreaPOIs(CommandArgs args, LoadableMapDataSource src) { + String s = args.getProperties().getProperty("add-pois-to-areas"); + if (s != null) { + // please update the initialCapacity argument if you a new conversion + HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(13, 1.0f); + // create map of known garmin polygon -> garmin point conversions + map.put(0x04, 0x640b); // Military + map.put(0x05, 0x2f0b); // Car Park + map.put(0x06, 0x2f0b); // Parking Garage + map.put(0x07, 0x2f04); // Airport + map.put(0x08, 0x2e04); // Shopping Centre + map.put(0x09, 0x2f09); // Marina + map.put(0x0a, 0x6410); // University + map.put(0x0b, 0x6408); // Hospital + map.put(0x13, 0x6400); // Man made area + map.put(0x17, 0x2c06); // City Park + map.put(0x18, 0x2d05); // Golf + map.put(0x19, 0x2c0a); // Sport + map.put(0x1a, 0x6403); // Cemetery + + for (MapShape shape : src.getShapes()) { + String shapeName = shape.getName(); + int shapeType = shape.getType(); + + // only make a point if the shape has a name and we know what type of point to make + if (shapeName == null || !map.containsKey(shapeType)) + continue; + + // go through all points to make sure there is no name or location collision + boolean addPOI = true; + for (MapPoint point : src.getPoints()) { + if (shapeName.equals(point.getName()) && shape.contains(point.getLocation())) { + addPOI = false; + break; + } + } + + // finally add the point + if (addPOI) { + MapPoint newPoint = new MapPoint(); + newPoint.setName(shapeName); + newPoint.setType(map.get(shapeType)); + newPoint.setLocation(shape.getLocation()); // TODO use centriod + src.getPoints().add(newPoint); + log.info("created POI ", shapeName, "from shape"); + } + } + } + + } + + void makeRoadNamePOIS(CommandArgs args, LoadableMapDataSource src) { String rnp = args.getProperties().getProperty("road-name-pois", null); // are road name POIS wanted? diff --git a/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java b/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java new file mode 100644 index 0000000..251d4ce --- /dev/null +++ b/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java @@ -0,0 +1,289 @@ +/** + * + */ +package uk.me.parabola.mkgmap.general; + + +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.List; + +import org.junit.Before; +import org.junit.Test; + +import uk.me.parabola.imgfmt.app.Coord; + +/** + * @author ben + * + */ +public class PointInShapeTest { + + MapShape square, triangle, line; + int squareSize = 4; + + /** + * @throws java.lang.Exception + */ + @Before + public void setUp() throws Exception { + // Square + List<Coord> points = Arrays.asList( + new Coord(0, 0), + new Coord(0, squareSize), + new Coord(squareSize, squareSize), + new Coord(squareSize, 0), + new Coord(0,0) + ); + square = new MapShape(); + square.setPoints(points); + + // Triangle + points = Arrays.asList( + new Coord(0,0), + new Coord(4,4), + new Coord(8,0), + new Coord(0,0) + ); + triangle = new MapShape(); + triangle.setPoints(points); + + // Line + points = Arrays.asList( + new Coord(2,5), + new Coord(12,1) + ); + line = new MapShape(); + line.setPoints(points); + } + + @Test + public void testLinePointsInsideSquare() { + + // inside square, 1 unit from corners + List<Coord> points = Arrays.asList( + new Coord(1, squareSize/2), + new Coord(squareSize/2, squareSize - 1), + new Coord(squareSize - 1, squareSize/2), + new Coord(squareSize/2, 1) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be inside square", + square.contains(coord)); + } + + // on the line + points = Arrays.asList( + new Coord(0, squareSize/2), + new Coord(squareSize/2, squareSize), + new Coord(squareSize, squareSize/2), + new Coord(squareSize/2, 0) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside square", + square.contains(coord)); + } + } + + @Test + public void testLinePointsOutsideSquare() { + + // outside square, 1 unit from line + List<Coord> points = Arrays.asList( + new Coord(-1, squareSize/2), + new Coord(squareSize/2, squareSize + 1), + new Coord(squareSize + 1, squareSize/2), + new Coord(squareSize/2, -1) + ); + for (Coord coord : points) { + assertFalse("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside square", + square.contains(coord)); + } + } + + @Test + public void testCornerPointsInsideSquare() { + // corner points + for (Coord cornerpoint : square.getPoints()) { + Coord co = new Coord(cornerpoint.getLatitude(), cornerpoint.getLongitude()); + assertTrue("corner point (" + co.getLatitude() + ", " + co.getLongitude() + ") should be outside square", + square.contains(co)); + } + + // sub shape + for (Coord cornerpoint : square.getPoints()) { + int xadd = cornerpoint.getLatitude() > 0 ? -1 : 1; + int yadd = cornerpoint.getLongitude() > 0 ? -1 : 1; + int x = cornerpoint.getLatitude() + xadd; + int y = cornerpoint.getLongitude() + yadd; + Coord co = new Coord(x, y); + assertTrue("point (" + x + ", " + y + ") should be inside square", square.contains(co)); + } + + // tests above / below corner points, on the outside edge + for (Coord cornerpoint : square.getPoints()) { + int xadd = cornerpoint.getLatitude() > 0 ? -1 : 1; + int x = cornerpoint.getLatitude() + xadd; + int y = cornerpoint.getLongitude(); + Coord co = new Coord(x, y); + assertTrue("point (" + x + ", " + y + ") should be outside square", square.contains(co)); + } + + // tests to the right / left side of corner points, on square edge + for (Coord cornerpoint : square.getPoints()) { + int yadd = cornerpoint.getLongitude() > 0 ? -1 : 1; + int x = cornerpoint.getLatitude(); + int y = cornerpoint.getLongitude() + yadd; + Coord co = new Coord(x, y); + assertTrue("point (" + x + ", " + y + ") should be outside square", square.contains(co)); + } + } + + @Test + public void testCornerPointsOutsideSquare() { + + // tests above / below corner points, outside squate + for (Coord cornerpoint : square.getPoints()) { + int yadd = cornerpoint.getLongitude() > 0 ? 1 : -1; + int x = cornerpoint.getLatitude(); + int y = cornerpoint.getLongitude() + yadd; + Coord co = new Coord(x, y); + assertFalse("point (" + x + ", " + y + ") should be outside square", square.contains(co)); + } + + // tests to the right / left side of corner points, outside square + for (Coord cornerpoint : square.getPoints()) { + int xadd = cornerpoint.getLatitude() > 0 ? 1 : -1; + int x = cornerpoint.getLatitude() + xadd; + int y = cornerpoint.getLongitude(); + Coord co = new Coord(x, y); + assertFalse("point (" + x + ", " + y + ") should be outside square", square.contains(co)); + } + + // super shape + for (Coord cornerpoint : square.getPoints()) { + int xadd = cornerpoint.getLatitude() > 0 ? 1 : -1; + int yadd = cornerpoint.getLongitude() > 0 ? 1 : -1; + int x = cornerpoint.getLatitude() + xadd; + int y = cornerpoint.getLongitude() + yadd; + Coord co = new Coord(x, y); + assertFalse("point (" + x + ", " + y + ") should be outside square", square.contains(co)); + } + } + + + @Test + public void testLinePointsInsideTriangle() { + // inside triangle, above / below lines + List<Coord> points = Arrays.asList( + new Coord(2,1), + new Coord(6,1), + new Coord(4,1) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be inside triangle", + triangle.contains(coord)); + } + + // on lines + points = Arrays.asList( + new Coord(2,2), + new Coord(6,2), + new Coord(4,0) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside triangle", + triangle.contains(coord)); + } + } + + @Test + public void testLinePointsOutsideTriangle() { + // outside triangle, above / below lines + List<Coord> points = Arrays.asList( + new Coord(2,3), + new Coord(6,3), + new Coord(4,-1) + ); + for (Coord coord : points) { + assertFalse("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside triangle", + triangle.contains(coord)); + } + } + + @Test + public void testCornerPointsInsideTriangle() { + // corner points + for (Coord cornerpoint : triangle.getPoints()) { + assertTrue("point (" + cornerpoint.getLatitude() + ", " + cornerpoint.getLongitude() + ") should be outside triangle", + triangle.contains(cornerpoint)); + } + + // sub shape + List<Coord> points = Arrays.asList( + new Coord(2,1), + new Coord(4,3), + new Coord(6,1) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be inside triangle", + triangle.contains(coord)); + } + + // beside points, on edge + points = Arrays.asList( + new Coord(1,0), + new Coord(7,0) + ); + for (Coord coord : points) { + assertTrue("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside triangle", + triangle.contains(coord)); + } + } + + @Test + public void testCornerPointsOutsideTriangle() { + // above points + for (Coord coord : triangle.getPoints()) { + Coord co = new Coord(coord.getLatitude(), coord.getLongitude() + 1); + assertFalse("point (" + co.getLatitude() + ", " + co.getLongitude() + ") should be outside triangle", + triangle.contains(co)); + } + + // outside triangle, beside / below lines + List<Coord> points = Arrays.asList( + new Coord(-1,0), + new Coord(0,-1), + new Coord(3,4), + new Coord(5,4), + new Coord(9,0), + new Coord(8,-1) + ); + for (Coord coord : points) { + assertFalse("point (" + coord.getLatitude() + ", " + coord.getLongitude() + ") should be outside triangle", + triangle.contains(coord)); + } + + // super shape + for (Coord cornerpoint : triangle.getPoints()) { + int xadd = cornerpoint.getLatitude() > 0 ? 1 : -1; + int yadd = cornerpoint.getLongitude() > 0 ? 1 : -1; + int x = cornerpoint.getLatitude() + xadd; + int y = cornerpoint.getLongitude() + yadd; + Coord co = new Coord(x, y); + assertFalse("point (" + x + ", " + y + ") should be outside triangle", triangle.contains(co)); + } + + } + + @Test + public void testLine() { + // midpoint + Coord co = new Coord(7,3); + assertFalse("point (" + co.getLatitude() + ", " + co.getLongitude() + ") should be outside line", + line.contains(co)); + + } +}