Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a square and a polygon. I want to transform all the points inside this square such that they are mapped inside the polygon. I was trying using scale and rotate matrices but I am not able to come up with anything that is making sense to me. I also googled a lot for some algorithm which can be used to implement this but dint find anything. Can anybody please help me with an algorithm which is there to map the points in square to a polygon?

enter image description here

I want to map the points inside the square to points inside the polygon on the right.

share|improve this question
    
If you scale a square, it is always possible to make it big enough to include any given polygon. Are you looking for the smallest square possible able to include a given polygon? –  Alexis Dufrenoy Feb 27 '13 at 13:07
    
Your question is ambiguous. Could you add some details (picture would be the best, but it is not necessary)? –  dtldarek Feb 27 '13 at 13:10
    
I have pasted the picture for better clarity. And No i dont want to scale the square in such a way that the square is inscribed or excribed inside or outside the polygon. I just want the mapping. Is there a way to do it? May be not only by using scale and rotate matrix. May be by using some other technique or using something in addition to scale and rotate matrix. –  user2092000 Feb 27 '13 at 13:30
1  
Schwarz-Christoffel mappings will do this, even conformally, but they are computationally very expensive. –  mrf Feb 27 '13 at 13:51
    
@mrf I went through that mapping but I found it difficult to comprehend. Is there an algorithm or can you suggest some steps in order to arrive at the result. –  user2092000 Feb 27 '13 at 13:58
add comment

1 Answer

Label the points of your polygon $A$, $B$, $C$, $D$, $E$, starting at the lower left and going counterclockwise. Then let $F$ be the mid-point of the bottom side $AB$. Define a mapping $f:[0,1]\times[0,1]\rightarrow R^2$ by:

$$f(u,v) = (1-u)(1-v)A + (1-u)vF + u(1-v)E + uvD$$

You can check that this maps $[0,1]\times[0,1]$ onto the left half of your polygon (the half with vertices $A$, $F$, $D$, $E$. By suitable scaling, you can get a mapping from the left half of your rectangle to the left half of the polygon.

Do the same thing with the right halves.

Put the two mapping together to get a mapping from the whole rectangle to the whole polygon.

More generally, choose two polylines $P(u)$ and $Q(u)$. These are strings of edges that will serve as the "top" and "bottom" borders respectively. Then use the mapping

$$g(u,v) = (1-v)P(u) + vQ(u)$$

to construct a "ruled" surface between $P$ and $Q$. This maps from the unit square to the polygon. Adjust accordingly to get a mapping from your rectangle to the polygon.

share|improve this answer
    
This would work in the above figure. I had put that figure only for others to understand my question better. I was not asking for answer to that specific example. What I want is transformation between a square and a convex polygon. The shape of the polygon can be anything. But it will always be convex. So is there any algorithm that would help in this transformation. –  user2092000 Feb 28 '13 at 14:20
    
The same basic idea will work on any convex polygon, regardless of the number of sides. You make a "ruled" surface by joining corresponding points on two polylines. In the example above the two polylines that we join by "rulings" are AB and CDE. I can write it up in more detail if you don't see the reasoning. –  bubba Feb 28 '13 at 14:43
    
I understood how u did it in your answer but the point is i have to implement it in a code. So I am finding it extremely difficult to code such a logic and i will have to let the code only to decide the number of optimal cuts to get enough triangles. –  user2092000 Feb 28 '13 at 14:57
    
What triangles? Pick two polygon sides to serve as the "left" and "right". The polylines in between these two become the "top" and the "bottom", P and Q. Parameterize P and Q (by arclength), as indicated above. In other words, write functions that return P(u) and Q(u) for a given u. Then use the mapping g. Your code will receive values (u,v) within the rectangle, and the function g will produce a point in the polygon. –  bubba Mar 1 '13 at 0:08
    
My apologies. I mixed up this answer with another one I was answering at the same time, so I mistakenly assumed that your polygon is convex. If the polygon is not convex, then you have to choose the "left" and "right" sides quite carefully, or else the algorithm won't work. In fact, it may be impossible to make a suitable choice. For convex polygons, the choice doesn't matter. –  bubba Mar 1 '13 at 2:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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