1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – fontanf
    Oct 2, 2023 at 11:53
  • 1
    $\begingroup$ Is your polygon convex? Is it in order, counter-clockwise? $\endgroup$
    – Brannon
    Oct 2, 2023 at 12:17
  • $\begingroup$ @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 $\endgroup$
    – Ken Adams
    Oct 2, 2023 at 13:54
  • $\begingroup$ @Brannon hello, Yeah polygon is convex, and the points are unordered. Do you have any idea regarding such scenarios? $\endgroup$
    – Ken Adams
    Oct 2, 2023 at 13:55
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4779400/… $\endgroup$
    – RobPratt
    Oct 3, 2023 at 0:11

1 Answer 1

5
$\begingroup$

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}

$\endgroup$
13
  • $\begingroup$ thanks for your answer. Really appreciate it. But the thing is I am working in Constraint Satisfaction Programming where the variables can only take Integer values. Here "lambda" takes float value and SAT problems does not support such floating point variables. How can I use you advise for Integer only variables? Can you please help me with that? $\endgroup$
    – Ken Adams
    Oct 2, 2023 at 16:28
  • $\begingroup$ @KenAdams I updated my answer just now. $\endgroup$
    – RobPratt
    Oct 2, 2023 at 17:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Oct 2, 2023 at 17:52
  • 1
    $\begingroup$ @A.Omidi The integer variables $p_i$ and $q$ are the numerator and denominator of a rational approximation of the continuous variable $\lambda_i$. $\endgroup$
    – RobPratt
    Oct 3, 2023 at 13:06
  • 1
    $\begingroup$ @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$. $\endgroup$
    – RobPratt
    Oct 3, 2023 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.