relations with rings intersecting on isolated nodes (the "intersection" is incorrectly signaled)

[verdyp@…]

this is an old bug in JOSM validator (see the snapshot)

Relations with this example form:

  A                    B
  +---------------------+
  |                     |
  |                     |
  |                     |
  |                     | C
  +---------------------+------------------+ E
  D                     |                  |
                        |                  |
                        |                  |
                        |                  |
                      G +------------------+ F

are correctly represented with a multipolygon or boundary relation having the following "outer" member ways (note the direction of drawingf each way does not matter, they can be inverted):

• 1st ring:
  • A to B
  • B to C
  • C to D
  • D to A
• 2nd ring:
  • C to E
  • E to F
  • F to G
  • G to C

The problem is that the validator incorrectly reports an intersection, even though the two rings only intersect on an area which as a null area

Another possible representation would be to order them as a single ring (but this is not possible when there are more than one "touching" nodes and no ring can be qualified as "inner" touching the larger outer ring (such case occurs in some un municipalities of Spain and on the bordzer between Belgium and the Netherlands and for one municipality in the suburbs of Paris, it also occurs for other kind of objects like landuse=* but this warning can be solved by creating separate relations; something impossible to satisfy for administrative borders that cannot be splitted this way), but this situation is not recommended and in fact impossible to satisfy everywhere (e.g. the NE and SW rectangles in the shcema above also belong to the same area modeled in other OSM relation: it's impossibler to decide that the intersection node belongs to one surface or another, it belongs to both).

• single ring:
  • A to B
  • B to C
  • C to E
  • E to F
  • F to G
  • G to C
  • C to D
  • D to A

(this doesnot change at all the number of members, only their relative order in the relation, but order of ways in multipolygons and borders in normally not significant)

A real intersection should be signaled if the intersections of rings on one node (explicitly drawn or not with a node object in OSM) do not cross each other, notably if a valid ring can be connected while keeping all other rings on the same side, even if they have a common node.

So it is valid for a relation to have positions on rings connected to more than 2 ways, but any intersection should be at an isolated node, and the relation is valid *if and only if*:

• all ways connected to that node are starting/ending on that node,
• the number of ways starting/ending to that node is *even* (2, 4, 6...),
• and the ways do not intererect anywhere else in the middle, i.e. the segments are starting or ending in different angular directions and not colinear (some ways may still intersect on multiple distinct isolated nodes, all of theses nodes being terminal in these ways).
• and there's no other intersection anywhere else (no colinear pair of segments), no pair of non-colinear segments interecting inside or at end of another (if this ever happens on a single closed way, that closed way should be transformed into a relation, and satisfying rings should be determined, by splitting this way and from any pair of colinear segments the common parts with non-zero length, possibly by splitting these segments on the nodes terminating the common parts, so this should be signaled by the validator)

For now (and since long in JOSM) the detection of "self-intersection" is wrong and gives false positive detections.

[anonymous]

example of valid area with rings touching on an isoalted node, but incorrectly reported as by the JOSM validator

[GerdP]

Yes, seems to be a false positive. My understanding of the wiki was that touching outer are not allowed, only touching inner.
My new understanding: One or more touching node are allowed, only shared segments are not allowed.

[anonymous]

There are similar sitatuations like this one where it is impossible to avoid the incorrect report of "self-intersection" (this situation is real, see the municipality of "L'Isle-Adam" in the Paris suburbs):

      +-------------------------------------------+
      |                                           |
      |               (inside)                    |
      |                                           |
   A  +--------------------------+                |
     / \                         |                |
    /   \       (outside)        |                |
   /     \                       |                |
  /       \                      |                |
 /         \                     |                |
+           +                    |                |
| (inside)  |                    |                |
|           |                    |                |
+           +                    |                |
 \         /                     |                |
  \       /                      |                |
   \     /                       |                |
    \   /       (outside)        |                |
     \ /                         |                |
   B  +--------------------------+                |
      |                                           |
      |               (inside)                    |
      |                                           |
      +-------------------------------------------+

This can be modeled either as:
 - the largest ring modeled with "outer" role, containing the smallest ring (lunar shape here) with role "inner", both rings touching at two separate isolated nodes A and B; or 
 - two rings (the lenticular one on the left, and the large lunar one to the right), both rings touching at the same two separate isolated nodes A and B

Both models are geometrically valid, it's not geometrically possible to say if the two ways forming the central lunar area are both "inner" or "outer" roles.

But in all cases, if you look at the roles of ways connected to A (or to B) ordered in a clockwise (or anticlockwise) circle, there are an even number of ways, and successive ways must form pairs with the same role ("inner" or "outer") (you cannot have an odd number of a ways with given role between two ways with the opposite role).

[GerdP]

The message produced for this case is informational. Do you see something different?

[GerdP]

Ah, sorry, tried a different case. Your screen shot shows an invalid case.
The wiki says "Exactly two unclosed ways, and no more should share an endpoint"
The node 576722000 is the end point of 4 ways.

[verdyp@…]

Finally, another situation occurs when one of the touching rings is formed by a single self-closed way: that way should start and end on the same node, and that node should be the isolated intersection point with other rings:

• you can (and must) ignore that way when counting ways around an intersection point to make sure that all other ways around that node are in an even number (it may be 0 when all touching rings are self-closed ways!), and their "inner" (or "outer" roles) match by sucessive pairs (the role can, but must not, change only between pairs of ways after discarding self-closed ways)
• if a self-closed way forming a closed ring has been split in two parts, the parts should have the interesection point defined as one of the terminal nodes (there will be another splitting point on that, and then you'll still have an even pair of ways connected to that node!).

Such case involcing self-closed ways also occurs (as shown in the attached screenshot above)

[anonymous]

I see that reported as a "warning" ("avertissement" in French) see the screenshot.
But if this bug was corrected, such thing about self-intersevtions should no longer be a "warning" but an "error" that needs to be corrected (we should not accept colinear segments with length>0 and not accept other intersections of rings with surface>0)

[GerdP]

See comment:4

[GerdP]

Thanks for your report, however your ticket is incomplete and therefore not helpful in its current form.

Please add all needed information according to this list:

• The required parts of the Status Report from your JOSM.
  • Please, use Report Bug from Help menu and copy & paste.
• Describe what behaviour you expected.
• Describe what did happen instead.
• Describe if and how the issue is reproducible.
• Add any relevant information like error messages or screenshots.

To ensure that all technical relevant information is contained, create new tickets by clicking in JOSMs Main Menu on Help → Report Bug.

Remember: This is a generic notice so we don't need to write the same stuff again and again. It may only apply in parts to the specific case!

How about a step by step description and attaching a small OSM data file to reproduce ?
And make it short, please.

[anonymous]

other examples with self touching rings deteted in Spain

[anonymous]

@GerdP. my report is accurate and all the info needed is contained in the examples and screenshots. I have fully discribed the situation and what is currently (incorrectly) reported by the validator in JOSM.
There's no need at all of ANY status report, you can reproduce it immediately from the existintg OSM data (look at the reported relation numbers).
I also gave an accurate algorithmic solution for that.
I posted also a shema to better explain and reduce the problem and its solution.

Please read more carefully before such unuseful response, if you don't understand things just ask, but it is easy to reproduce immediately (with ALL version of JOSM since long). I think however that you don't want to read anything, and focus just on simple bugs that are easy to explain and solve. Here this is something that is not obvious (and not correctly documented and explained in the OSM wiki and documentation, and frequently incorrectly implemented in applications, including in some rederers, but not all; the OSM Carto renderer is not affected by this bug, and correctly accepts this as valid data).

[anonymous]

Also it is correctly summarized in the title of this bug report.

[GerdP]

You report doesn't say what's expected. Do you want an error message instead of the warning or do you think that the warning is a false positive?

[anonymous]

Note also that ithis is not a bug of OSM database design, it also does not affect other GIS softwares, these situations are correctly handled in GIS extensions for PostGreSQL. So this is specificalklky for the JOSM validator whgich does not handle them correctly.

My report says "incorrectly signaled" in its title. Wo what is expected is obvious: there should not be any such (false positive) signal.

[anonymous]

And you're wrong, that node is CORRECTLY connected to 4 ways, from which it is one of their endpoint !
This is absolutely not a data error, but really a false signal reported by JOSM because it forgets to handle the case correctly.
The same is true for the other examples found in relations shown in the next screenshot. In all cases, JOSM is wrong.

[GerdP]

sample for invalid boundary Boundary relation 343670 has 4 ways ending at the same node

[GerdP]

For the attached file there is a warning "Self-intersecting polygon ring"
I would agree to change that to an error message "More than two unclosed ways share the same end node"

[anonymous]

you can look at also at what happens:

• along the Belgium-Netherlands border between the municipalities of Baarle-Nassau and Barrle-Hertog

These are real examples of "patchworked" boundaries with touching rings (and no clear determination for the "inner" or "outer" roles to give to ways, but a clear determination of what is inside or outside the rings for each municipality, and no way to split their touching node into several ones to create areas around them that would become incorrectly separating holes in all of them, or wrong superpositions of small areas incorrectly belonging to both; the touching nodes are connecting the subareas, there's no disconnection and you can pass from one area to another without leaving the city, even if you pass by a bordering node which also belongs to the other city).

Boundaries are almost never convex, they are concave almost everywhere. "Convexity" is not the appropriate axis to anaylize. All that matters is "connexity". And a boundary can be fully connex without necessarily having a single ring and still without any hole forming an enclave in their inner area. For such cases, it is impossible to say if successive pairs of ways are both "inner" or both "outer". All that can be said is that they can only have the same role in the same pair (after excluding self-closed ways which are paired with themselves on the same intersection node).

And you're still wrong, relation 343670 is entirely correct and cannot be represented by another mean (reordering ways in the relation has no effect, merging/splitting ways has no effect, changing their drawing direction has no effect, in all attempts, JOSM will still signal this).

There are really 4 ways at the same ending node and this is definitely NOT an error ! These ways may form self-intersecting rings (when computing rings from them, but only if you don't correctly order ways with the same role around such node in a circular order)
It is valid in iD, in PostGIS after imports, valid for the OSM Carto renderer.

[GerdP]

So you think that the wiki is wrong when it says "Exactly two unclosed ways, and no more should share an endpoint"?

[anonymous]

And for more related information about this, you may look at the specifications of the "even-odd" fill rule in SVG. All is about parity check but on isolated nodes this is valid.
The OSM wiki is not explaining things clearly. What is correct is what is documented in other GIS references (and after all the OS Mdata will be converted to other standard GIS format: look at PostGIS specifications.

[GerdP]

@Klumbumbus: What do you think? I would not want to change the test code as long as the wiki clearly states that the multipolygon is wrong.
​https://wiki.openstreetmap.org/wiki/Relation:multipolygon
Or maybe type=boundary is a special case here?

[anonymous]

You'll note that such difficulty is not encountered in other GIS formats, because they never break rings in their multipoygons. But OSM represents multipolygons by an unordered collection of ways, and rings and only infered later, using the *implicit* "even-odd" fill rule (the same as in SVG): the roles for member ways is nor even needed to do that, but can be used only after generating such rings, because rings really have an inner and ouoter role, which can then be compared to what is OSM...

But the generation of rings from an unordered collection of ways rtaced in arbitrary direction in OSM does not necessarily give a unique result (there are multiple sets of rings in some case, all these being equally valid in GIS, which also requires in stadnard GIS that these rings be correctly oriented (clockwise or anticlockwise) depending if they are inner or outer).

Take for example an area shaped like an 8: it is valid in standard GIS, only if it is drawn by *not* crossing the border line through the medial intersection point (not the way you usually draw the 8 digit with a pen), but by "rebounding" on it; in OSM, this has to be infered, and on the intersection point, you'll count 4 segments ending on that node). The roles given to ways in OSM are not used for the generation they are informative for contributors, or useful as a "hint" only in the case a relation is partly broken and must be repaired. The role happens to be checked as well during the export and conversion from OSM to GIS.

This is a difficulty that is solved during the export of OSM data to a GIS database (this is made by common export/conversion tools, that have no other choice than using the "even-odd fill rule", because it has to lookup for candidate rings, fond intersection points, order segments connected to these intersection points in a circular order, then group them by successive pairs: on each node you can have two groupings by pair possible, but for the whole relation, there should remain only one; then OSM ways in the pairs, must have the same role in OSM, closed ways may have any role but must be between other pairs or open ways or next to another closed way when you lookup for all ways connected to the same node in circular order.)

[anonymous]

This case is not treated at all in the wiki OSM page for multipolygon relations. It has been forgotten.
But it is discussed in other pages showing more complex cases (which do happen!) where the OSM model is ambiguous and requires specific analysis during the data export and conversion from OSM to GIS, and the validator in editors should use the same "even-odd" rule which is implicit in OSM data.
To limit the ambifguyity and provide hints to users contributing to it, the roles "inner" and "outer" were added in OSM, but are not needed at all in standard GIS data, because rings are always explicitly closed there (but even in stadard GIS, the closed rings can still touch each other at isolated nodes only (not along segments with length > 0 and not around areas with surface>0).

Things would have been simpler in OSM if relations for multipolygons/boundaries required:

• member ways to be grouped ring by ring (or an extra member was added to separate rings made of multiple unlosed ways.
• ways in the same rings to be ordered (consistantly like in GIS, in anticlockwise direction for outer rings, or clockwise direction for inner rings, but this is not possible to require a direction because ways have dual roles depending on which relation reference them, so exports to GIS have to infer these directions, but at least OSM could have required groups of ways in the same ring to be fully connected in sequence from the first one to the last one of the group and back to the 1st one)

In some cases, even the consistant grouping and ordering of member ways cannot determine if there's one or two rings (this is the case for the 8-shaped area: it can be a single outer ring with a rebound on the intersection node, or two separate outer rings having a common node ; but in both cases, you still have 4 member ways in the relation connected to that node; if there are only two rings in the relation, there's no separation between groups, OSM does not encode if there uis one ot two rings intended, so the OSM to GIS expprt will also have to guess: it will have no other choice than using the even-odd rule, and can create one or two rings, with equivalent results with this even-odd rule)

[anonymous]

The case is the same as well for multipolygons (we cannot always create separate multipoygons if we need to represent and tag the whole group). For example: forests, lagoons, atolls, industrial and commercial areas which sometimes are made fully connex only by a few isolated joining nodes like a crossroad which is also in the middle of a residential area that this node also interconnects, without clear separation or attribution of the crossroad (and its immediate surrounding) to one area or the other. This also happens with areas of restrictions which have invisible boundaries but are not real boundaries and are represented by multipolygons, and as well for areas defined by fuzzy border ways.

Boundaries are not special. The only difference is that they also allow a few additional members for admin_centre, label, subareas and other kind of relations specific for some admin types or to create different parallel hierarchies of subdivisions, but I've seen also labels and central nodes added to some multipolygons in OSM (generally because some inner subareas were still not defined with their border ways). Another minor difference which plays no geometric role) is the fact that boundaries are formal and come from a reference authority without any immediate consequence on the ground, and are stable over time, whilst multipolygons generally are not and are rather based by what is visible and evolutive on the ground (multipolygons are subject to local interpretations). So complex multipolygons frequently can be subdivided into separate ones (even touching ones) quite arbitrarily (this is normally not the case for boundaries that must then keep their geometric complexity unbroken according to what they designate: only one boundary <=> only one relation).

[anonymous]

Also look at the end of talk page ​https://wiki.openstreetmap.org/wiki/Talk:Relation:multipolygon#Multipolygons_with_an_outer_ring_and_inner_rings_which_touch_it

For usual polygons, you can often avoid this difficulty by create separate multipolygons (as many as you have outer rings, then all other rings in the multipolygon will be inner, and all their members can be listed at end of the member list after all outer ways that form a single outer ring).

But this does not work for boundaries that do have and do need multiple outer rings that are unseparatable

An in some cases, you cannot split a multipolygon as this would create separate objects which are noramlly only designed as an unbroken group (isolated parts have other designations). Take the example of archipelagoes, it makes no sense to split an archepelago and designate it island by island, when each island also has its own local name (and in some cases the islands are touching each other by one interesection node (there may also be a bridge passing over it, or there may be an area of land discovered at low tide and joining multiple islands, but it's not always evident to delimit an area of land around the connection point to add to one of the islands or to the arhipelago, when that area is also subject to tide and should be maritime in OSM, still there's a permanent link between the two conencted islands which may be secured by a built bridge).

The same occurs for natural reserves, national parks, cultivated fields, inhabited areas, floodable areas along rivers, riverbeds passing though a narrow tunnel not representable precisely, but you don't want to break the whole area covered by the riverbed of the same single rive, beaches connected at a single node at the tip of a rocky cape or a dike (and you don't want to add a common way where they would be touching, notably beaches separated by this dike as an uncrossable barrier...

Standard GIS formats don't have these dificulties at all, they only represent full rings, they don't split ways and don't reuse them (also they don't even reuse the nodes, there's no merging, no integration like what OSM requires, no conflation is needed, all objects are geometrically independant and have independant sources and independant precision from their source authority, the goals are radically different).

[Klumbumbus]

Replying to GerdP:

@Klumbumbus: What do you think? I would not want to change the test code as long as the wiki clearly states that the multipolygon is wrong.
​https://wiki.openstreetmap.org/wiki/Relation:multipolygon
Or maybe type=boundary is a special case here?

My opinion: If the wiki is "wrong" it should really be discussed somewhere else, not here in the JOSM bug tracker. After a consensus is found the wiki can be corrected and then JOSM adapted accordingly. No objection to reword warning texts.

[anonymous]

The wiki is not wrong, the case of interesection by isolted nodes is not documented, but is really needed and in fact well supported by all existing tools.
Only JOSM complains that they are errors, when these are not at all documented as errors/invalid cases. Those cases are real and are impossible to represent with the rules that JOSM invented to enforce them... The only thing that can be done is to ignore these false positive reports of JOSM, so this validation in JOSM has absolutely no utility, it is just a nuisance.

[anonymous]

Other competing QA tools do not report these cases are errors. All the main renderers support these cases without any problems (yes there are minor renderers that perform incorrect checks but they are very specialized with limited goals and not intended to generate a complete map).

[GerdP]

The attached small patch changes the algorithm that assembles the polygon rings to stop adding ways to one ring when the ring is closed. This only helps when the order of the members is "correct" and it doesn't fix the displayed rings in the relation editior as this uses a different algo. I think it is an acceptable compromise as complete solution would be comlex, possibly slow and unstable.
Work in progress (a unit test will complain because it expects the old behaviour).

[anonymous]

note that you can safely test that intersection points are shared as terminal endpoints by an *even* number of ways (otherwise rings would not be closed).

Rings that intersect on points that are not in data as terminal nodes should still be signaled because they will create areas with surface>0. Rings that intersect only on nodes which have an even number of connected ways are still resolved using the even-odd rule (and if there are only two rings, one of them should be "inner", the other will be "outer"; if there are three rings, i.e. 6 ways, one is unabiguously "outer", another is unambiguously "inner", the third one is ambiguous as it is both, but the pair of ways that make it should have both the same role, i.e. the list of ways at that node have necessarily an even number of ways with "inner" roles and an even number with "outer" role, plus optionally an even number with the empty role which should however be already signaled by a warning; "inner" and "outer" roles on ways are not significant when there are 3 rings or more on a node, the role is in fact given to rings, and rings should only contain ways with the same role)

Roles on ways are checked and compared in OSM-to-GIS exports when they generate rings, but even if there are incorrect roles they are always ignored because inner/outer roles will be recomputed and assigned for rings as they must determine the standard (anti-)clockwise direction by reordering nodes in each ring to generate a correct GIS geometry for polygons and multipolygons; these exports also detect intersections at positions other than OSM nodes, and will add implicit nodes, they perform other checks when there are missing segments to close them and will also add implicit segments connecting the nodes arbitrarily chosen from the nearest pairs (and will also signal this in their QA report logs); renderers of multipolygons that have not fully loaded the geometry of ways (e.g. the iD or JOSM editors) also do that but silently (this is visible because you can see colored shadows passing along segments where there's still no OSM way detected there, and sometimes the inner/outer direction of the shadow may be wrong with incomplete geometry, until it is fully loaded and all missing ways are added to the data to fill "holes").

So this is not just the validator that performs this algorithm, even the map renderer in JOSM has to do it to determine areas to fill (or to create bordering colored shadow bands when the area to fill between borders would be larger than two bordering bands)... The algoroithm is then already in JOSM... but elsewhere and not the validator itself.

[GerdP]

18861.1.patch implements a new approach to assemble the rings. If more than two open ways share a node the algo tries to find the rightmost way which doesn't go back directly. So, unlike the unpatched version this algo produces multiple rings which don't self-intersect at the shared node.
The new algo involves some trigonometric calculations. For degenarated MP with mutiple overlapping segments rounding errors may produce overlapping rings where a different order would prevent that. I hope we can ignore this.
Performance is equal to old algo.
Still WIP as the relation editor also needs changes:

• Sort relation members should try to use the same or a similar algo
• The displayed rings are calculated with a different algo which cannot yet handle this special case.

[GerdP]

Patch needs more work, the rightmost way is only the best choice when the order of the nodes is clockwise. This doesn't work with the example relation 344613.

[GerdP]

I think I give up with the idea that I should change the algo which assembles the rings . The rules following the "*if and only if*" in the ticket description don't describe how to assemble the rings when more than open ways are sharing a node, and also the wiki doesn't say that. So, if you have an 8-shaped MP it is not clear if this should be assembled into one or two rings. If one ring is computed the ring might be self-intersecting.
It is not yet clear to me if such an 8-shaped ring should be split or if the validator should ignore it.

[anonymous]

The 8-shaped MP at least must have an explicit intersection point. As long as these points are isolated and have an even number of segments, the even-odd rule will be OK for the conversion from OSM to standard GIS (using only closed rings for all areas) for rendering using the evenodd algorithm (and this algorithm is already used as well in JOSM itself for its own builtin map renderer...)

---

Internally renderers split the multipolygons into a set of convex polygons by breaking it along horizontal axis passing via nodes where there are non horizontal segments (it just has to check iof the other endpoints of the segments are above or below the horizontal cutting line, ordering them by slope (delta-y / delkta-x), there not even ant need of trigonometric functions or to perform any division to compare and order the directions of segments. Then the polygons generated are reduced to just triangles with on horizontal base, or to trapeses, which are extremely easy to fill. This type of algorithm is also used by hardware accelerators (the oblique lateral sides are computed also withour even using any multiplication/division using only additions for increments along one axis or the other.

The result is very precise to the exact pixels and Bresenham uses an accumulator of errors along the slope which also indicates directly a shading ratio for subpixel smoothing (it can be used to compute an alpha value for the color to apply, or can be used for colored RGB subpixels, or both, or can be used for halftoning by masks if there's no alpha channel (e.g. when printing with monochromatic masks, but the volume of ink droplets and their centering in the subpixel grid can be controled, e.g. on inkjet printers). Some hardware contain also similar ccelerations with additive operation only for approximating cubic or quatratic Bezier arcs or circle arcs (for elliptical arcs, there's no simple solution other than splitting it into multiple Bezier arcs as incremental positions of pixels for elliptical arcs would require elliptic integration; for this case the regular grid of pixels is replaced by a grid with a higher precision for subpixels. Generally a factor of 256 subpixels per pixel or multiplying coordinates by 16 or keeping 4 fraction bits for them, is sufficient for rendering with 8-bit color depth per color plane; monochromatic inkjet printers use a factor of 16 subpixels per pixel, or 2 extra bits of fractional precision for the position of pixel for computing the position of droplets and their size/volume of projected ink, which is controled by the electric voltage of the pulse applied on the piezoeleectric crystal of the printing head for precise halftoning masks; in all cases, you never need slow trigonometric functions or slow mumltiplications/divisions in the main loops for each pixel)

[GerdP]

Example to show how the order of members matters with the currently used algo. See how rendering changes when you move e.g. the last member two positions up.

[GerdP]

This chessboard example is a bit clearer compared to the mp-order example. In the mp-order example some ways could or should have role inner. The rendered result changes a lot depending on the order of the members. So, there has to be a rule how members are selected when more than 2 open ways share the same end node.

[anonymous]

The rule is fully described in the SVG specifations, as I said, look at "fill-rule:" for the "even-odd" value. There are lot of references from there about how to do it correctly.
Implementations have the choice:

• either ordering segments around the intersection point in circular order to determine rings
• or (generally for filling the areas) split the area into a set of convex triangular or trapezoidal surfaces with horizontal bases, using an horizontal cutting lines passing through nodes, then look at additional points where all other ways are intersecting to order them, allowing segments above the cutting line to be ordered from right to left, and then the even-odd counting rule determines areas alternating from "inner" and "outer" (When you have the set of triangles and trapezes, you can recombine them into closed rings (not necessarily convex, discarding the extra intersection points that were only created temporarily by the cutting line). For this, you never need any trigonometric function (sin/cos/tg/atan), only linear arithmetic.

[GerdP]

Sorry, still no clue. Please point me to the algorithm that is used in SVG to assemble an unordered set of lines to a set of closed rings. I think this never happens when SVG data is processed, but I am not familiar with SVG.

[GerdP]

In 16115/josm:

see #18861: simplify code, no functional change intended

[anonymous]

The winding rules and even-odd rules are explained for example in
​https://oreillymedia.github.io/Using_SVG/extras/ch06-fill-rule.html

In SVG there's no requirement for clockwise or anticlockwise with the "evenodd" rule, but the direction matters when there are several closed ways and the fillrule is "nonzero"

See also Wikipedia for the evenodd rule (there's a sample but this is not decompsing polygons in convex triangles or trapezes for filling, or for determining rings, it just determines if any point is inside or outside the area defin,ed by the [multi]polygonal shape):

​https://en.wikipedia.org/wiki/Even%E2%80%93odd_rule

Such things also applies to other graphics format, including opentype fonts for their glyphs. This is not something exceptional. It is still quite simple to correctly pair the ways connected to an intersection point. If you have no clue, you can just consider all segments connected are the start of the half of a straight line, and then test with an horizontal cutting line above and below that point to determine at which X coordinate these half-lines are intersecting: this determines the order to apply above the line by growing X-coordinate; follow this list by horizontal segments starting from the intersection node and going forward to higher x-coordinate, then order segments by decreasing x-coordinates of positions where a second horizontal line below that node are crossing the half-lines, terminate the list with horizontal segments going backward: the ways are then ordered circularly and it is easy to pair them (you have to take special care of horizontal segments that pairs must pass through to create triplets instead of pairs).

With that, you have safely determined the rings whose surface of interections is zero, and that are equivalent the evenodd fill rule.

That algorithm can also be used to safely order member ways in relations instead of matching any random pair of connected ways that have a common terminal node by testing only these terminal nodes: when you have done that, there should remain no intersection outside these nodes between other any other pair of ways or between segments in a single way (this should be signaled in the reported tests for all ways, and for all relations containing ways).

[GerdP]

It seems I am too stupid for this. I don't see how the sorting helps with the chessboard example.
I don't want to invent a wheel again, so if you know an open software which solves this problem please post a link to the source.