Discrete point inside a polygon formed by set of vertices

Question

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 :)

Answer 1

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}