Skip to content
This repository has been archived by the owner on Jul 24, 2021. It is now read-only.

Clockwiseness detection broken #970

Closed
openstreetmap-trac opened this issue Jul 23, 2021 · 6 comments
Closed

Clockwiseness detection broken #970

openstreetmap-trac opened this issue Jul 23, 2021 · 6 comments

Comments

@openstreetmap-trac
Copy link

Reporter: richard
[Submitted to the original trac issue database at 10.34am, Wednesday, 11th June 2008]

http://www.openstreetmap.org/edit?lat=51.70607&lon=-1.31916&zoom=17

Way 24777545 (outer part of polygon)

Clicking to reverse it doesn't appear to change the direction.

@openstreetmap-trac
Copy link
Author

Author: chriscf
[Added to the original trac issue at 10.01am, Tuesday, 16th September 2008]

Still there in 0.10b. Not so much detection, with some ways the direction is changed and gets stuck that way. See way 26435355 - http://www.openstreetmap.org/edit?lat=51.46587&lon=-3.16336&zoom=17 - selecting this way and retagging it (e.g. changing the name) results in the way being reversed from clockwise to anticlockwise.

@openstreetmap-trac
Copy link
Author

Author: jonathan.dickinson[at]k2.com
[Added to the original trac issue at 9.22am, Thursday, 2nd October 2008]

Maybe you could pull it out for now. I certainly wouldn't mind changing the direction of each line in the way.

@openstreetmap-trac
Copy link
Author

Author: osm[at]randomjunk.co.uk
[Added to the original trac issue at 1.49pm, Thursday, 2nd October 2008]

It fails when the lowest, rightmost point is the first (and last) point in the polygon. This is because the algorithm on geometryalgorithms.com is expecting a polygon where V[n]=V[0], and it cleverly ignores point V[n]. What we have in OSM is a polygon such that V[n-1]=V[0] (V[n] is array index out of bounds), and you don't ignore V[n-1].

This difference means that the onLeft function will pick a degenerate case if it's node 0 that's lowest. ie: it picks nodes n-1, 0, 1 to do the calculation, except that n-1 == 0 (it's the same node), which means it always returns 0 (on the line, but which gets interpreted as anticlockwise).
Actually, the OSM data model allows two nodes on the same location, and also a way to have the same node twice in a row, so you have to handle these cases anyway.

The Fix

  • Proper & Complete: Change onLeft to make sure it's picking three points in different locations. ie: keep going round the path till you find a different one... don't forget to escape if you get back to where you started without finding one.

  • Quick: Change onLeft to go round an extra node on the join. ie:

    var left = 0;
    if ( this.path.length >= 3 ) {
        var i=j-1; if (i==-1) { i=this.path.length-2; }
        var k=j+1; if (k==this.path.length) { k=1; }
        left = ((this.path[j].x....
    }
    return left;

Quick note: it's actually impossible for k==this.path.length given how onLeft is called... but we don't know who called onLeft so I've left it.

@openstreetmap-trac
Copy link
Author

Author: osm[at]randomjunk.co.uk
[Added to the original trac issue at 1.53pm, Thursday, 2nd October 2008]

  • Proper & Complete: Change onLeft to make sure it's picking three points in different locations. ie: keep going round the path till you find a different one... don't forget to escape if you get back to where you started without finding one.

Actually these are degenerate polygons anyway, and we're not promising to cope with those... it's just a special case of self-intersection. Might as well do the quick method.

@openstreetmap-trac
Copy link
Author

Author: Richard
[Added to the original trac issue at 1.55pm, Thursday, 2nd October 2008]

/me applauds

Utterly brilliant. Thank you.

@openstreetmap-trac
Copy link
Author

Author: Richard
[Added to the original trac issue at 11.32pm, Saturday, 4th October 2008]

Fixed in 0.10d.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

1 participant