Hi
I've made a few changes and fixes to the point in polygon code. Here are
the changes included in the attached patch:
* Add copyright statements
* Correctly assign lat and long to x and y values in
MapShape.contains(List<Coord>, Coord, boolean) - This doesn't change
the results since the values were used consistently but it's still
nice to have it correct.
* Clarify comments in MapShape.contains(List<Coord>, Coord, boolean)
* Fix comment in
MapMaker.makeAreaPOIs(CommandArgs, LoadableMapDataSource)
* Add unit test for unclosed shape to ensure all code is exercised.
Thanks, Ben
diff --git a/src/uk/me/parabola/mkgmap/general/MapShape.java
b/src/uk/me/parabola/mkgmap/general/MapShape.java
index 8845db3..02f1918 100644
--- a/src/uk/me/parabola/mkgmap/general/MapShape.java
+++ b/src/uk/me/parabola/mkgmap/general/MapShape.java
@@ -1,5 +1,6 @@
/**
* Copyright (C) 2006 Steve Ratcliffe
+ * Copyright (C) 2009 Ben Konrath <b...@bagu.org> - point in shape code
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
@@ -96,17 +97,16 @@ public class MapShape extends MapLine {// So top code can
link objects from here
pointsTemp.add(new Coord(start.getLatitude(),
start.getLongitude()));
points = pointsTemp;
}
-
- int xtarget = target.getLatitude();
- int ytarget = target.getLongitude();
+ int xtarget = target.getLongitude();
+ int ytarget = target.getLatitude();
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;
+ int x0 = points.get(i).getLongitude() - xtarget;
+ int y0 = points.get(i).getLatitude() - ytarget;
+ int x1 = points.get(i+1).getLongitude() - xtarget;
+ int y1 = points.get(i+1).getLatitude() - 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) {
@@ -118,27 +118,33 @@ public class MapShape extends MapLine {// So top code can
link objects from here
y1 = ytemp;
}
- // use (0,0) as target because points already
transformed
+ // use (0,0) as the target point because the edge
points are 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
+ // (x0 < 0 && x1 >= 0)
+ // ~~~~~~~~~~~~~~~~~~~
+ //
+ // We transformed the polygon edge points to make the
target point (0,0) and
+ // we know that x1 >= x0 from 'if (x0 > x1)' above,
therefore we only need
+ // to check if the x values are between the y-axis. We
only include points
+ // from the right (x0 < 0 as opposed to x0 <= 0) with
this check so that
+ // corners aren't counted twice and the count will be
odd for this case.
//
- // (y0 * (x1 - x0) > (y1 - y0) * x0):
+ // (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
+ // (1) => b = y0 - ((y1 - y0) / (x1 - x0))
* x0
+ //
+ // for intersection of y-axis and polygon edge, we need
b > 0:
+ // from (1) => y0 - ((y1 - y0) / (x1 - x0)) *
x0 > 0
+ // (2) => y0 > ((y1 - y0) / (x1 - x0)) * x0
+ // from 'if (x0 > x1)' above, we know that x1 >= x0:
+ // => x1 - x0 >= 0
+ // from (2) => y0 * (x1 - x0) > (y1 - y0) * x0
if ((x0 < 0 && x1 >= 0) && (y0 * (x1 - x0)) > ((y1 -
y0) * x0))
inside = !inside;
}
diff --git a/src/uk/me/parabola/mkgmap/main/MapMaker.java
b/src/uk/me/parabola/mkgmap/main/MapMaker.java
index cd36079..7eaa23f 100644
--- a/src/uk/me/parabola/mkgmap/main/MapMaker.java
+++ b/src/uk/me/parabola/mkgmap/main/MapMaker.java
@@ -168,7 +168,7 @@ public class MapMaker implements MapProcessor {
int pointType = shape.getPoiType();
- // only make a point if the shape has a name
and we know what type of point to make
+ // only make a point if we know what type of
point to make
if (pointType == 0)
continue;
@@ -178,7 +178,6 @@ public class MapMaker implements MapProcessor {
continue;
// check if there is not already a poi in that
shape
-
if(poiMap.findPointInShape(shape, pointType,
shapeName) == null)
{
MapPoint newPoint = new MapPoint();
diff --git a/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java
b/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java
index 54585e2..e6f9db0 100644
--- a/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java
+++ b/test/uk/me/parabola/mkgmap/general/PointInShapeTest.java
@@ -1,5 +1,14 @@
/**
- *
+ * Copyright (C) 2009 Ben Konrath <b...@bagu.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
*/
package uk.me.parabola.mkgmap.general;
@@ -19,6 +28,7 @@ import org.junit.Test;
public class PointInShapeTest {
private MapShape square;
+ private MapShape unclosedSquare;
private MapShape triangle;
private MapShape line;
private final int squareSize = 4;
@@ -38,7 +48,17 @@ public class PointInShapeTest {
);
square = new MapShape();
square.setPoints(points);
-
+
+ // Unclosed Square
+ points = Arrays.asList(
+ new Coord(0, 0),
+ new Coord(0, squareSize),
+ new Coord(squareSize, squareSize),
+ new Coord(squareSize, 0)
+ );
+ unclosedSquare = new MapShape();
+ unclosedSquare.setPoints(points);
+
// Triangle
points = Arrays.asList(
new Coord(0,0),
@@ -143,7 +163,7 @@ public class PointInShapeTest {
@Test
public void testCornerPointsOutsideSquare() {
- // tests above / below corner points, outside squate
+ // tests above / below corner points, outside square
for (Coord cornerpoint : square.getPoints()) {
int yadd = cornerpoint.getLongitude() > 0 ? 1 : -1;
int x = cornerpoint.getLatitude();
@@ -172,7 +192,6 @@ public class PointInShapeTest {
}
}
-
@Test
public void testLinePointsInsideTriangle() {
// inside triangle, above / below lines
@@ -283,4 +302,44 @@ public class PointInShapeTest {
assertFalse("point (" + co.getLatitude() + ", " +
co.getLongitude() + ") should be outside line",
line.contains(co));
}
+
+ @Test
+ public void testUnclosedShape() {
+
+ // inside unclosed 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 unclosed square",
+ unclosedSquare.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 unclosed square",
+ unclosedSquare.contains(coord));
+ }
+
+ // outside unclosed square, 1 unit from line
+ 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 unclosed square",
+ unclosedSquare.contains(coord));
+ }
+ }
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
