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.

enter image description here

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?

  • $\begingroup$ 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? $\endgroup$ Jun 13 '18 at 7:54
  • $\begingroup$ @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? $\endgroup$ Jun 13 '18 at 7:58
  • $\begingroup$ 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.) $\endgroup$ Jun 13 '18 at 15:00
  • $\begingroup$ @Undistraction Sorry, I got slightly confused as to the generality of transformations that can be done with affine transformations. $\endgroup$ Jun 14 '18 at 8:12
  • $\begingroup$ @SharkyKesa No bother. This stuff is mind bending. $\endgroup$ Jun 19 '18 at 20:23

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.


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.