Hi Gerd
Here is a patch that should fix the problem - In the original code I
got carried away with the symmetry of Lat/Lon handling in the distance
calculation but the set-up for the crossing calculation isn't
symmetric!
I've also explained the ON error area more carefully and used INFINITY
instead of NaN because that is the horizontal distance where a line
through the node would meet a horizontal polygon side.
Ticker
On Fri, 2020-05-22 at 21:44 +0100, Ticker Berkin wrote:
> Hi Gerd
>
> I think I understand what is going wrong. I'll do another patch
> tomorrow.
>
> Ticker
>
>
> On Fri, 2020-05-22 at 13:36 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > the patched version still returns ON for a Coord which is not ON
> > and
> > thus doesn't work with my example.
> > The result doesn't depend on the position of the last point of the
> > way as long as it is builds a nearly or exactly straight line with
> > two nodes of the shape.
> >
> > Your algorithm returns true for each such point, even when it is
> > 100m
> > away from any shape vertex.
> > See my new example where A,B and C build a straight line. Another
> > node is very close to the edge but still returns IN (OK)
> >
> > Gerd
> >
> >
> > ________________________________________
> > Von: mkgmap-dev <[email protected]> im Auftrag
> > von Ticker Berkin <[email protected]>
> > Gesendet: Donnerstag, 21. Mai 2020 17:07
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] Explanation of the is_in function
> >
> > Hi Gerd
> >
> > Here is patch that prevents possible underflow when node is very
> > close
> > to an almost horizontal or vertical line and incorrect results when
> > exactly on this line.
> >
> > Ticker
> >
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/util/IsInUtil.java
===================================================================
--- src/uk/me/parabola/util/IsInUtil.java (revision 4498)
+++ src/uk/me/parabola/util/IsInUtil.java (working copy)
@@ -351,27 +351,30 @@
++lhsCount; // definite line segment all slightly to the left
} else { // need to consider this segment more carefully.
if (leadLat == trailLat)
- lonDif = 0; // dif meaningless; will be ignored in crossing calc, 0 handled for distToLine calc
+ lonDif = Double.POSITIVE_INFINITY; // horizontal lines ignored in crossing calc, infinity handled in distToLine calc
else
lonDif = nodeLon - trailLon - (double)(nodeLat - trailLat) / (leadLat - trailLat) * (leadLon - trailLon);
- if (leadLon == trailLon)
- latDif = 0; // ditto
- else
- latDif = nodeLat - trailLat - (double)(nodeLon - trailLon) / (leadLon - trailLon) * (leadLat - trailLat);
- // calculate distance to segment using right-angle attitude theorem
- final double lonDifSqrd = lonDif*lonDif;
- final double latDifSqrd = latDif*latDif;
- log.debug("inBox", leadLon-nodeLon, leadLat-nodeLat, trailLon-nodeLon, trailLat-nodeLat, lonDif, latDif, lhsCount, rhsCount);
- // there a small area between the square EPS_HP*2 and the circle within, where, if polygon vertix and
- // segments are the other side, it might still be calculated as ON.
- if (lonDif == 0)
- distSqrd = latDifSqrd;
- else if (latDif == 0)
- distSqrd = lonDifSqrd;
- else
- distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
- if (distSqrd < EPS_HP_SQRD)
- return ON;
+ if ((minLon - EPS_HP <= nodeLon) && (maxLon + EPS_HP >= nodeLon)) { // check if the point is ON the line
+ if (leadLon == trailLon)
+ latDif = Double.POSITIVE_INFINITY; // handled in distToLine calc
+ else
+ latDif = nodeLat - trailLat - (double)(nodeLon - trailLon) / (leadLon - trailLon) * (leadLat - trailLat);
+ // calculate distance to segment using right-angle attitude theorem
+ log.debug("inBox", leadLon-nodeLon, leadLat-nodeLat, trailLon-nodeLon, trailLat-nodeLat, lonDif, latDif, lhsCount, rhsCount);
+ // There can be a small area, within the square EPS_HP*2 around the node, but is not in the circle radius EPS_HP where a polygon
+ // vertix meets this square, that will be incorrectly calculated as ON
+ if (Double.isInfinite(lonDif))
+ distSqrd = latDif*latDif;
+ else if (Double.isInfinite(latDif))
+ distSqrd = lonDif*lonDif;
+ else if (Math.abs(lonDif) < EPS_HP || Math.abs(latDif) < EPS_HP)
+ return ON;
+ else
+ distSqrd = lonDif*lonDif * latDif*latDif / (lonDif*lonDif + latDif*latDif);
+ if (distSqrd < EPS_HP_SQRD)
+ return ON;
+ } else
+ log.debug("inSlice", leadLon-nodeLon, leadLat-nodeLat, trailLon-nodeLon, trailLat-nodeLat, lonDif, "N/A", lhsCount, rhsCount);
if ((trailLat <= nodeLat && leadLat > nodeLat) || // an upward crossing
(trailLat > nodeLat && leadLat <= nodeLat)) { // a downward crossing
if (lonDif < 0)
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
