Find a line that crosses multiple line segments I'm looking for a formula, or algorithm, that would allow me to figure out if there's a line that cross multiple line segments (those are always parallel to the y axis), and if there is, the equation for that line.
For example, in the following diagram, I'm looking for any line that touches the 4 vertical bar, such as the red line shows. It can touch the bars anywhere.

I can figure out how to do it with 3 line segments, but anything over that I have no idea.
I'm also not a mathematician so I probably got most terminology wrong.
EDIT: a possible approach is recursive, by drawing the bow-tie of possible lines for the left-most two segments, and seeing if the third segment touches the bow-tie. If so, create a narrower bow-tie of acceptable lines for the first three, and so on.


 A: If a line $\ L\ $ has equation $\ y=ax+b\ $ and a vertical line segment has $\ x$-coordinate $\ x_0\ $,  maximum $\ y$-coordinate $\ u_0\ $, and minimum $\ y$-coordinate $\ \ell_0\ $, then $\ L\ $ intersects $\ S\ $ if and only if
$$\ell_0\le ax_0+b\le u_0\ .
$$
Thus,if the $\ x$-coordinate, maximum $\ y$-coordinate and and minimum $\ y$-coordinate of your $\ i^\text{th}\ $ vertical line segment are $\ x_i $, $\ u_i\ $ and $\ \ell_i\ $, respectively, then the line with $\ y=ax+b\ $ will satisfy your criteria if and only if
$$
\hspace{-4em}(1)\hspace{8em}\ell_i \le ax_i +b\le u_i\\
$$
for all $\ i\ $.  This is a system of linear inequalities in the two variables $\ a, b\ $, for which a solution can be found efficiently (if it exists) by any of the modern techniques of linear programming. However, because there are only two variables, there's also a more elementary technique you can use.
Assume, without loss of generality, that $\ x_i\ $ are indexed in order—that is, $\ x_i\le x_j\ $ if $\ i\le j\ $. If $\ x_i=x_j=x^*\ $ for any $\ i,j\ $ with $\ i\ne j $, let $\ \ell^*=\max_\limits{\left\{j\,|\,x_j=x^*\right\}}\ell_j\ $ and $\ u^*=\min_\limits{\left\{j\,|\,x_j=x^*\right\}}u_j\ $. Then it is possible for all of those vertical segments to be intersected by a single line  if and only if $\ \ell^*\le u^*\ $, and a line will intersect them all if and only if it intersects the vertical segment with $\ x$-coordinate $\ x^*\ $,  maximum $\ y$-coordinate $\ u^*\ $, and minimum $\ y$-coordinate $\ \ell^*\ $.  This segment is just the intersection of all the segments having $\ x$-coordinate $\ x^*\ $. We can thus simplify the problem by replacing all these vertical segments with this single segment.  Assume that this has been done. Then we will have $\ x_i<x_j $ for $\ i<j\ $.
Now rewrite the inequalities $(1)$ as
$$
\ell_i-ax_i\le b\le u_i-ax_i
$$
from which it follows that
$$
\hspace{-3em}(2)\hspace{8em}\ell_i-ax_i\le u_j-ax_j
$$
for all $\ i,j\ $.  If $\ i<j\ $, this gives
$$
\hspace{-5em}(3)\hspace{8em}a\le\frac{u_j-\ell_i}{x_j-x_i}\ ,
$$
while if $\ i>j $ it gives
$$
\hspace{-5em}(4)\hspace{8em}\frac{\ell_i-u_j}{x_i-x_j}\le a\ .
$$
Thus, if $\ \underline{a}=\max_\limits{\{(i,j)\,|\,i>j\}}\frac{\ell_i-u_j}{x_i-x_j}\ $ and $\ \overline{a}=\min_\limits{\{(i,j)\,|\,i<j\}}\frac{u_j-\ell_i}{x_j-x_i}\ $ then we must have
$$
\hspace{-6em}(5)\hspace{8em}\underline{a}\le a\le\overline{a}
$$
which is only possible if $\ \underline{a}\le\overline{a}\ $.
Conversely, if $\ \underline{a}\le\overline{a}\ $ and $\ a\ $ is any number satisfying $(5)$, then it will satisfy $(3)$ for any $\ i,j\ $ with $\ i<j\ $ and $(4)$ for any $\ i,j\ $ with $\ i>j\ $, and hence it will satisfy $(2)$ for all $\ i,j\ $.  So if we let $\ \underline{b}=\max_\limits{i}\,\ell_i-ax_i\ $ and $\ \overline{b}=\min_\limits{j}\,u_j-ax_j\ $ then $\ \underline{b}\le\overline{b}\ $ and it is possible to find a number $\ b\ $ satisfying $\ \underline{b}\le b\le \overline{b}\ $.  The numbers $\ a\ $ and $\ b\ $ will then satisfy $(1)$ for all $\ i,j\ $, and hence the line $\ y=ax+b\ $ will intersect all the given vertical segments.
To summarise:

