Commit: r996: Fix rounding in two places.
Version 996 was commited by steve on 2009-04-05 19:43:28 +0100 (Sun, 05 Apr 2009) Fix rounding in two places. Before the patch clipping was a little inaccurate. Some points 2m outside the bounding box gets included in the img. With this patch it works correctly now. I've tested this since some days and up to now found no new failures. Whatever the reason for this small delta was, there should be no bad effects, if one adds a somewhat bigger delta. - Johann Gail
Hi Steve, I ran across a case that didn't get covered by Johann Gail patch. Please find a patch against trunk attached to fix this issue along with a unit test. As an aside, I noticed that ends[1] is calculated using y0 and x0 values, not y1 and x1. I haven't read the algorithm on web page mentioned in the comments, but I'm just wondering if that's correct? Thanks, Ben svn commit wrote:
Version 996 was commited by steve on 2009-04-05 19:43:28 +0100 (Sun, 05 Apr 2009)
Fix rounding in two places.
Before the patch clipping was a little inaccurate. Some points 2m outside the bounding box gets included in the img. With this patch it works correctly now.
I've tested this since some days and up to now found no new failures. Whatever the reason for this small delta was, there should be no bad effects, if one adds a somewhat bigger delta.
- Johann Gail _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
diff --git a/src/uk/me/parabola/mkgmap/general/LineClipper.java b/src/uk/me/parabola/mkgmap/general/LineClipper.java index 55aa51d..76e730d 100644 --- a/src/uk/me/parabola/mkgmap/general/LineClipper.java +++ b/src/uk/me/parabola/mkgmap/general/LineClipper.java @@ -136,10 +136,10 @@ public class LineClipper { double d = 0.5; if (t[0] > 0) - ends[0] = new Coord((int) (y0 + t[0] * dy + d), (int) (x0 + t[0] * dx + d)); + ends[0] = new Coord((int) (y0 + t[0] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[0] * dx + (x0 > 0 ? d : -d))); if (t[1] < 1) - ends[1] = new Coord((int)(y0 + t[1] * dy + d), (int) (x0 + t[1] * dx + d)); + ends[1] = new Coord((int)(y0 + t[1] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[1] * dx + (x0 > 0 ? d : -d))); return ends; } diff --git a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java index 80fdbb9..85ab7a9 100644 --- a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java +++ b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java @@ -51,6 +51,11 @@ public class LineClipperTest { new Coord(132, 230) }; assertArrayEquals("example result", result, listList.get(0).toArray()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } } /** @@ -76,6 +81,10 @@ public class LineClipperTest { // No empty lists for (List<Coord> lco : list) assertTrue("empty list", !lco.isEmpty()); + + // All points should be inside Area + for (List<Coord> lco : list) + assertTrue("all coords should be inside area", a.allInside(lco)); // Check values Coord[] firstExpectedLine = { @@ -106,4 +115,25 @@ public class LineClipperTest { List<List<Coord>> list = LineClipper.clip(a, l); assertNull("all lines inside", list); } + + /** + * This test comes from real osm data that caused a problem. + */ + @Test + public void testAreaInSecondQuadrant() { + Area a = new Area(435809, -3916474, 436165, -3915960); + Coord[] co = { + new Coord(436009, -3915955), + new Coord(435956, -3916034), + }; + + List<List<Coord>> listList = LineClipper.clip(a, Arrays.asList(co)); + assertTrue("list should be empty", !listList.isEmpty()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } + } + }
Hi Steve, Just wondering if you've had a chance to look at this patch? Thanks, Ben On Mon, Apr 6, 2009 at 12:57 AM, Ben Konrath <ben@bagu.org> wrote:
Hi Steve,
I ran across a case that didn't get covered by Johann Gail patch. Please find a patch against trunk attached to fix this issue along with a unit test.
As an aside, I noticed that ends[1] is calculated using y0 and x0 values, not y1 and x1. I haven't read the algorithm on web page mentioned in the comments, but I'm just wondering if that's correct?
Thanks, Ben
svn commit wrote:
Version 996 was commited by steve on 2009-04-05 19:43:28 +0100 (Sun, 05 Apr 2009) Fix rounding in two places.
Before the patch clipping was a little inaccurate. Some points 2m outside the bounding box gets included in the img. With this patch it works correctly now.
I've tested this since some days and up to now found no new failures. Whatever the reason for this small delta was, there should be no bad effects, if one adds a somewhat bigger delta.
- Johann Gail _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
diff --git a/src/uk/me/parabola/mkgmap/general/LineClipper.java b/src/uk/me/parabola/mkgmap/general/LineClipper.java index 55aa51d..76e730d 100644 --- a/src/uk/me/parabola/mkgmap/general/LineClipper.java +++ b/src/uk/me/parabola/mkgmap/general/LineClipper.java @@ -136,10 +136,10 @@ public class LineClipper {
double d = 0.5; if (t[0] > 0) - ends[0] = new Coord((int) (y0 + t[0] * dy + d), (int) (x0 + t[0] * dx + d)); + ends[0] = new Coord((int) (y0 + t[0] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[0] * dx + (x0 > 0 ? d : -d)));
if (t[1] < 1) - ends[1] = new Coord((int)(y0 + t[1] * dy + d), (int) (x0 + t[1] * dx + d)); + ends[1] = new Coord((int)(y0 + t[1] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[1] * dx + (x0 > 0 ? d : -d))); return ends; }
diff --git a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java index 80fdbb9..85ab7a9 100644 --- a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java +++ b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java @@ -51,6 +51,11 @@ public class LineClipperTest { new Coord(132, 230) }; assertArrayEquals("example result", result, listList.get(0).toArray()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } }
/** @@ -76,6 +81,10 @@ public class LineClipperTest { // No empty lists for (List<Coord> lco : list) assertTrue("empty list", !lco.isEmpty()); + + // All points should be inside Area + for (List<Coord> lco : list) + assertTrue("all coords should be inside area", a.allInside(lco));
// Check values Coord[] firstExpectedLine = { @@ -106,4 +115,25 @@ public class LineClipperTest { List<List<Coord>> list = LineClipper.clip(a, l); assertNull("all lines inside", list); } + + /** + * This test comes from real osm data that caused a problem. + */ + @Test + public void testAreaInSecondQuadrant() { + Area a = new Area(435809, -3916474, 436165, -3915960); + Coord[] co = { + new Coord(436009, -3915955), + new Coord(435956, -3916034), + }; + + List<List<Coord>> listList = LineClipper.clip(a, Arrays.asList(co)); + assertTrue("list should be empty", !listList.isEmpty()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } + } + }
Hi Ben, yes, my patch was only the one half and your solution is more correct. But also not 100%. While looking at your patch I see another small error: Not the value of y0 should be compared to zero, but the result of (y0 + t[0] * dy) The best solution would be in my eyes a new constructor for a Coord object which accepts floats or doubles and does the rounding internal. Regards, Johann Ben Konrath schrieb:
Hi Steve,
Just wondering if you've had a chance to look at this patch?
Thanks, Ben
On Mon, Apr 6, 2009 at 12:57 AM, Ben Konrath <ben@bagu.org> wrote:
Hi Steve,
I ran across a case that didn't get covered by Johann Gail patch. Please find a patch against trunk attached to fix this issue along with a unit test.
As an aside, I noticed that ends[1] is calculated using y0 and x0 values, not y1 and x1. I haven't read the algorithm on web page mentioned in the comments, but I'm just wondering if that's correct?
Thanks, Ben
svn commit wrote:
Version 996 was commited by steve on 2009-04-05 19:43:28 +0100 (Sun, 05 Apr 2009) Fix rounding in two places.
Before the patch clipping was a little inaccurate. Some points 2m outside the bounding box gets included in the img. With this patch it works correctly now.
I've tested this since some days and up to now found no new failures. Whatever the reason for this small delta was, there should be no bad effects, if one adds a somewhat bigger delta.
- Johann Gail _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
diff --git a/src/uk/me/parabola/mkgmap/general/LineClipper.java b/src/uk/me/parabola/mkgmap/general/LineClipper.java index 55aa51d..76e730d 100644 --- a/src/uk/me/parabola/mkgmap/general/LineClipper.java +++ b/src/uk/me/parabola/mkgmap/general/LineClipper.java @@ -136,10 +136,10 @@ public class LineClipper {
double d = 0.5; if (t[0] > 0) - ends[0] = new Coord((int) (y0 + t[0] * dy + d), (int) (x0 + t[0] * dx + d)); + ends[0] = new Coord((int) (y0 + t[0] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[0] * dx + (x0 > 0 ? d : -d)));
if (t[1] < 1) - ends[1] = new Coord((int)(y0 + t[1] * dy + d), (int) (x0 + t[1] * dx + d)); + ends[1] = new Coord((int)(y0 + t[1] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[1] * dx + (x0 > 0 ? d : -d))); return ends; }
diff --git a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java index 80fdbb9..85ab7a9 100644 --- a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java +++ b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java @@ -51,6 +51,11 @@ public class LineClipperTest { new Coord(132, 230) }; assertArrayEquals("example result", result, listList.get(0).toArray()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } }
/** @@ -76,6 +81,10 @@ public class LineClipperTest { // No empty lists for (List<Coord> lco : list) assertTrue("empty list", !lco.isEmpty()); + + // All points should be inside Area + for (List<Coord> lco : list) + assertTrue("all coords should be inside area", a.allInside(lco));
// Check values Coord[] firstExpectedLine = { @@ -106,4 +115,25 @@ public class LineClipperTest { List<List<Coord>> list = LineClipper.clip(a, l); assertNull("all lines inside", list); } + + /** + * This test comes from real osm data that caused a problem. + */ + @Test + public void testAreaInSecondQuadrant() { + Area a = new Area(435809, -3916474, 436165, -3915960); + Coord[] co = { + new Coord(436009, -3915955), + new Coord(435956, -3916034), + }; + + List<List<Coord>> listList = LineClipper.clip(a, Arrays.asList(co)); + assertTrue("list should be empty", !listList.isEmpty()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } + } + }
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev .
Hi Johann, Nice catch! I've updated the patch to fix the problem you described. I didn't add a new constructor to Coord because there is already a method Coord(double, double) for converting regular latitude and longitude. Also, the doubles we are dealing with here are already in mapunits, they are just doubles because of the math involved. I think that this is a relatively small use case and therefore it should be dealt with in the LineClipper class. Let me know if this needs more work to get committed. Cheers, Ben On Thu, Apr 30, 2009 at 3:50 PM, Johann Gail <johann.gail@gmx.de> wrote:
Hi Ben,
yes, my patch was only the one half and your solution is more correct. But also not 100%. While looking at your patch I see another small error:
Not the value of y0 should be compared to zero, but the result of (y0 + t[0] * dy)
The best solution would be in my eyes a new constructor for a Coord object which accepts floats or doubles and does the rounding internal.
Regards, Johann
Ben Konrath schrieb:
Hi Steve,
Just wondering if you've had a chance to look at this patch?
Thanks, Ben
On Mon, Apr 6, 2009 at 12:57 AM, Ben Konrath <ben@bagu.org> wrote:
Hi Steve,
I ran across a case that didn't get covered by Johann Gail patch. Please find a patch against trunk attached to fix this issue along with a unit test.
As an aside, I noticed that ends[1] is calculated using y0 and x0 values, not y1 and x1. I haven't read the algorithm on web page mentioned in the comments, but I'm just wondering if that's correct?
Thanks, Ben
svn commit wrote:
Version 996 was commited by steve on 2009-04-05 19:43:28 +0100 (Sun, 05 Apr 2009) Fix rounding in two places.
Before the patch clipping was a little inaccurate. Some points 2m outside the bounding box gets included in the img. With this patch it works correctly now.
I've tested this since some days and up to now found no new failures. Whatever the reason for this small delta was, there should be no bad effects, if one adds a somewhat bigger delta.
- Johann Gail _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
diff --git a/src/uk/me/parabola/mkgmap/general/LineClipper.java b/src/uk/me/parabola/mkgmap/general/LineClipper.java index 55aa51d..76e730d 100644 --- a/src/uk/me/parabola/mkgmap/general/LineClipper.java +++ b/src/uk/me/parabola/mkgmap/general/LineClipper.java @@ -136,10 +136,10 @@ public class LineClipper {
double d = 0.5; if (t[0] > 0) - ends[0] = new Coord((int) (y0 + t[0] * dy + d), (int) (x0 + t[0] * dx + d)); + ends[0] = new Coord((int) (y0 + t[0] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[0] * dx + (x0 > 0 ? d : -d)));
if (t[1] < 1) - ends[1] = new Coord((int)(y0 + t[1] * dy + d), (int) (x0 + t[1] * dx + d)); + ends[1] = new Coord((int)(y0 + t[1] * dy + (y0 > 0 ? d : -d)), (int) (x0 + t[1] * dx + (x0 > 0 ? d : -d))); return ends; }
diff --git a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java index 80fdbb9..85ab7a9 100644 --- a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java +++ b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java @@ -51,6 +51,11 @@ public class LineClipperTest { new Coord(132, 230) }; assertArrayEquals("example result", result, listList.get(0).toArray()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } }
/** @@ -76,6 +81,10 @@ public class LineClipperTest { // No empty lists for (List<Coord> lco : list) assertTrue("empty list", !lco.isEmpty()); + + // All points should be inside Area + for (List<Coord> lco : list) + assertTrue("all coords should be inside area", a.allInside(lco));
// Check values Coord[] firstExpectedLine = { @@ -106,4 +115,25 @@ public class LineClipperTest { List<List<Coord>> list = LineClipper.clip(a, l); assertNull("all lines inside", list); } + + /** + * This test comes from real osm data that caused a problem. + */ + @Test + public void testAreaInSecondQuadrant() { + Area a = new Area(435809, -3916474, 436165, -3915960); + Coord[] co = { + new Coord(436009, -3915955), + new Coord(435956, -3916034), + }; + + List<List<Coord>> listList = LineClipper.clip(a, Arrays.asList(co)); + assertTrue("list should be empty", !listList.isEmpty()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } + } + }
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev .
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
diff --git a/src/uk/me/parabola/mkgmap/general/LineClipper.java b/src/uk/me/parabola/mkgmap/general/LineClipper.java index 55aa51d..06c61f4 100644 --- a/src/uk/me/parabola/mkgmap/general/LineClipper.java +++ b/src/uk/me/parabola/mkgmap/general/LineClipper.java @@ -135,11 +135,17 @@ public class LineClipper { assert t[1] <= 1; double d = 0.5; - if (t[0] > 0) - ends[0] = new Coord((int) (y0 + t[0] * dy + d), (int) (x0 + t[0] * dx + d)); + if (t[0] > 0) { + double lat = y0 + t[0] * dy; + double lon = x0 + t[0] * dx; + ends[0] = new Coord((int) ( lat + (lat > 0 ? d : -d)), (int) (lon + (lon > 0 ? d : -d))); + } - if (t[1] < 1) - ends[1] = new Coord((int)(y0 + t[1] * dy + d), (int) (x0 + t[1] * dx + d)); + if (t[1] < 1) { + double lat = y0 + t[1] * dy; + double lon = x0 + t[1] * dx; + ends[1] = new Coord((int)(lat + (lat > 0 ? d : -d)), (int) (lon + (lon > 0 ? d : -d))); + } return ends; } diff --git a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java index 80fdbb9..78fa03b 100644 --- a/test/uk/me/parabola/mkgmap/general/LineClipperTest.java +++ b/test/uk/me/parabola/mkgmap/general/LineClipperTest.java @@ -51,6 +51,11 @@ public class LineClipperTest { new Coord(132, 230) }; assertArrayEquals("example result", result, listList.get(0).toArray()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } } /** @@ -77,6 +82,10 @@ public class LineClipperTest { for (List<Coord> lco : list) assertTrue("empty list", !lco.isEmpty()); + // All points should be inside Area + for (List<Coord> lco : list) + assertTrue("all coords should be inside area", a.allInside(lco)); + // Check values Coord[] firstExpectedLine = { new Coord(100, 108), @@ -106,4 +115,25 @@ public class LineClipperTest { List<List<Coord>> list = LineClipper.clip(a, l); assertNull("all lines inside", list); } + + /** + * This test comes from real osm data that caused a problem. + */ + @Test + public void testAreaInSecondQuadrant() { + Area a = new Area(435809, -3916474, 436165, -3915960); + Coord[] co = { + new Coord(436009, -3915955), + new Coord(435956, -3916034), + }; + + List<List<Coord>> listList = LineClipper.clip(a, Arrays.asList(co)); + assertTrue("list should be empty", !listList.isEmpty()); + + // All points should be inside Area + for (List<Coord> list : listList) { + assertTrue("all coords should be inside area", a.allInside(list)); + } + } + }
Ben Konrath schrieb:
Hi Johann,
Nice catch! I've updated the patch to fix the problem you described. I didn't add a new constructor to Coord because there is already a method Coord(double, double) for converting regular latitude and longitude. Also, the doubles we are dealing with here are already in mapunits, they are just doubles because of the math involved. I think that this is a relatively small use case and therefore it should be dealt with in the LineClipper class.
Hi Ben, I haven't tested, but for me it looks okay now. Greetings, Johann
participants (3)
-
Ben Konrath -
Johann Gail -
svn commit