0

Suppose I have 2D polygon image and a larger 2D rectangle image and that I have a collection of points for each that I want to align.

For Example the polygon has point collection:

[PA(a, b), PB(c, d), (PC(e, f)]

And the Rectangle has point collection:

[RA(g, h), RB(i, j), RC(k, l)]

Is there an algorithm I can use to pragmatically transform the Polygon such that the points will align to the points on the Rectangle, Scaling and Rotating such that the Polygon remains intact?

Please note: I'm using three points in the example; however, an algorithm with an arbitrary number of equal points is fine.

For clarity:

I by transform I mean: Scale and Rotate. The objective being that the polygon image is not "warped"

I think circumscribed does describe what I'm trying to accomplish; however, for all practical purposes the Rectangle will always be large enough to contain the polygon.

Images:

Given: Polygon (please assume outside is transparent, inside is opaque)

And: Rectangle

I want: Please Note both Scale and Rotation

  • 3
    Could you be a little more specific about what you mean by "transform" and "align", and provide some examples of desired input/output? For instance, if the polygon is not exactly the right size to be circumscribed by the rectangle (I assume you're interested in circumscription here), where do we put it? – Ixrec Jun 3 '15 at 18:21
  • @Ixrec please see edit – SMTF Jun 3 '15 at 18:40
  • 4
    There is an ancient proverb that says "One picture is worth a thousand words." This would seem to be one of the times where that observation is appropriate. – John R. Strohm Jun 3 '15 at 18:45
  • Are you just looking for the linear transformation matrix that transforms PA to RA, PB to RB and PC to RC? If so, you really obscured your question with this polygon and rectangle explanation. – null Jun 3 '15 at 19:24
1

In general, no.

The two sets of three points each define a triangle. Unless those triangles are proportional to one another, there is no 2D affine transformation (i.e., without warping) that can map one to another.

In the special case that they are proportional, a geometric approach would be:

  1. Compute the circumscribing circles for each set of points.
  2. Translate the polygon by the negative of the center of its circle, centering it's circle.
  3. Scale by the ratio of the radii of the two circles.
  4. Rotate the polygon (about the origin) to align the directions of the points.
  5. Translate the polygon to the center of the rectangle's circle.

You may have to perform a reflection between steps 3 and 4 if the order of the two points in each set are not identical.

  • I suspect you are correct; however, please see if the images I've added further inform your answer. Thank you. – SMTF Jun 3 '15 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.