What is the best way to check if data is inside constraints? Linear programming?

Question

Assume that every black line can be displayed on this linear equation. Let's define them as constraints.

$$y = Kx + M$$ where $K$ is the slope and $M$ is the bias.

The purple is my data. My goal is to confirm that the data is inside the constraints. But how can I do that? In this case, it's 12 black lines, that means 13 equations because I'm counting also the open gap also as a line.

Anyway, they are the constraints. How can I prove with math that the purple data is bounded around these black lines if I know the data and the linear equations?

Should I use a specific method such as linear programming? Or should I only use if-statements e.g regular programming?

Let's define the constraints.

$$y = K_1 x + M_1$$ $$y = K_2 x + M_2$$ $$y = K_3 x + M_3$$ $$\vdots$$ $$y = K_{13} x + M_{13}$$

Update:

There are actually multiple constraints.

Answer 1

One approach is to find the convex hull and express each purple point as a convex combination of the resulting vertices. Explicitly, let $(x_p,y_p)$ be the coordinates of purple point $p$, define nonnegative decision variable $\lambda_i$ for vertex $(\hat{x}_i,\hat{y}_i)$, and solve the linear system \begin{align} \sum_i \hat{x}_i \lambda_i &= x_p \\ \sum_i \hat{y}_i \lambda_i &= y_p\\ \sum_i \lambda_i &= 1 \end{align} This system is feasible if and only if the purple point is within the bounded region.

As a shortcut, you can first find the convex hull of the purple points and check only the vertices in that subset.

Answer 2

A general way to do this for $N$ arbitrary polygons in $\mathbb{R^n}$ is to proceed in three steps(note -- definitely not optimized for speed/size):

1. Partition the $N$ polygons $(P_i)_{i\in 1...N}$ into convex components (i.e., Let $P_{ij}$ be the $jth$ component in the convex partition of polygon $P_i$).
2. Express each $P_{ij}$ as a system of half-planes $A_{(ij)}\mathbf{x} \leq \mathbf{b}_{(ij)}$ (not strict equalities -- we need to define the interior of each $P_{ij}$). Since the $P_{ij}$ are convex polygons, this construction will always exist.
3. For each data point $\mathbf{x}_k \in \mathbb{R^n}$ check it against each system of inequalities $A_{(ij)}\mathbf{x} \leq \mathbf{b}_{(ij)}$, stopping when you find an $P_{ij}$ whose system is satisfied by $\mathbf{x}_k$. If none are satisfied, it is outside of all polygons. If $\mathbf{x}_k$ satisfies system $A_{(pq)}\mathbf{x} \leq \mathbf{b}_{(pq)}$ then it is contained in $P_q$.

That is the basic algo. You could make it a bit more efficient if you sorted the order of the polygons test based on how close $\mathbf{x}_k$ is to the centroid of each $P_{ij}$ (closest to furthest). You'd likely need to use a $kd-$tree or something like that to avoid the quadratic explosion of comparisons.