Why am I detecting UK relation is inside England relation?

Help and support
1

Hi, I am writing a ray casting algorithm which works well but I am getting an unexpected result that the UK is not all outside of England when it really is. I am visually impaired and hope that someone can give me some sighted help by looking at the geometry of the situation which will explain the odd result. Below are the details.

I am testing if all UK nodes that make up the UK relation 62149 are inside the England relation 58447. I should get an even number from the ray cast algorithm for every single node as they are either all outside or I cater for shared nodes. However, I get 4 nodes out of about 28,000 that give an odd number and hence get classed as inside England.

When I test the UK node 312182514 against England it intersects in 3 places.

Intersection 1: At node 312182520 which is actually the first of a series of nodes all on the same latitude and exactly level with the UK node at 51.593 degrees. My algorithm discards all the other horizontally level nodes. But it looks like the general direction of travel of the way is bottom left to top right.

Intersection 2: A clean intersection between nodes 312182509 and 312182524.

Intersection 3: A clean intersection between nodes 11132397718 and 11132397717

All 3 of these intersections are far off to the east of my UK node.

I believe that all 3 of these intersections are legitimate and the only thing I can think of is that there is a fourth intersection I am not accounting for though why this should be I don’t know.

So, please is anyone able to take a look at this scenario and help explain what might be going on?

The fact I only get 4 incorrect results suggests I can’t be far wrong. I also have success checking out other relations. Hopefully there is something simple going on.

Many thanks for any help,
Chessel

2

correct

correct

This is the source of the problem. The ray casting algorithm requires that a small “epsilon” be added to the y coordinate when testing for intersection with a segment with an endpoint (node) that has the same y coordinate as the point being tested. However, there are cases where this will still give you the wrong answer. From what I can tell, the ray-casting algorithm is primarily used in computer graphics, where being “close” is good enough.

3

Hi Mike, thanks for helping me out again.

For intersection 1, the latitude coordinate for both the UK and England node are 51.5930000 when I inspect the xml. So it isn’t a rounding error.

To help me understand better, are you able to describe the shape of the England polyline in the area of the intersection? It is a little tricky just looking at the raw numbers but I think the polyline is coming up from the bottom left, then goes horizontal for 5 nodes, and then moves on up to the top right. Is this correct?

Many thanks, Chessel

4

Hi Chessel,

Let’s take a simple example, an equilateral triangle with one vertex down (pointing to the south). Select a point that is outside of this triangle to the West, but has the same y-coordinate as the southern pointing vertex. If you draw a ray from the point that is outside of the triangle to the East, it will intersect the vertex in question. Since the point being tested is outside the triangle, we need an even number of intersections. Therefore we conclude that we should count an intersection with a vertex as two intersections (or as zero intersections).

Now, let’s rotate that same triangle so that a vertex is pointing west. Select a point outside of the triangle to the West but with the same y-coordinate as the west-pointing vertex. Like before, a ray drawn to the east will intersect this vertex. From the previous example, we know we should count this twice, so we do, but then the ray also intersects the eastern side of the triangle, so we get a total of three intersections, an odd number, indicating that we are inside the triangle, which is wrong.

Clearly, special treatment is needed when the ray intersects a vertex. One possible solution is to consider three vertices, the one which the ray intersects, the preceding one, and the following one. If the preceding and following vertices both have y values on the same side of the vertex being tested (both greater than or both less than), count the intersection twice, otherwise, count it once. I haven’t tested the above in all situations.

5

Hi Mike, that is a great example. Thanks.

I thought I had worked this sort of “tangental” case through but seems I’m wrong. I’ll try and work out some approach to these edge cases that I can implement.

My main question is still though that my UK/England problem isn’t a case of a triangle with a horizontal base as it looks like the intersection 1 case is a section of the polygon that is in general moving southwest to northeast. Is this correct or is it actually a tangental" intersection?

6

Hi Chessel,

Here is a discussion of the actual example you cited. I hope this helps. I would still recommend that you use one of the existing open source spatial libraries that I, and others, have suggested.

Starting from node 312182514, which is outside of England, and traveling east along your ray:

You enter England at 51.593, -2.6703813
Between nodes 11132397717 and 11132397718
You are now inside England
The intersection count is one

Continuing East, you exit England at 51.593, 1.2882946
Between nodes 312182509 and 312182524
You are now outside of England
The intersection count is two

Continuing East, you intersect node 312182515 at 51.593, 1.3809251

The node prior to this is

312182510 at 51.592, 1.3526499
That node is south of your ray.

You then intersect the following nodes:
312182515 at 51.593, 1.3988181
312182517 at 51.593, 1.4031891
312182518 at 51.593, 1.41333
312182519 at 51.593, 1.4194234
312182520 at 51.593, 1.4321584

The next node that is part of the boundary of England is
Node: 312182511 | OpenStreetMap at 51.592, 1.4604337

It is south of your ray. Since both this node and the node previous to the string of node intersections we have just listed are south of your ray, you have not reentered England (you have only touched its border - the border forms a sort of broad inverted U in this area), so you do not increment your intersection counter. Your intersection counter remains at two indicating that the original point is outside of England, which is correct.

7

Hi. I’ve just gone through the XML and followed the way that my troublesome ray intersects as intersection 1. It does indeed turn out that this is an inverted U shape and so counts as a tangental intersection and one I should treat as a fail in the point-in-polygon test.

My previous mistake in looking at the XML was just to look at the nodes as they appeared in the data. I think they must be sorted by latitude or something like that which led me to think it was a series of nodes moving upwards.

So now all I have to do is rewrite my point in polygon function so it looks at 3 nodes not just 2. The first two I use as before for my intersection test but if the test node is level with node 2, then I need to also look at node 3. If node 3 is on the same side of my ray as node 1 then it is a tangental hit and is actually a fail. If node 3 is on the other side of the ray to node 1 then it really is a hit and I flip my inside boolean variable.

And I also need to check that node 3 is not actually on the ray and keep looking ahead until I get to a node that isn’t on the ray.

And also cater for the scenario where the first pair of nodes I test aren’t horizontal. I’ll need to forward until I get to a non-horizontal pair of nodes.

And the scenario where my test node is actually on the horizontal segment.

Easy peasy. Not. :slight_smile:

But at least I know now.