CODEWITHSUNDEEP
algorithm
Wonka Bear
Wonka Bear

Reputation: 31

Shifting Polygon inside Polygon

I'm having troubles figuring out an algorithm to solve the following problem:

enter image description here

I want the user to be able to snap the rectangle (Could be any type of polygon) to the 4 corners of the polygon such that it's as far inside the polygon as it can be.

What I'm trying so far:

  1. Allow user to get the object.
  2. Find the nearest vertice on the polygon to the rectangle.
  3. Find the furthest vertice on the rectangle to the polygon's nearest vertice.
  4. Use a plane to find the first intersection point with the furthest rectangle's point to the polygon's point.
  5. Shift up or down using the corresponding x/y plane based on whether the furthest point is further in the x/y coordinate.
  6. Keep repeating the steps above until everything is inside.

Upvotes: 0

Views: 233

Answers (1)

btilly
btilly

Reputation: 46455

As long as the enclosing polygon is convex, you can write this as a linear programming problem and then apply https://en.wikipedia.org/wiki/Simplex_algorithm to find the answer. The smaller polygon you are putting inside can be as complicated as you want.

Your inequalities are all of the conditions to make sure that each vertex of the smaller polygon is inside of the larger. You don't have to be clever here, there is no cost to extra inequalities that don't come into play.

The function to optimize is constructed as follows. Look at the interior angle of the vertex you are trying to get close to. Draw a coordinate system at that point with one axis pointing directly into the polygon (call that axis y) and the other at right angles to the first (call that axis x). You want to minimize the y value of the nearest vertex on the polygon you are putting in. (Just put the polygon you are putting in in the middle, and search for the nearest vertex. Use that.

The solution that you find will be the one that puts the two vertices as close together as possible subject to the condition that the smaller polygon has to be inside of the larger.

Upvotes: 1

Related Questions