Finding the intersection of a line with a polygon

Question

I am trying to find the intersection of a line represented by two geographical coordinates and a polygon represented by three or more geographical coordinates. My goal is to find the closest point to the first coordinate on any of the polygon's boundary lines and the line described by the first two coordinates.

I am assuming that the polygon is a simple closed polygon (i.e. rectangle).

In this case the algorithm would return the intersection point marked in red (closer to the first coordinate).

I am using Kotlin for android.

I was trying to use Turf for Java but was not able to find the functions to do that.

Answer 1

Maybe there is actually a library for this problem, but why load thousends of code lines when you can do it yourself with 10 or 20 lines of code?

The coordinates of the points must be given in degrees (i.e. 8°30'00" -> 8.5) and have negative signs for the southern and western hemisphere respectively. Then you can find the coordinates of the red point you are looking for with the following algorithm:

1. For each blue line segment (there are 6 of them in your drawing), you have to use formula 1 (see below) to calculate whether the blue line segment intersects the green line at all, and if so, you have to calculate the coordinates of the intersection point. In your example, you will find two such intersection points.

2. For each intersection point that you have found in step 1), you must calculate the distance squared to point 1 using formula 2. The intersection point from 1) with the smallest distance squared is the red point you are looking for.

Formula 1: If you are familiar with math, you can find everything you need here (or look for "intersection of two line segment" on the Internet). If not, I can explain it to you step by step. I would then need to know: Is the red point guaranteed to be between 1 and 2, or could 1 and 2 also be on the same side of the polygon? Is the green straight line guaranteed to hit the blue polygon?

Formula 2: If (P.x, P.y) is an intersection point from 1), it has the distance squared

(P.x - 1.x) * (P.x - 1.x) + (P.y - 1.y) * (P.y - 1.y) 

from 1 = (1.x, 1.y).