1

So I have around 500K x,y points as a dataset. This is the coastline polygon of UK. If I select any point in that set and assume I am facing offshore, I need to create an algorithm which helps me derive the direction I am facing.

One of the simple ideas I've been having is to drop a point in the centre of the land mass and extrapolate the directing by plotting a straight line from that centre-point through the selected coastal point. But that's not accurate enough given the many curves and inlets around the coastline which would be ignored by such a blunt instrument as that.

At the opposite end of the complexity curve is somehow shifting each point inland by a small margin to then extrapolate that same line through the coastal point. This would be much more accurate - but to do that, I then need to know the same 'orientation' to shift each point accurately. So hence a catch 22.

So right now, I'm looking for ideas about how to do this conceptually? I'm certain there will be a mathematical core to the solution hence posting here given my area of expertise is engineering and not mathematics.

Thanks for listening !

Stew
  • 11
  • If you have the points in order, you can. 1. take a point and a direction 2. move that point to that direction just a little, obtaining point X 3. draw a straight line from X in the opposite to the selected direction 4. if that line (or I'd say ray or half-a-line) intersects with odd number of coasline intervals (say 1), X is inside, answer is no, otherwise (e.g. 4 or 2) X is not inside, answer is yes (the original facing direction was offshore). Did I get the problem right? – Alexey Burdin May 13 '20 at 17:04
  • @AlexeyBurdin Hi Alexey, thanks for the quick input. I think your ideas are in the right zone - that was where I started but the challenge is that for the base set of gps points I have provide no context of land or sea, they are just abstract points. So if I implement the idea you have shared I will find an intersection with a line between 2 adjacent/closest points but still not understand if I am pointing to onshore or offshore. As such, there is an associated pre-processing step to efficiently derive that context without having to annotate each point manually – Stew May 13 '20 at 17:38
  • I wanted to share this idea and I don't see if I can) Thanks – Alexey Burdin May 13 '20 at 17:43
  • Oh ‘click’ I think you may have it! Sorry I just realised you were talking about intersecting with another edge of the polygon ! Yes I think you may have something ! Let me experiment - thanks ! – Stew May 13 '20 at 17:49
  • Please feel free to edit the original question with the attempt taken in case if results would be somehow unsatisfactory -- maybe too slow (as $500000^2$ is much) or not 100% fitting the task. – Alexey Burdin May 13 '20 at 18:00
  • Can you please leave a comment on the answer at least was I answering the right question or is it useful at all, when you have time. Thanks – Alexey Burdin May 14 '20 at 15:38
  • Definitely ! I’m experimenting with this on smaller datasets - thanks. – Stew May 14 '20 at 15:39

1 Answers1

1

This thing works if the points are properly ordered to form a non-intersecting (not convex, a convex case would be too obvious) polygon:
Let's say we have a consecutive pair of points $B(x_i,y_i), A(x_{i-1},y_{i-1})$, so the vector $AB(x_i-x_{i-1},y_i-y_{i-1})$ points from $A$ to $B$. Let $AB=(a,b)$ for simplicity. Then we have vector $n=(-b,a)$ would point outwards or inwards, dependently of walking direstion, but it would point all the times the same way (meaning inwards/outwards). It's the idea of vector product by $(0,0,1)$.

The algorithm is quite simple, but fails on acute angles, need to be modified to use bisectors and $O(1)$ for every point ($O(n)$ overall). But not if you have just the points, without proper ordering...
Update: Though $3$ times read the original post, I don't know what exactly we do need. So,
0. We have ordered set of points, representing the UK coastline
Is that right?
1. For every point we have to find
What? Direction
2. such as if we stand at that point and look in that direction
we look at the sea. Is that right?
If all yes, let's say we have $3$ consecutive points $(x_{i-1},y_{i-1}),(x_{i},y_{i}),(x_{i+1},y_{i+1})$ and we take $2$ vectors: $v_1=(x_{i-1}-x_i,y_{i-1}-x_i),\,v_2=(x_{i+1}-x_i,y_{i+1}-x_i)$.
Then we normalize both of them and find their sum: $$b=\frac{v_1}{|v_1|}+\frac{v_2}{|v_2|}$$ will be a vector, laying on bisector of $v_1,\,v_2$. If $b=(0,0)$ that means $v_1||v_2$ and the point $(x_i,y_i)$ might be excluded from the polygon.
This handles acute angles of land fine (on the right):

But it has a flaw: the vector has to be in the opposite direction if the turn anlge is against the counter walk.
How we fix it:
we multiply the resulting vector by $\hbox{sign}(v_1\times v_2)$ -- the sign of $v_1\times v_2$ vector cross product. Now it's fine)

Alexey Burdin
  • 5,214