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 !
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)