Find smallest quadrilateral from a given quadrilateral that fits a rectangle

I am working on an imaging application using GDI+ in C# (VS 2008) and I got stuck with something. I have a rectangle on my canvas and a quadrilateral of random size on my canvas. I know the 4 corner points of rectangle and the quadrilateral. I need to compute开发者_JAVA百科 the smallest quadrilateral that fits my rectangle. The new quadrilateral needs to be computed from the quadrilateral I already have on the canvas. The new quadrilateral need not be the scaled version of my existing quadrilateral, but the sides of the input and output quadrilateral must be parallel. I have uploaded an image to describe the problem.

http://www.4shared.com/photo/dufR-UeN/SmallQuad.html

Any ideas how I can go about this?

Thanks in advance.

---

Ok, let A, B, C, D be the points defining your random quadrilateral:

• 1 is the segment [AB]
• 2 is the segment [BC]
• 3 is the segment [CD]
• 4 is the segment [DA]

Now let E (top left), F (top right), G (bottom left), H (bottom right) be the points of your rectangle. In your image, you have to determine:

• the equation of the parallel to 1 passing by E (let's call it 1')
• the equation of the parallel to 2 passing by F (let's call it 2')
• the equation of the parallel to 3 passing by G (let's call it 3')
• the equation of the parallel to 4 passing by H (let's call it 4')

Then you can compute their intersections, which in turn give you the lines you need.

Let's determine 1' (the other ones are similar): all lines parallel to 1 have the same slope as 1 has. And this slope s1 is given by:

s1 = (yB - yA) / (xB - xA)

Then 1' has an equation like y = s1 * x + b. Since we want this line to reach the point E(xE, yE), we have b:

yE = s1 * xE + b => b = yE - s1 * xE

and then 1' has for equation: y = s1 * (x - xE) + yE. Similarly, 2' has for equation y = s2 * (x - xF) + yF, s2 being determined by the coordinates of B and C, idem for 3' and 4'.

We now want the intersection of 1' and 2': this point I has coordinates the verify the equations of these 2 lines, so:

yI = s1 * (x - xE) + yE
yI = s2 * (x - xF) + yF

So:

s1 * (xI - xE) + yE = s2 * (xI - xF) + yF

which gives you xI then yI:

xI = (s1 * xE - s2 * xF + yF - yE) / (s1 - s2)
yI = s2 * (xI - xF) + yF
   = (s1 * s2 * xE - s1 * s2 * xF + s1 * yF - s2 * yE) / (s1 - s2)

You can determine the coordinates of J (intersection of 2' and 3'), K (intersection of 3' and 4') and L (intersection of 4' and 1') the same way. The quadrilateral you want is formed by these 4 points I, J, K and L.