CODEWITHSUNDEEP
algorithmpolygon
kubaork
kubaork

Reputation: 161

Algorithm for transforming polygon with points inside

Sorry, if this is a duplicate. I was trying to find this in Google and Stackoverflow but I couldn't find it. Maybe I can't name correctly what I am looking for.

Let's say that I have a square and inside there are points. Than I change it's points to make quadrangle. How I can now get new coordinates of points after transform? enter image description here

Upvotes: 0

Views: 331

Answers (1)

such
such

Reputation: 603

There exist a canonical method for a unit square (a square with one corner at origo and sides of length 1) because coordinates of a point (x,y) can be used directly for interpolating within a skewed quadrangle with points at q00 (which corresponds to origo (x=0, y=0)), q01 for (x=0, y=1), q10 for (x=1, y=0) and q11 for (x=1, y=1). The transformed point is the bilinear interpolation:

p = (1-x)*(1-y)*q00 + x*(1-y)*q10 + (1-x)*y*q01 + x*y*q11

A generalisation of this is to compute p as a weighted mean of the polygon corners (the weights must sum to 1). The weights for the quadrangle based on the unit square is:

w = { (1-x)*(1-y); x*(1-y); (1-x)*y; x*y }
q = { q00; q10; q01; q11 }
p = w * q

Where w * q is a dot product. Weights for a triangle are computed by solving p0 = w * q0 for sum(w)=1, where p0 is the original point and q0 are the original corner points.

The general case with a polygon has multiple solutions. One way that works quite ok (in a simple test I did) is to form triangles from all triplets of corners in the polygon that covers a given point, compute the weights of the triangles, and use their combined weight over all corners as w in p = w * q.

Upvotes: 1

Related Questions