Geodesic preciseness

[MysticJay]

picking up an old issue, that already existed in legacy IITC:
iitc-project/ingress-intel-total-conversion#1011

The issue has not been resolved and can still be reproduced:
create a link from A to C and check the offset at location B
A: https://intel.ingress.com/intel?ll=55.477626,9.458853&z=17
B: https://intel.ingress.com/intel?ll=54.73925,9.439722&z=17
C: https://intel.ingress.com/intel?ll=53.785501,9.415725&z=17

The below picture shows
red line: stock Intel (manually added to the picture)
purple/pink line: IITC/IITC-CE
red dottet line: what Niantic reports back to be a blocker

The offset in the chosen example is about 12m (this value may vary in different locations all over the world). It seems always to be an east-west issue.
So while the drawn purple line does not touch the left links and these are indicated a crosslinks, the right link is not - even though the draw crosses it (a bit further up).

[MysticJay]

We have investigated this and found that the link actually consists of small peaces, each 5000 m lenght.
we can reduce the lenght of these segments for the cost of speed.
A value of 500m gives a very good preciseness.
The fault in above sample is no longer visible.

1. We need to collect samples from different places over the world.
2. We propose to reduce the value or have it adjustable. allowed values should be 200m - 5000m per segment

Alternatively we could try to use a different geodesic function, but we are yet not sure if it is really a different function (maths-wise) and if the communities would accept that change.

If some Math-Superbrain could confirm that the two functions do the same it would be an option.
check here: https://github.com/springmeyer/arc.js

[johnd0e]

If some Math-Superbrain could confirm that the two functions do the same it would be an option.
check here: https://github.com/springmeyer/arc.js

ingress-intel-total-conversion/external/L.Geodesic.js

Line 47 in 256f9c5

// maths based on http://williams.best.vwh.net/avform.htm#Int

As you can see our geodesic library is originally based on the same algorithm as arc.js (but implementation details may differ).

Stock intel code is known to use another library: geodesy (there is also leaflet-friendly lib based on this: Leaflet.Geodesic).

[McBen]

Its not about the geodesic function. Its about "how to draw a curved line".

[...] each 5000 m lenght

no. maybe in your observation but the real rule is: divide a line into
(longitude1- longitude2)*earth_radius*(2*pi/360) / 5000 straight lines

A value of 500m gives a very good preciseness.

what is "good"? the next bug report may tell you: "plz fix the 1m differenz"

so, how to draw an curved line?
There is no hardware support. To be accurate you've to draw it pixel by pixel.
This is usally not practical. So you've to divide the curved line into smaller pieces depending on the curve value and zoom level. This is the basic idea of the above formula.

For a better solution you've to recalculate every line depending on zoom level.
The difficult part is the "curved value" 'cause it depends on start/end coords and visible area.

[johnd0e]

The difficult part is the "curved value" 'cause it depends on start/end coords and visible area.

Well, there are ready-to-use formulas, but.. it's still a huge work - to implement all this stuff efficiently.

As for me - I do not have enough math background for such work.

But I can implement customizable option for segment length, so everyone will have ability to set value that fits some particular conditions.

I agree with @McBen, that it is far from ultimate solution, but in any case - it is better than what we have currently.

But we'll leave this issue open, and wait for better alternatives.

[johnd0e]

A value of 500m gives a very good preciseness.

what is "good"?

I suppose 'good' is close to stock intel.

I'm not sure that we can reverse dashboard.js code, but we know what formulas it is based on.
And we even have corresponding leaflet lib to try.

[MysticJay]

Its not about the geodesic function. Its about "how to draw a curved line".
While you are right in detail I tried to keep the explanation as simple as possible. Digital computers can not draw a curved line, they can only make very, very small moves, practically impossible to see for a human eye.

[...] each 5000 m lenght

no. maybe in your observation but the real rule is: divide a line into
(longitude1- longitude2)*earth_radius*(2*pi/360) / 5000 straight lines
correct too, but explaining the segments can be up to 9999m long does not help to solve the issue

A value of 500m gives a very good preciseness.

