# Subdividing a four-sided polygon with curved edges

I'm looking for an approach to subdividing a polygon into a grid. Obviously if the polygon had four straight sides, this is easy, but is there an approach when it has four curved sides?

The polygon will have the following properties:

• It will always have four sides
• The sides will never overlap each other or themselves.
• A side will never extend beyond the limits of the points at each of its ends along that axis.
• I'm afraid I don't have the correct language to describe the nature of the curves, but assume they always be fairly gentle curves that will never overlap themselves or do anything crazy.
• The subdivisions should be equal in terms of the distance between the two sides at any given point. As you can probably tell by my fumbling language, I'm not a mathematician, however I am a competent programmer. I'm looking for an approach to use in rendering shapes to screen.

Even if you can't give me a solution, some appropriate terminology to help me hunt one down would be appreciated. For example, is subdivision the correct name for what I'm trying to achieve?

• Hmm, if these shapes aren't convoluted, have you considered doing an affine transformation to convert them to a rectangle, drawing the standard grid, and reverting the transformation? – Sharky Kesa Jun 13 '18 at 7:54
• @SharkyKesa Thanks for the suggestion. The idea of creating a grid and then distorting it is an interesting one, though ultimately I need to describe each square as a vector shape, so I would have to preserve the information about the lines. Isn't an affine transformation going to result in straight edges though? – Undistraction Jun 13 '18 at 7:58
• This sounds like a biquadratic or bicubic patch, defined using 9 or 16 points (four of them corresponding to the four corners). See e.g. here. (Although they do not keep the subdivisions equal.) – Nominal Animal Jun 13 '18 at 15:00
• @Undistraction Sorry, I got slightly confused as to the generality of transformations that can be done with affine transformations. – Sharky Kesa Jun 14 '18 at 8:12
• @SharkyKesa No bother. This stuff is mind bending. – Undistraction Jun 19 '18 at 20:23

## 1 Answer

You can use a Coons patch to subdivide a quadrilateral with four two-dimensional or three-dimensional curved edges. Given the values of a function $f:\mathbb{R}^2\rightarrow\mathbb{R}^n$ (where $n$ is the dimension of your curve, either 2 or 3) over the boundary of the unit square, the Coons patch defines a mapping over the interior of the unit square that interpolates the known values of $f$ on the boundary of the unit square. The Coons patch formula is: \begin{align} f(u,v) &= (1-v)f(u,0) + vf(u,1) + (1-u)f(0,v) + uf(1,v) \\ & \qquad -(1-u)(1-v)f(0,0) - u(1-v)f(1,0) \nonumber\\ & \qquad -(1-u)v f(0,1) - uv f(1,1). \nonumber \end{align}

To use a Coons patch for subdividing a quadrilateral with curved edges, first define a parameterization of each of the curves over the unit interval. Then reverse the orientation of the first and last curved edge. Then $u$ will be the parameter value for the second and last curved edge and $v$ will be the parameter value for the first and third curved edge. You can now create a rectangular grid of points on the unit square and map these points to your quadrilateral with curved edges using the Coons patch mapping.

$f(u,0)$ is the point of the second curved edge at curve parameter value $u,$ $f(u,1)$ is the point of the last curved edge at curve parameter value $u,$ $f(0,v)$ is the point of the first curved edge at curve param value $v,$ etc.