I am working on a graphics project wherein I need to keep a rectangle (assume it has a fixed but arbitrary size, rectWidth * rectHeight) constrained inside an arbitrary polygon.
The polygon is represented in data as a series of connected points. The direction/winding of the polygon is known (usually clockwise, but that can be changed easily enough) and may or may not contain holes (whose winding is also known and can be set to whatever is easier). If holes exist, they are similarly represented in data as series of sequential/connected points. Neither polygon nor holes self-intersects, but any may be concave. Once the polygon is constructed it will not change, though it is arbitrarily constructed.
If an attempt is made to move the rectangle outside the polygon, the rectangle should move as close to the desired point as possible (minimize total distance) while still remaining fully inside. No vertices of the rectangle are allowed to leave the polygon, though they can rest on the edges/edges of holes. No edge of the rectangle is allowed to intersect with any edge of the polygon/holes, though it may rest against any vertices/edges.
Ideally the mathematical operations underlying these constraints remain as lightweight/fast as possible because they'll be running very frequently on a not-very-fast processor.
I've spent a fair amount of time on this problem, and I think the best way to simplify the problem is to create a new polygon/set of polygons, based on the original polygon, that represent(s) the "safe" or "allowed" area for the center of the rectangle to reside. I can calculate this/these "sub-polygon(s)" just once, so even if it's a bit of a heavier computation that's OK. This way I only have to try constraining a single vertex (the center of the rectangle): it's fairly easy to determine whether or not that point is inside the polygon(s) with a ray-test, and if necessary it's decently easy (via dot-products) to find the closest place in/on the polygon(s) to place the rectangle (if the user requests placing the rectangle in a spot outside the polygon).
If my assumption that this is a good/simple way to constrain the rectangle is bad, please let me know. The rest of this question proceeds with that assumption.
My challenge right now is to construct the "sub-polygon(s)" from the initial. As I see it, each side of the initial polygon needs to "shrink", but it doesn't appear to be a consistent operation. See the picture below: [
On order for the (shaded) rectangle to remain within the overall polygon, the center of the rectangle must remain within the (incomplete) sub-polygon denoted with the dotted line. Yet the lines of the dotted polygon are not just reduced copies of the original polygon; there are new lines! Specifically the ~45 degree ones on the insides of inner corners.
My initial attempts to solve for these suggested that we could copy each line of the original polygon, move it by some quantity and in some direction, the trim the segments where they intersected as well as adding new segments where they had gaps. Unfortunately this solution doesn't seem consistent, either: some lines seem to be translated to the right and down, while others are translated to the left and up - I can't determine the pattern/reasoning. Obviously they always move "inward" (mathematically struggling a bit with determine what that means with regards to their coordinates) while holes would have their lines move "outward", but I'm stuck on figuring out the relationship between the original polygon and new one(s).
What IS the relationship? Alternatively, is there a better way to constrain given the specifics I've provided?
Thank you!