what is "good"? the next bug report may tell you: "plz fix the 1m differenz"
For the MAP, NIA, and the scanner all these thoughts are void, they tell you exactly where the planned link causes a cross link. The issue is about what we see at maximum zoom level.

so, how to draw an curved line?
There is no hardware support. To be accurate you've to draw it pixel by pixel.
This is usally not practical. So you've to divide the curved line into smaller pieces depending on the curve value and zoom level. This is the basic idea of the above formula.

For a better solution you've to recalculate every line depending on zoom level.
The difficult part is the "curved value" 'cause it depends on start/end coords and visible area.
the zoom level has no influence on the observed effect here.

Each link has to be calculated from start to end, while only the visible part is displayed. The offset (in meters) is always the same. The interpolation done will only take care that start and end of the link hit the defined coords. The smaller the steps the less offset, but the more compute power used.

So what do you think about reducing the divider to 500?

[McBen]

I suppose 'good' is close to stock intel.

I don't care about stock intel. I want a "correct" line. A line that nia-server will accept as "not crossing".
(hopefully stock-intel is close to it..but I've no idea)

So what do you think about reducing the divider to 500?

it's a shot into the dark. stealing performance from everybody and maybe help fixing your special problem.... no real solution

[Jormund]

@McBen when do you need the drawn line to be correct as long as crosslink is correct?
Crosslink uses the theoretical arc and not the drawn approximation.

[johnd0e]

the zoom level has no influence on the observed effect here.

At low zoom levels that offset will be less than 1 pixel. So no sense to spend CPU and memory.

Each link has to be calculated from start to end, while only the visible part is displayed.

Again: we do not care about offscreen precision, to better would be not calculate (and store) that unneeded points.

[johnd0e]

@Jormund
Yeah, @McBen is author of crosslink

So I'm also interesting: how does it handle all this?

[MysticJay]

And it is not a shot into dark, we have tested it.
The Cross links are calculated not based on the visualization.
The drawn link does not have any influence on that decision, even if we displayed it as a straight line.
So yes it is all about making it not (visibly) cross its own crosslinks.
(Updated: removed "Nia does the calculation")

[johnd0e]

@MysticJay
It's obvious that 500 is more precise than 5000. But for most links we actually do not need such precision.

And precision is not free. Mobiles (and some desktops) may be short on resources.

[MysticJay]

A way more complex problem is what happens if (in the above example) we not only have the A-C-link, but also plan about linking away from that middle portal (B), E.g. for a protective link. You would rather plan to the left. So yes, as a planner and operator I need a preciseness that will not lead me wrong.

[McBen]

@Jormund here we're talking about visual correctness. And as we all know: iitc is wrong (in some cases)..like we know that the game-client itself sucks at this.

@johnd0e "how does it handle all this?" In fact the current crosslink calculation was done by -good guy- Jon Atkins!. The difference: it's pure math instead of approximation. It can be solved with even more simpler math - high-school-level. I'll create a PR if I've got time.

But as said, calculation and drawing are differnt jobs.

[johnd0e]

@McBen

It can be solved with even more simpler math - high-school-level. I'll create a PR if I've got time.

Do you mean improved collision test algorithm that was commited in your fork?

[johnd0e]

To summarize.
Ideal geodesic implementation should apply to rendering only, taking into account current visible map bounds.

I suppose we have to override _project method of L.Polyline (and/or _projectLatlngs).

There is also promising _clipPoints method, which actually limit rendering to visible parts.
But it is applied to already projected shape (and L.LineUtil.clipSegment is not geodesic aware).
So again it seems not that simple..

Anyway, even if we extend only _project - it is worth enough, and can simplify things a lot (in many places).
E.g. it let us use plain L.Polyline with added options.geodesic.

[johnd0e]

But I can implement customizable option for segment length, so everyone will have ability to set value that fits some particular conditions.

Done: https://github.com/IITC-CE/Leaflet.Geodesic/

[johnd0e]

@McBen
If you have ideas for improvement - welcome here:
IITC-CE/Leaflet.Geodesic#4

It is draft PR, where we do not store intermediate points anymore.
Instead they are calculated on every projection (which typically occurs on zoom/viewreset).

• greatly simplify classes, and increase compatibility with L.Polyline-related routines (especially 3rd-party).
• changes in performance is unmeasured yet
  • memory footprint is lower
  • recalculations may be more frequent (unsure)

But besides mentioned benefits there is also plenty space for future improvement:

• depend on zoom
• depend on map bounds
  • include lines/bounds intersections to points
  • clip to bounds (not calculate invisible parts)

[johnd0e]

@MysticJay
Use this plugin in latest test build:

custom-geodesic.user.js

// ==UserScript==
// @id             custom-geodesic
// @name           IITC plugin: Custom geodesic
// @category       Custom
// @version        0.1.0
// @description    Customize geodesic precision by increasing intermediate points count
// @namespace      https://github.com/IITC-CE/ingress-intel-total-conversion
// @include        https://intel.ingress.com/*
// @grant          none
// ==/UserScript==


if (typeof window.plugin !== 'function') window.plugin = function() {};
(function wrapper (plugin_info) {

function setup () {
  L.GeodesicCircle.mergeOptions({           // default:
    segmentsCoeff: 500,                     //    1000
    segmentsMin: 96                         //      48
  });
  var polyOptions = { segmentsCoeff: 500 }; //    5000
  L.GeodesicPolyline.mergeOptions(polyOptions);
  L.GeodesicPolygon.mergeOptions(polyOptions);
}
setup.priority = 'high';

setup.info = plugin_info; //add the script info data to the function as a property
if (!window.bootPlugins) window.bootPlugins = [];
window.bootPlugins.push(setup);
if (window.iitcLoaded && typeof setup === 'function') setup();
})({ script: typeof GM_info !== 'undefined' && GM_info.script && {
  version: GM_info.script.version, name: GM_info.script.name, description: GM_info.script.description
}})// wrapper end

[johnd0e]

Currently segments count calculation is based not on line length, but on longitude difference.
That's why precision for 'vertical' lines is worse than 'horizontal'.
But such approach still can be reasonable, as it simplifies math a lot...

Anyway, we can use distance formula:

    var distance = Math.acos(
      Math.sin(lat1) * Math.sin(lat2) +
      Math.cos(lat1) * Math.cos(lat2) * Math.cos(-dLng));
    var segments = Math.ceil(distance * earthR / segmentLength);

And this fixes case with set of given 3 portals, even if we use far greater coefficient: var segmentLength = 1000000;.

[MysticJay]

The longer the segmentlenght the bigger is the offset, where curve and straight line between the nodes of the segmented poliline differ most (in the middle between nodes).
The shorter the segmentlenght the more calculations have to be done.
The bigger the zoom, the less links have to be calculated, i.e. if we have only "few" links to calculate we can go for a smaller segmentlenght.

Proposal 1:
We can define SegmentLength acording to the min linklength Intel is showing,

z<7 (lenght>10,000), segmentlenght=10,000
...
z=12 (lenght>300), segmentlenght=300
z>12 (lenght>0), segmentlength =150

Implementing a table of fixed values for each zoom-level should do the job.

Proposal 2:
As my tests have not shown any significant offset with segmentlenght >1000, neither an improvement with smaller values I even propose
z<=10 (lenght >2,500), segmentlenght = 10,000
z>10 (lenght >0), segmentlength=1,000

A simple if-statement could do the job.
(CustomGeodesicPreccision uses segmentsCoeff as "SegmentLength")
if (map.getZoom() > 10) { segmentsCoeff = 1000; } else { segmentsCoeff = 10000; };

[MysticJay]

It can be solved with even more simpler math - high-school-level. I'll create a PR if I've got time.

IMHO no real need. Crosslinks are only a few compared to the rest of the links. If everyone is fine with Jon's implementation, we should rather concentrate on other things. Put it on the Backlog in case CrossLinks-plugin needs other changes (like: crosslinks should also test if drawn links cross each other).

[MysticJay]

Summary of the discussion on this issue:

1. Is a change needed? Yes.
   
   This is the same portal/location as in the first post. While the user thinks everything is OK, the drawn field is not possible, as the drawn link passes the marked portal on the wrong side. If this was an existing link, crosslinks (which needs to be additionally installed) would mark the two links to the portal red, but the user would still be questioning the reason. Even if crosslinks would be enhanced and detect the two links to the portal and the right link as xlinks the irritation is still there.

2. Do we know why this is happening? Yes.
   To understand this we need to know two things:
   a) Our links follow "great circles" which have a circumference of aprox. 40,000 kilometers.
   b) The map of the world that we use is stretched and squeezed. When zoomed out, a line of 10km near the equator would show as a few dots, while near the north pole the line is displayed on the screen with a reasonable length (see Mercator-Projection).

