Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]

share|improve this question
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.