Opened 3 months ago

Closed 3 months ago

great circle arcs (orthodromy)

Reported by: Owned by: verdyp@… team normal Plugin

Description

For now JOSM has tools to draw circles and straight lines, these are fine, but only for small distances or along the equator:

• Except along the equator, loxodromies are in fact spirals converging two the two poles with the same angle relative to the North.
• "straight lines" are in fact loxodomies, but they are not the shortest route between two nodes. They just appear to be "straight" on a Mercator projection (like the default WGS84 projection used in JOSM), because this preserves angles, but not distances (real distances along a parallel with the same longitudinal angle difference are getting smaller when you escape away from the equator). So the "circles" in JOSM are not real circles: if you center the circle anywhere else then on the Equator in the Northern Hemsipere, the "radius" to the south is in fact smaller than the radius to the north, objects will be significantly distorted if your objects span a large enough difference of latitude (more than 1 degree).

We need another geometric "primitive" for large objects, notably routes, but also some legal definitions of maritime borders, that use "orthodromies" (i.e. effective distance along a great circle) and not "loxodromies", even if in a Mercator project they will show as smooth curves.

Lowodromies and orthodromies between two arbitrary nodes are equivalent if they are *both* on the Equator, or *both* on the same meridian. In all other cases, they are different, and "straight lines" are not the shortest routes (this also affects precise measurement of long distances in JOSM): to limit the error, we need to be able to add more nodes to represent these curves (JOSM warns us for straight loxodromic arcs betwee ntwo nodes that are longer than 10 kilometers, i.e. about 5 minutes of longitude, but the deviation error from the real great circle arc to the loxodromic arc can reach up to 1 minute measured orthograonally, i.e. about 700 meters, in the middle of the arc; this is not precise enough for some circonstances; the error depends on the angulare cape between the two nodes and the latitude difference).

Is there a plugin or integrated tool to approximate orthodromic routes between to nodes, by adding enough nodes so the deviation angle along all nodes of the generated polyline goes below 0.1 degree, or the deviation distance betwween loxodromy and orthodromy goes below a given precision (e.g. 10 meters) ?

For now, these orthodromic arcs have been drawn with incorrect estimations (e.g. incorrect radius for territorial waters, computed from a simple loxodromic distance) or based on external maps (such as WPS maps) where these arcs were computed by someone else ?

Note that we could compute routes externally and then import the generated ways.

Finally, how are distances really measured in JOSM ? I suppose that what is displayed is just a loxodromic distnace, but I really suspect these distances are incorrect estimations of real distances (even if we ignore the effect of altitude and relief, and suppose that all is measured on the projection sphere and not the real ground).

comment:1 in reply to:  description Changed 3 months ago by taylor.smock

Finally, how are distances really measured in JOSM ? I suppose that what is displayed is just a loxodromic distnace, but I really suspect these distances are incorrect estimations of real distances (even if we ignore the effect of altitude and relief, and suppose that all is measured on the projection sphere and not the real ground).

There are a couple of methods used.

The two primary methods are LatLon.greatCircleDistance and Coordinate.distance. For example, Geometry.getDistance uses `greatCircleDistance` for nodes. Also, the Way.getLength method also uses `greatCircleDistance`. This is what is (usually) displayed as the way length in the bottom JOSM toolbar.

I don't know if JOSM curves lines to match the `greatCircleDistance` formula. I doubt it, since I suspect it would probably affect performance significantly (instead of straight lines, you are drawing curved lines, with the associated calculation costs for the parabola).

Someone else with more experience in JOSM's map renderer could probably chime in for your other questions.

comment:2 Changed 3 months ago by stoecker

Please explain your rationale. JOSM cannot define new ways to draw a line. This would be the task of OSM API and I doubt someone will introduce new API functions for VERY LONG lines.

comment:3 Changed 3 months ago by anonymous