Drawing a circle on the map is implemented as drawing a polyline. Each segment (math "chord") of the polyline will be close to the circle. The shorter the segments the more the drawn polyline matches the circle (still it will have a small offset). The downside of this preciseness is CPU-usage. The shorter the segments the more coordinates for the nodes at start and end of the segment need to be calculated.

Now the original developer found, that a vertical (North-South) link would show as a straight line, what ever the length is. So he only used the "horizontal" distance dLON as length to calculate the number of segments for all links. A mistake, but read ahead...

The current implementation uses 5000 (meters) as a divider, that means 8km would be 1.6 segments. A well chosen value, used in some other implementations as well. But then he truncated the result to "1" segment, which means, 9.99 km would fit into 1 segment. Should not matter much, but as only dLON was calculated a long 150km link that only is 9km out of the N-S line would also only be represented with one segment. In the middle of that line the "offset" form the "correct" curve has its maximum. Returning to the example in the first post, is at 15m (other examples have resulted in an offset of even 34m).

The offset is different based on the LAT of the portals linked and becomes bigger the further to the poles.

3. Can we fix that? Yes, but...
   The first idea is to use Ceil() instead of floor() to truncate the number of segments. This already brings our test down to a few meters.
   The second idea is to use a lenght of the link that is closer to the real length, using dLON and dLAT and good old Pythagoras' formulas. The 150 km link would now be represented by 30 segments.
   The third idea is to reduce the divider so that we get a node every 1000m.
   ... but all these create quite a number of additional calculations. We need to compensate to not use (much) more compute power

