1
$\begingroup$

I have six linear inequalities that together specify a polygon. For a given point $P$, how can I find the nearest point $P'$ that satisfies all six inequalities (if $P$ itself does not)?

inequalities

[edit: changed picture to represent regions as well as bounds]

  • 0
    Try minimizing the distance function with Lagrange Multipliers.2012-04-27
  • 0
    I'm not too familiar with Lagrange multipliers, but from what I can see the technique is useful for minimising within _equality_ conditions, not inequality conditions.2012-04-27
  • 0
    Well, you know that your minimum will be along one of the boundary points, since if not you could find a point that is a hair closer to $P$. So your equality conditions come from the fact that you're looking for points on one of the six lines (curves?) shown. You should also check the vertices, since they may be the best you can do in the region of interest but may not be optimal on any line.2012-04-27
  • 0
    I'd rather avoid finding all the intersection points, since I'm not really sure how to deal with points that are outside the valid region (e.g. the points where the green line intersects the two blue lines on the left).2012-04-27
  • 0
    By verteces, I meant those which are on the boundary of the region. There's no reason to check points those intersection points which are strictly outside the region you're interested in.2012-04-27
  • 0
    If I'm finding all the intersection points anyway, I might as well just collect the segments and use a point-segment distance test and take the minimum. I was hoping for something a little more elegant :/2012-04-27
  • 0
    On the face of it, this is a quadratic programming problem: minimize $\lVert P - P'\rVert^2$ subject to linear inequalities on $P'$. But six is a very small number of inequalities, so trying all the segments on the boundary is probably the easiest thing to do.2012-04-28

0 Answers 0