I wrote it explicitly: "Is there a plugin or integrated tool..."
There are clearly missing tools to help draw *accurately* other kinds of ways (accurately means with a known measurable maximum deviation matching the local need: if we want decametric precision on the map because there are other nearly objects in the 10 meters band, and want to clearly make them appear on the correct side, the drawn lines should be drawable, or rectifiable with that precision in mind.

But many sources only focus on specific types of objects whose precision is sufficient inside this limited datasource, but insufficient when we have to merge them and integrate them with other data (this is a topologial problem: is some other object inside or outside another, the precision of lines does matter, a datasource may provide a geometry with one node every a few kilometers which is insufficient for integrating other sources of whan matching them with an imagery).

As the intent of OSM is to draw a map with decimetric precision (in dense areas where there are many items: buildings, trees, roads, kerbs, signals, waste baskets, lighting...) it becomes important to fix the topological problem caused by insufficient geometric precision even if this is the precision given by a specific source for a more limited dataset fused only on specific objects. But those sources already specify that these nodes are defined in terms of loxodromy or orthodromies, as well roads are never polygonal, curves are actually smoothed.

But the OSM geometry is polygonal and implicitly ALL these "polylines" have an inaccuracy proportional directly to the length of *each* line segment and to the sine of the deviation angle at each node (but no way in OSM to indicate that a node is a real angle or is smoothable).

There's still no primitive allowing at least quadratic or cubic curves (OSM still has no concept distinguishing exact nodes and directional nodes like for Bezier: a single boolean flag per node would allow it, by allowing distinctiuons between "exact" nodes and control nodes: a polyline would be valid if it starts and ends by an exact node, and has at at most 1 or 2 control nodes to define positions that the curves does NOT pass through. Using cubic or Quadratic Bezier primitives would dramatically reduce the number of nodes we need to add in the geometry of many long ways. They could make a significant difference between a loxodromy and an orthodromy.

They could even better match common curves like circles and ellipse, even if circles are not exactly the same as cubic or quadratic, a circle is accurate enough if it's approximated in practice at all scales by 6 cubic Bezier arcs (18 nodes, one of them being referenced twice at start and end of the line) or 9 quadratic Bezier arcs (18 nodes as well), and with higher precision than with a 18-node polygon.

It's a common need to allow drawing better geometries. Given that OSM still only has polygonal lines, what we need is extra tools allowing to add extra intermediate nodes to match the desired geometry, but there's no such tool for now: they are added inaccurately manually, eiother there are too many of them, or not enough. And the intermediate nodes added never indicate why they were added and don't have any flag indicating they could be freeely moved along the curve if one needs to add more intermediate nodes).

I just hope that one day the OSM polylines will not jsut have "<node>" members in ways but also "<controlnode>" so that we can finally define smooth ways wiuthout having to add so many intermediate nodes. If we only have "<node>", then we need drawing tools; and additional tagging to explicit how they were computed if we need more: defined by a Bezier, by an alignment with other nodes or as the interection of two ways, or at some known distance from another node (these are geometric constraints that are lost for now).

This is also important when rendering OSM at large scales, because there's no clear indication about which nodes can be elimiated to "simplify" the geometry when drawing shapes on a very large area containing many more shapes.

There are some renderers that attempt to infer smoothed lines for roads, but the result is disastrous. And the OSM geometry at low scales are also very poor if only "straight segments" are used, as this will show arbitray angles everywhere that does not even match the reality (and there's no real indication of the polygonal stroke precision, which is only best approximated by the product of segment length at each vertice and the sine of the angular deviation.

So how to define good geometries that work at all scales (including for 3D rendering or for rendering with other projections than Mercator, including 3D rendering like street views 1 meter above ground and in automotive navigation)?

We do need better geometric primitives (circular arcs are not really needed, adding only quadratic and cubic Bezier, using only 1 or 2 "control nodes" between pairs of existing "nodes" would be enough; even if this is not defined in OSM, I do not see why such primitive, could not exist in JOSM i.e. adding only "control nodes" as a new type and allowsing their presence as members of "ways", plus an optional a metatag of the way indicating the desired precision: here again its default would be proportional to the length of segments between nodes for straight segments or between nodes and control nodes for surved segments, and to the absolute sine of the angular deviation).

The polygonal lines are insufficient. But it would cost too much in the OSM database if we forced every way to define 1 node every 10 meters (for now OSM tries to enforce at least 1 node every 10 km, this is very poor for a map that should reach decimetric precision and matching the imagery we can have now, and insufficiant for dense areas with many objects: a disc with 10 km radius is an extremely large area).

These new primitives (supported by drawing tools) would be helpful to convert existing polygonal geometries into an intermediate polycurve that can be adjusted, and then regenerated as a polyline into OSM (with automatic regeneration of the intermediate nodes). And with these, we could finally have tools allowing easy and accurate drawing of orthodromies, cicles, roads, and so on, and with just enough nodes to match the intended precision and the local needs (some geometric constraints of the defining curve could be saved to OSM as additional "meta" tags of ways or their nodes).

And in JOSM, this integration is not necessarily inside the core but could be done via plugins. Without plugins, we have to use external geometric tools that will regenerate the polylines to reimport...

comment:4 Changed 3 months ago by anonymous

Note that the need for smoothed curves is already standard in other vectorial graphic formats: SVG, PDF, PostScript, OpenType... They are very simple to represent. They just need something other than basic "nodes" at absolute position: only "control nodes" are needed, as very few validation rules:

• there can be only 1 or 2 "control nodes" between "absolute nodes" if we limit us to cubic Bezier
• a "way" can only start/end by an absolute node
• ways can only intersect on an absolute node (control nodes and absolute nodes should NOT be merged, and control nodes of distinct ways are also not mergeable, eahj of them is attached to a single way referencing it, so control nodes do not even need any OSM "id", they are only part of the way definition)
• control nodes should probably have no tags at all in OSM.

And finally the conversion of such OSM-based extended "polycurve" primitive to SVG or other vectorial formats would become accurate at all scales. And the size of the OSM database would be dramatically smaller. We could manage the shape accuracy to what we need without having to import so many OSM nodes.

comment:5 Changed 3 months ago by stoecker

Sorry, but your texts are much too long and I wont read them. If you can't explain your rationale in a few sentences it does not seems worth bothering with this ticket. Please keep in mind JOSM is an OSM editor, not a drawing tool.

comment:6 Changed 3 months ago by verdyp@…

drawing tools are part of JOSM, but they are too basic given the existing geographic practices.
I do not ask them to be integrated by default in core, but there should be plugins to help compute the geometry. And for now I've not seen any one managing the common "orthodromy" curves. The existing tools are made only for very local edits of small objects.
And anyway there's still a need to better handle smoothed curves without assuming than all nodes have equal values and are all implying an infinite curvature at each vertice (like it is with polygonal-only nodes).
even if there's still no "control node" primitive in OSM, we could still use its existing "nodes" with additional tags distinguishing nodes that were added to approximate curves, plus nodes that were added only as control nodes (usable as normal nodes for polygonal rendering only for compatiblity with simple renderers). This just requires two additional boolean tags. And with suchg information was can infer esily how to derive more nodes if needed (for rendering at high zoom levels), or how to simplify the geometry of complex polylines (for low zoom level), without breaking the topology (e.g. correctly infer what is on the right or left of the curve, or what is inside or outside an area.
two bits of information that could be modeled as tags on OSM nodes such as:

• "curve:control=yes" for control nodes (not necessarily "on" curves), default is "curve:control=no" for normal nodes (should not be on intersection nodes, but only on non-terminal nodes of a way; if this ever occurs on a node used by more than 1 way, ignore/discard it handle it as with the default "curve:control=no")
• "curve:added=yes" for generated or manually added intermediate nodes (may be on both normal nodes or control nodes added automatically, for example by a curve computing tool that would approximate a well defined parametric curve like a circle or orthodromy, by splitting it in several quadratic or cubic arcs, joined together in a the same way or between two ways of a relation by normal nodes on curve)

Now with this, we can safely model various curves, and renderers have enough info to generate accurate smooth curves without needing so many nodes. The only validation is that such curve definition in the same way is usable if

• there are no control nodes used by more than two ways not connecting the same neighbouring nodes, and no control node at both ends of ways (otherwise treat them as normal nodes)
• beside debugging tags these control nodes should have no other semantic tags (e.g. names, or feature types), otherwise treat the node as a normal nodes
• there are no more than two control nodes between two normal nodes (so that was can infer a quadratic or cubic Bezier spline between the two normal nodes), otherwise treat the nodes as normal nodes (this will then render a polygonal line with non-smooth angles: there may be a missing normal node to recreate between them)

Then geometric drawing tools can be made to compute extra nodes ("curve:added=yes"): normal nodes (for splitting a curve into multiple arcs in order to reach a desired precision) or control nodes with "curve:control:yes". And some of these types of curve drawing tools would obviously be: circular or elliptical arcs (approximated by multiple bezier), or a single Bezier arc, or classic orthodromic arcs used in navigation and in some legal texts (may be we could record the type of curve by adding "curve:*" tags on ways generated with these annotated nodes). The default remains the "straight segment" (which is only "straight" in the editor Mercator view, but has limitations where JOSM signals overlong segments which are always inaccurate over 10 km, including loxodromies because of the non-linear exponential deformation of the latitutes axis in the default "Google Mercator" projection: see the extreme distortion of distances along meridians that occur when you approach the poles, where this projection is unusable, even if it preserves angles relative to the geographic north axis; and as the coordinates in WGS84 are in fact polar, the needed numeric precision for angles in fact decreases and we actually don't need so many nodes compared to the area near the Equator when our intend is just to build a map with an accurate precision in real distances, not in terms of real polar angles in degrees).

Many curves in OSM could then be modeled in OSM with much less nodes, with this extension to support quadratic and cubic Bezier splines (which are very easy to compute and fast to render, ans supported also by standard graphic APIs hardwares). And globally we'll have more accurate definitions of ways without the costs of adding so many nodes in the OSM database to improve their accuracy (Bezier splines are effectively extensively used in many applications using complex geometries without needing so much data).

But I think that OSM's curent definition of nodes is too costly, control nodes or added/generated nodes have unnecessary info (notably unique id's, not necessary as most nodes are used by a single way only as intermediate nodes to approximate curves): adding such new primitive (instead of tagging normal <node> elements with special tags like above) would require change in the OSM API and model. There's however no need to change the tagging model for ways and relations (only ways could contain not just normal unique selectable <node> but as well unindexed and untagged nodes and control nodes: it would be up to OSM editors to convert them to normal unique selectable nodes only when they need to split ways or create intersections at specific positions, or to annotate a specific position on the curve with OSM tags).

As long as the OSM model is not change, we still need tools to help generating correct curves that correctly match their actual definition. These can be for now external tools, or integrated plugins for JOSM (or other OSM editors). May be this is not done in JOSM, but for large objects (over 100 meters in diameter the decimetric precision is lost, and we already have ortho-imagery data offering centimetric precision per pixel, and we already ambiguities to determine which objects are to the left or right of a border, no correct estimation of their relative distances to these ways, no clear indication of their correct alignment, for example with navigation beacons, or for legal purposes: "who" owns or administrates "what"?)

So once again I repeat the initial question about missing drawing tools and lack of manageability of the precision for map data in OSM. (this is not just in JOSM but for OSM in general, but JOSM is concerned because it offers the possibility of adding plugins, that may later be integrated, and because JOSM also has presets for tags that could be useful to manage the definition of curves and the wanted precision, without loosing this important geometric information)

comment:7 Changed 3 months ago by stoecker

Resolution: → wontfix new → closed

Modify Ticket

Change Properties