4. Compensate? No
   Idea A: calculate a "divider" based on zoomlevel (and maybe some other display factors like resolution and screensize). We might even choose bigger values than 5000.

Idea B: if zoomed out (Z=8) we can not distiguish a portal's location from a nearby link. The offset becomes visible at "all links" detail level (Z>=13) and we can clearly distinguish portal and link from z>=15 (all portals). So why not use different calculation (see above) from Z>=15?

We now have to see what the ingress world looks like. A dense area will have a whole lot of links, but only few longer than 5km. A short test in Hamburg/Germany (8,000 portals in a 15km radius) at Z=13 showed 10 links >5km and none >10km, but hundreds of shorter links. The huge number of short links takes way more time than the additional segments for those 10 "long" links. OTOH a rural area will only have a few links, but these may be really long, maybe 100km. The length of the link will cause a lot of additional segments (20/100km), but only for a few links, nothing really time consuming.

So no, we do not really need to compensate.

5. Summary
   A close to ideal solution with segments of max 1000m length will be too costly. The current divider (5000) has been used in several implementations addressing a similar problem. Any idea to work with different segment lengths based on zoomlevel, curvature on the screen or coordinates, adds way more compute cycles than we win by reducing the number of nodes. Using the approximate (real) length of a link and not only the dLON value is an obvious need for any solution, thus this is the minimum to be done.

[MysticJay]

My proposal:

1. make approximate length the default.
2. use ceil() instead of floor() as default.
3. seek for easy ways to reduce the overall number of nodes to be calculated
4. do not overdo, keep the idea in mind.

Sidenote: crosslinks should detect on draws as well.

[MysticJay]

Captured today at: https://intel.ingress.com/?pll=55.456331,9.951137