*

*The problem be solved only if any set of vertical segments having the same $\ x$-coordinate have a nonempty intersection.


*If the problem is simplified, as described above, by replacing every such collection of vertical segments having the same $\ x$-coordinate with their intersection; and


*the $\ x$-coordinates of the vertical segments are indexed so that $\ x_i<x_j\ $ for $\ i<j\ $;
then the problem has a solution if and only if
$$
\max_\limits{\{(i,j)\,|\,i>j\}}\frac{\ell_i-u_j}{x_i-x_j}\le\min_\limits{\{(i,j)\,|\,i<j\}}\frac{u_j-\ell_i}{x_j-x_i}\ ,
$$
and if $\ a,b\ $ are any numbers satisfying the inequalites
\begin{align}
\max_\limits{\{(i,j)\,|\,i>j\}}\frac{\ell_i-u_j}{x_i-x_j}\le&\,a\le\min_\limits{\{(i,j)\,|\,i<j\}}\frac{u_j-\ell_i}{x_j-x_i}\\
\max_\limits{i}\,\ell_i-ax_i\le&\,b\le\min_\limits{j}\,u_j-ax_j\ ,
\end{align}
then the line with equation $\ y=ax+b\ $ will intersect all the given vertical segments.
A: I don't know your precise requirements in handling this problem, but I can suggest a "practical" (engineer-wise) approach to it.
The concept is that if there is a set of lines which crosses all or most of the segments, then the least-squares regression line through the end points of the segments will be "close" to that set.
Since you are actually interested to pierce the most of the segments, the smaller ones having to you the same interest as the larger, you shall actually perform a weighted regression, giving higher weight to smaller segments. You could for instance duplicate the points at regular distance over each segment (every $1/3$) or triplicate, etc. and then perform the regression.
You could also perform a non-linear regression, e.g. quadratic, and then judge from the concavity of the obtained parabola if a line going through all segments is attainable.
A: Defining the vertical segments as $s_k = (p_k,q_k),\ \ \cases{p_k = (x_k,l_k)\\ q_k = (x_k, u_k)}$with $l_k \le u_k$ for $k=1,\cdots,n$ the problem can be solved finding $(a, b)$ such that
$$
l_k \le a x_k + b\le u_k,\ \ \ k=1,\cdots,n
$$
This kind of problem can be solved with the help of a linear programming algorithm. Linear programming solves a problem proposed as
$$
\min_y c\cdot y \ \ \text{s.t}\ \ M \cdot y \ge b,\ \ y \ge 0
$$
so forming
$$
M = \left(\begin{array}{cc}
x_1 & 1 \\
x_2 & 1 \\
\vdots & \vdots\\
x_n & 1 \\
-x_1 & -1 \\
-x_2 & -1 \\
\vdots & \vdots\\
-x_n & -1 \\
\end{array}
\right),\ \ \ b = 
\left(\begin{array}{c}
l_1  \\
l_2  \\
\vdots \\
l_n\\
-u_1 \\
-u_2\\
\vdots\\
-u_n\\
\end{array}
\right), \ \  c = (1, 1)
$$
we can proceed submitting it as a linear programming problem.
Follows an example, solved with a MATHEMATICA script
n = 10;
SeedRandom[1];
x = Sort[RandomReal[{0, 10}, n]];
p = Sort[RandomReal[{0, 10}, n]];
q = RandomReal[{1, 3}, n];
pq = p + q;
M = Join[Table[{x[[k]], 1}, {k, 1, n}], Table[{-x[[k]], -1}, {k, 1, n}]];
b = Join[p, -pq];
resultl = Quiet[LinearProgramming[{0, 1}, M, b]]
resultu = Quiet[LinearProgramming[-{0, 1}, M, b]]
segs = Table[{{x[[k]], p[[k]]}, {x[[k]], pq[[k]]}}, {k, 1, n}];
grseg = Table[Graphics[{Thick, Black, Line[segs[[k]]]}], {k, 1, n}];
gr2l = Plot[resultl[[1]] u + resultl[[2]], {u, Min[x], Max[x]}, PlotStyle -> {Blue, Dashed}];
gr2u = Plot[resultu[[1]] u + resultu[[2]], {u, Min[x], Max[x]}, PlotStyle -> {Red, Dashed}];
Show[grseg, gr2l, gr2u, AspectRatio -> 1]

Follows a plot showing blue the minimum and in red the maximum answers.

NOTE
The condition $x \ge 0$ can be relaxed by introducing a translated variable as $X = x - \lambda(1, 1)$ with $\lambda$ big enough.
