# Find the nearest point that lies within a polygon specified by 6 linear inequalities

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

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

-
Try minimizing the distance function with Lagrange Multipliers. – Brett Frankel Apr 27 '12 at 23:28
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. – nornagon Apr 27 '12 at 23:35
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. – Brett Frankel Apr 27 '12 at 23:37
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). – nornagon Apr 27 '12 at 23:38
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. – Brett Frankel Apr 27 '12 at 23:40