related links:
{"maps":{"idOthers":{"label":"Others","state":1,"bkmrk":{}}},"portals":{"idOthers":{"label":"Others","state":1,"bkmrk":{"id1610798002885431":{"guid":"ecf475d81d1c4192b14303eb7df717f7.16","latlng":"55.480193,9.976049","label":"Brenderup Aktivitetscenter"},"id1610798008365513":{"guid":"154c13480f574312aa0df42a0cccf919.16","latlng":"55.350954,9.841514","label":"Sdr. Aaby Strand"},"id1610798016260616":{"guid":"435c628bdcbf4fe283307f2b4255f595.16","latlng":"55.456331,9.951137","label":"8 Miil "},"id1610798019692721":{"guid":"19ed6d73b0a44702958988ab378c708d.16","latlng":"55.436662,9.941699","label":"Ejby Kirke "}}}}}

[MysticJay]

line 17543: var segments = Math.ceil(Math.abs(dLng * earthR / this.options.segmentsCoeff));
line 17604: segmentsCoeff: 1000

[McBen]

Let me add some more details:
I calculated the maximum distance between the iitc drawn geodesicline and a full detailed arc (high segments value)

a) top (post 1) example:
is drawn as straight line (2 Points); max-error is 29 meter

b) example in #560
is drawn as straight line (2 Points); max-error is 0.22 meter

c) random long west-east link (from US to EU)
has 2899 Points; max-error is 0.86 meter

d) random long north-south link (from sweden to africa)
has 4 Points; max-error is 433 meter!
( [{"type":"polyline","latLngs":[{"lat":64.80713807412829,"lng":12.65625},{"lat":-7.306149605771363,"lng":12.48046875}],"color":"#a24ac3"}] )

---

with segmentsCoeff: 2000 values are
a) 3pts, 7.3m b) 3pts, 0.05m d) 10pts, 52m
(note: ~2000 is the limit for a+b to switch from 2 to 3points)

with segmentsCoeff: 1000 values are
a) 5pts, 1.8m b) 5pts, 0.01m d) 20pts, 12m
(c) 14,495pts, to much points for my quick calcualtion algorithm)

my test code; https://jsfiddle.net/mcben/rLcnug3w/16/

---

about arc.js:
arc.js and iitc are using the same math. arc is doing it recursive while iitc use an iterative approach.
Both requires a target segment count. In arc examples this is usually set to 100.
IITC tries a dynamic way (see above).

[MysticJay]

@McBen Thanks adding. 433m sounds really heavy, still I'd like to see, where that offset is visible. both ends of the line do not end on a portal. The max I was able to find on a close by link is 28m somewhere in the center.
used these portals:
[{"type":"polyline","latLngs":[{"lat":64.80713807412829,"lng":12.65625},{"lat":-7.306149605771363,"lng":12.48046875}],"color":"#a24ac3"},{"type":"polyline","latLngs":[{"lat":-4.792808,"lng":11.837257},{"lat":64.539563,"lng":11.265648}],"color":"#a24ac3"}]

[McBen]

nah, my math is not fully correct. It skips map transformation and uses simple trigonometry to calculate the error-point.
By visuall comparsion the real error seems to be only half of current distance (d) ~180m instead of 433m)

here is the code including visuals
https://jsfiddle.net/mcben/rLcnug3w/164/
(reveals the error in my calculation 'cause one maker should be on the red-line)

anyway, even 180m is quite far and 0.2meter is still a bug report.

[MysticJay]

@McBen 0.2 m is nothing we are able to display. in the end it is about visualization.

[McBen]

@McBen 0.2 m is nothing we are able to display. in the end it is about visualization.

#560

top line is (more) accurate, lower line is IITC default, portal should be below both

even with zoom=17 the portal looks like it is above the IITC line
(plz note that the visual image is not only affected by zoom but it's one main factor)

[McBen]

This bug bubbles up every year:

I would suggest to decrease

ingress-intel-total-conversion/core/external/L.Geodesic.js

Line 87 in f979fe2

segmentsCoeff: 5000

down to 1000.

I'm (now) pretty sure modern system will handle well a little increase in line-drawing calls.

[Artoria2e5]

I believe we should go back to johnd0e's suggestion: just take into account dLat, not just dLng. In fact, I believe I can PR it now!