Geometry – How to Find the Shortest Path Intersecting a Point in a Polygon

Question

Sorry if I'm explaining this badly, math in English can be a bit troublesome.

I have a polygon, I have a random point inside that polygon. From this point I want a line "drawn" edge-to-edge and to intersect the point, but I want this line to be the shortest possible. See my image below:

The red dot indicates the random point inside polygon.
The green dotted line is the shortest path/line (which I'm looking for)
The blue vague line is just example of longer lines that does not match the criteria (shortest path of all paths).
And, obviously I want the path to intersect the red point.

(My real problem is that I want to find the line AND all the coordinates above that line, but that can be another problem for another day unless someone's feeling really ambitious)

Edit:
I want to do this because I want to somewhat (not true physics) simulate the (2D) behavior of cracking a rock and thus want to know what piece of the rock that should split away.

Also, a solution for a convex-polygon would suffice (even though the image shows a non-convex).

Answer 1

The main problem here is how to handle the non convexity. Given the rock 2D shape as a point sequence

$$ S = \{p_k\}, k = 1,\cdots,n $$

we can construct the segments

$$ s_k = \lambda_k p_k + (1-\lambda_k) p_{k+1},\ \ \ 0 \le \lambda_k\le 1 $$

and $s_n = \lambda_n p_n + (1-\lambda_n) p_1$

Now given a point $p_0$ in the $S$ interior, we define a generic line containing $p_0$ as

$$ L_j = p_0 + \lambda_0 v_j,\ \ \ v_j = (\cos t_j, \sin t_j) $$

and then given a direction $t_j$ we determine all possible intersections between $L_j$ and $\{s_k\}, \ \ k = 1,\cdots n$: thus given a $t_j$ we consider as associated interior distance

$$ d_j = \min{{\lambda_0}_k^+}-\max{{\lambda_0}_k^-} $$

where $\lambda_0^-,\lambda_0^+$ indicates if the intersection result gives a $\lambda \le 0$ or $\lambda \ge 0$ respectively. Finally we register for each $t_j$ the minimum $d_j$ found obtaining this way the result. The sweep made with $t_j$ can be choose to the precision needed.

Follows a MATHEMATICA script to solve with specified precision this problem. Here data is the set of points defining the rock profile, and p0 is the interior point. The algorithm performs a sweep from $0$ to $360$ degree, calculating the shortest distance along all possible intersections.

s[p1_, p2_, lambda_] := lambda p1 + (1 - lambda) p2
l[p0_, lambda_, v_] := p0 + lambda v
v = {Cos[t], Sin[t]};
data = {{0, 2.5}, {2.0, 1.8}, {3, 0.5}, {7.0, 10}, {2, 6.0}, {2.5, 8.0}, {0.5, 7.0}};
p0 = {1, 5};
data = AppendTo[data, data[[1]]];
n = Length[data] - 1;
segs = Table[s[data[[k]], data[[k + 1]], Subscript[lambda, k]], {k, 1, n}];
grp = Graphics[{Red, PointSize[0.02], Point[p0]}];
grd = ListLinePlot[data];
grt = Table[Graphics[Text[k, data[[k]]]], {k, 1, n}];

distmin = Infinity;
jmax = 360;
For[j = 0, j <= jmax, j++, tj = 2 Pi j/jmax;
  change = False;
  vj = v /. {t -> tj};
  minresult = -Infinity;
  maxresult = Infinity;
  For[k = 1, k <= n, k++,
    sol = Solve[Thread[l[p0, lambda, vj] == segs[[k]]], {lambda, Subscript[ lambda, k]}][[1]];
    lambda0 = Subscript[lambda, k] /. sol;
    If[(0 <= lambda0) && (lambda0 <= 1), result = (lambda /. sol), result = Infinity];
    If[result != Infinity,
      If[result <=  0, If[result >= minresult, minresult = result; topt = tj; change = True]];
      If[result >= 0, If[result <=  maxresult, maxresult = result; topt = tj; change = True]]]
  ];
  dist = maxresult - minresult;
  If[dist <= distmin, distmin = dist; maxr = maxresult; minr = minresult; tmin = topt]
]
vj = v /. {t -> tmin};
pa = l[p0, minr, vj];
pb = l[p0, maxr, vj];
seg = u pa + (1 - u) pb;
gr2 = ParametricPlot[seg, {u, 0, 1}];
grpa = Graphics[{Red, PointSize[0.02], Point[pa]}];
grpb = Graphics[{Red, PointSize[0.02], Point[pb]}];
Show[grp, grd, grt, grpa, grpb, gr2, Axes -> True]

In the figures, the black dot represents $p_0$ and in dashed red the rupture line.

NOTE

The intersections $L_j\cap s_k$ are performed as

$$ p_0+\lambda_0 v_j = \lambda_k p_k + (1-\lambda_k) p_{k+1} $$

giving

$$ \cases{ \lambda_0 = \frac{x_{k+1}(y_0-y_k)+x_0(y_k-y_{k+1})+x_k(y_{k+1}-y_0)}{(y_{k+1}-y_k)\cos t_j+(x_k-x_{k+1})\sin t_j}\\ \lambda_k = \frac{(y_{k+1}-y_0)\cos t_j+(x_0-x_{k+1})\sin t_j}{(y_{k+1}-y_k)\cos t_j+(x_k-x_{k+1})\sin t_j} } $$

Here to have a feasible intersection it is needed $0\le \lambda_k\le 1$