Opened 11 years ago

Closed 11 years ago

#970 closed defect (fixed)

Clockwiseness detection broken

Reported by: richard Owned by: richard@…
Priority: major Milestone:
Component: potlatch (flash editor) Version:
Keywords: Cc:

Description

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.

Change History (6)

comment:1 Changed 11 years ago by chriscf

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.

comment:2 Changed 11 years ago by jonathan.dickinson@…

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

comment:3 Changed 11 years ago by osm@…

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.

comment:4 in reply to:  3 Changed 11 years ago by osm@…

  • 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.

comment:5 Changed 11 years ago by Richard

/me applauds

Utterly brilliant. Thank you.

comment:6 Changed 11 years ago by Richard

Resolution: fixed
Status: newclosed

Fixed in 0.10d.

Note: See TracTickets for help on using tickets.