Search code examples
algorithmcollision-detectioncomputational-geometry

Algorithm to place the rectangular inside the polygon

Is there any algorithm that can place an arbitrary rectangular inside an arbitrary polygon (I can deal with limitation to only convex polygons) in the closest available position (i.e. without intersections with polygon)?

enter image description here

For example, an algorithm should move the rectangular from image above to this position: enter image description here

It's important, that I don't know original position of rectangular before it leaves the polygon. So I should find most close available position in the polygon.

Solution

  • At least for convex polygons I believe there's a fairly simple solution which involves constructing the inset polygon representing the loci of the rectangle's center point when the rectangle is just touching the polygon.

    A diagram will hopefully help - the blue polygon represents the input polygon, the red the inner polygon that we need to construct.

    enter image description here

    Once we have this inner polygon we can just locate the point closest to the center of the rectangle and translate the rectangle's center to coincide with this point. If the inner polygon contains the center of the rectangle then you can choose between leaving it untouched or translating it outwards so that it touches the outer polygon.

    enter image description here

    The inner polygon can be constructed by insetting each side of the input polygon by a distance equal to half the angular width of the rectangle, and determining the intersection points of neighboring inset sides. If a side of the outer polygon is it angle a to the positive x axis then the inset distance is as shown below. Note that we'll have to ensure that a lies in the first quadrant, possibly swapping the width and height of the rectangle if this is not the case.

    enter image description here

    Once we have the inset distances for neighboring sides we can calculate the corresponding point on the inner polygon as shown below, where b is the angle between the neighboring sides and p' is the calculated point.

    enter image description here

    Here's some Java code to illustrate - we assume the input polygon is ordered counter-clockwise, such that the interior is to the left as we travel around the sides.

    List<Point2D> poly = new ArrayList<>(Arrays.asList(p(0, 0), p(10, 0), p(13, 7), p(9, 12), p(4, 15), p(-3, 11), p(-5, 6)));

List<Point2D> innerPoly = new ArrayList<>();
            
int n = poly.size();
for(int i=0, j=n-1; i<n; j=i++)
{
    Point2D p0 = poly.get(j);
    Point2D p1 = poly.get(i);
    Point2D p2 = poly.get((i+1) % n);
    
    Point2D u0 = unit(p0, p1);
    Point2D u1 = unit(p1, p2);
    
    double d0 = rectAngDist(u0, outerRect);
    double d1 = rectAngDist(u1, outerRect);
    
    double phi = Math.PI - angle(u0, u1);
    
    double v0 = d0 / Math.sin(phi);
    double v1 = d1 / Math.sin(phi);

    innerPoly.add(add(p1, add(times(u0, -v1), times(u1, v0))));
}

static double rectAngDist(Point2D u, Rectangle2D r)
{
    double w = r.getWidth();
    double h = r.getHeight();
    
    double s0 = w;
    double s1 = h;
    
    double th0 = angle(u);
    if(th0 < 0) th0 += Math.PI;
    if(th0 > Math.PI/2) 
    {
        s0 = h; s1 = w; 
        th0 -= Math.PI/2;
    }               
    
    return (s0 * Math.sin(th0) + s1 * Math.cos(th0))/2;         
}

    Once we have the inner polygon we can identify the closest point and translate the rectangle to coincide.

    Point2D centre = p(outerRect.getCenterX(), outerRect.getCenterY());
if(innerPoly.contains(centre))
{
    innerRect.setFrame(outerRect);
    return;
}
            
double minDist = 0;
Point2D closestPoint = null;
for(int i=0, j=n-1; i<n; j=i++)
{
    Point2D p0 = innerPoly.get(j);
    Point2D p1 = innerPoly.get(i);
    
    double len = distance(p0, p1);              
    Point2D u = unit(p0, p1);               
    
    Point2D diff = sub(centre, p0);             
    double s = dot(u, diff);
    
    Point2D pp = (s < 0) ? p0 : (s > len) ? p1 : add(p0, times(u, s));  
    
    double dist = distance(pp, centre);             
    if(closestPoint == null || dist < minDist)
    {
        closestPoint = pp;
        minDist = dist;
    }
}

translate(outerRect, sub(closestPoint, centre), innerRect);

    I implemented the above in Java to test out the ideas - you can watch a short capture of the application in operation here (Youtube).