Discrete point inside a polygon formed by set of vertices

I am working on a problem where I have a set of 2D vertices and a test point. I want to chek whether the test point lies inside the polygon formed by the set of given vertices. I am trying to model this problem using discrete optimization.

Naturally, this lies under point-in-polygon problem and I tried to implement a model for the Ray casting algorithm for my discrete problem. It seems a bit difficult to model and program it as I ran into some division issues.(You can look at this post for the model and the issue). There is a big discussion about the method in this stack-post

My Question:

1. Is there any other way in discrete optimization modeling to check if a test point lies inside the set of vertices?

2. Does the Ray-casting algorithm fit best when we model it in Integer programming format?

This problem is kinda of stressing me out. Can anyone suggest me some other method that we can model as a constraint model I am using a constrained programming method hence strictly integers only

Any help will be really appreciated :)

• I don't have time for a detailed answer right now. One way is to decompose your polygon into convex polygons. Then write the edges of the polygons as equations of the form $ax + by + c = 0$ and compute the relative distance from your point to each edge with linear constraints. There must be at least one convex polygon for which all these distances are negative for the point to lie inside the polygon. Oct 2 at 11:53
• Is your polygon convex? Is it in order, counter-clockwise? Oct 2 at 12:17
• @fontanf thanks a lot for the input but is there any name for this method? And how would I find a, b and c in the equation? Will you please elaborate when you get some time? I will be greatful Oct 2 at 13:54
• @Brannon hello, Yeah polygon is convex, and the points are unordered. Do you have any idea regarding such scenarios? Oct 2 at 13:55
• Cross-posted: math.stackexchange.com/questions/4779400/… Oct 3 at 0:11

You can test whether a point $$(x,y)$$ appears inside a convex polygon with vertices $$(x_i,y_i)$$ by solving a linear programming problem (with no objective): \begin{align} \sum_i \lambda_i &= 1 \\ \sum_i x_i \lambda_i &= x \\ \sum_i y_i \lambda_i &= y \\ \lambda_i &\ge 0 &&\text{for all i} \end{align} The idea is to express $$(x,y)$$ as a convex combination of the vertices. If the problem is feasible, the point appears inside the polygon. If infeasible, it doesn't.
Note that the $$\lambda_i$$ are continuous variables. If your solver requires integer variables, you can approximate $$\lambda_i$$ as $$p_i/q$$, where $$p_i$$ and $$q$$ are integer variables, and clear the denominators: \begin{align} \sum_i p_i &= q \\ \sum_i x_i p_i &= x q \\ \sum_i y_i p_i &= y q \\ p_i &\ge 0 &&\text{for all i} \\ q &\ge 1 \end{align}
• I imposed lower bounds on $p_i$ and $q$. If your SAT solver also requires finite upper bounds, you will need to determine those yourself. The point lies within the polygon if and only if all the constraints can be satisfied simultaneously. Oct 2 at 17:52
• @A.Omidi The integer variables $p_i$ and $q$ are the numerator and denominator of a rational approximation of the continuous variable $\lambda_i$. Oct 3 at 13:06
• @KenAdams Both formulations still apply if $x$ and $y$ are variables. The second formulation becomes nonlinear because of the products $x q$ and $y q$. Oct 3 at 13:07