1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Alexis Dufrenoy
    Feb 27, 2013 at 13:07
  • $\begingroup$ Your question is ambiguous. Could you add some details (picture would be the best, but it is not necessary)? $\endgroup$
    – dtldarek
    Feb 27, 2013 at 13:10
  • $\begingroup$ 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. $\endgroup$
    – user2092000
    Feb 27, 2013 at 13:30
  • 1
    $\begingroup$ Schwarz-Christoffel mappings will do this, even conformally, but they are computationally very expensive. $\endgroup$
    – mrf
    Feb 27, 2013 at 13:51
  • $\begingroup$ @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. $\endgroup$
    – user2092000
    Feb 27, 2013 at 13:58

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – user2092000
    Feb 28, 2013 at 14:20
  • $\begingroup$ 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. $\endgroup$
    – bubba
    Feb 28, 2013 at 14:43
  • $\begingroup$ 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. $\endgroup$
    – user2092000
    Feb 28, 2013 at 14:57
  • $\begingroup$ 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. $\endgroup$
    – bubba
    Mar 1, 2013 at 0:08
  • $\begingroup$ 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. $\endgroup$
    – bubba
    Mar 1, 2013 at 2:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .