Subdivision of Four-Sided, 2D Shape

Question

I'm looking for an approach to splitting a four sided shape into a grid. For example:

Ultimately I need to be able to convert the resulting shapes to SVG, but I'm happy to handle conversion to/from another library or coordinate system. What I'm looking for is how to approach the calculation.

Assume the shape is a four-sided shape drawn quadratically where each side can be concave or convex, but no edges overlap with other edges or themselves and any of the four sides can be curved.

The same approach for a four-sided polygon (shape with straight edges is trivial), and if two opposed edges are straight lines, is is easy to find the intersecting points because they will lie along straight lines drawn between the subdivisions of the opposing sides. From there is is relatively easy to calculate the curve needed to join them to the previous point along the alternative axis:

However when there are not two straight, opposed sides (as in the third example above) I am unsure of how to find the points because there is no longer the certainty of the points lying along a straight line.

I've spent a long time looking for a documented approach, but to no avail.

Here is an example of the kind of starting shape using SVG to describe it (it doesn't have to processed in SVG, as long as I can output to SVG.

<svg version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
     viewBox="0 0 406.4 233.4" xml:space="preserve">
  <path class="st0" d="M394.3,232.7c-106-37.8-353.7,0-353.7,0s-90.4-151.2,0-207.3s353.7,0,353.7,0S420.3,154.7,394.3,232.7z"/>
</svg>

EDIT: I asked a similar question over at Stack Exchange Maths and one of the answers describes one approach - the use of a Coons Patch. Quora explaination here.

Answer 1

You can see the live example and full code on Codepen here.

Data representation

The simplest data representation of the image below uses Cubic Bézier curves. I believe that would also cover all of your use cases. In order not to pollute our code with various special cases, we will require the input to always be in the format of four subsequent Cubic Bézier curves as if we drew them. This means we cannot use:

• Quadractic Bézier curves (convertible to Cubic by mirroring the other control point)
• Segments (convertible to Cubic Bézier curve by placing the control points equidistantly between the endpoints on the line)
• Close path [Z SVG command] (convertible to Cubic Bézier curve by calculating the given segment and then taking it from there)

More on the subject of paths in SVG

Its SVG representation

<path d=" M50 50
     C 100 100 400 100 450 50
     C 475 250 475 250 450 450
     C 250 300 250 300 50 450
     C 150 100 150 250 50 50"
 fill="transparent"
 stroke="black"
/>

However, for convenience we will define our own datastructures.

Point is just a plain old Vector2D class.

class Point {
  constructor (x, y) {
    this.x = x
    this.y = y
  }
}

Curve is Cubic Bézier curve.

class Curve {
  constructor (
    startPointX, startPointY,
    controlPointAX, controlPointAY,
    controlPointBX, controlPointBY,
    endPointX, endPointY) {
    this.start = new Point(startPointX, startPointY)
    this.controlA = new Point(controlPointAX, controlPointAY)
    this.controlB = new Point(controlPointBX, controlPointBY)
    this.end = new Point(endPointX, endPointY)
  }

}

Grid is just a container for the curves.

class Grid {
  constructor (topSide, rightSide, bottomSide, leftSide, horizontalCuts, verticalCuts) {
    this.topSide = topSide
    this.rightSide = rightSide
    this.bottomSide = bottomSide
    this.leftSide = leftSide

    // These define how we want to slice our shape. Just ignore them for now
    this.verticalCuts = verticalCuts
    this.horizontalCuts = horizontalCuts
  }
}

Let's fill it with the same shape.

let grid = new Grid(
  new Curve(50, 50, 100, 100, 400, 100, 450, 50),
  new Curve(450, 50, 475, 250, 475, 250, 450, 450),
  new Curve(450, 450, 250, 300, 250, 300, 50, 450),
  new Curve(50, 450, 150, 100, 150, 250, 50, 50),
  8,
  6
)

Finding intersection points

Apparently you already implemented it using the t approach (as opposed to true curve splice length) so I am putting it here just for completness' sake.

Note that cuts is the actual number of the intersection points (red points) you'll get. That is, the starting point and ending point are not there (but with minor edits to cut() they can be)

function cut (cuts, callback) {
  cuts++
  for (let j = 1; j < cuts; j++) {
    const t = j / cuts
    callback(t)
  }
}

class Curve {

// ...

  getIntersectionPoints (cuts) {
    let points = []
    cut(cuts, (t) => {
      points.push(new Point(this.x(t), this.y(t)))
    })
    return points
  }

  x (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.start.x +
            3 * ((1 - t) * (1 - t)) * t * this.controlA.x +
            3 * (1 - t) * (t * t) * this.controlB.x +
            (t * t * t) * this.end.x
  }

  y (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.start.y +
            3 * ((1 - t) * (1 - t)) * t * this.controlA.y +
            3 * (1 - t) * (t * t) * this.controlB.y +
            (t * t * t) * this.end.y
  }
}

Finding the splitting curves

function lerp (from, to, t) {
  return from * (1.0 - t) + (to * t)
}

class Curve {

// ...

  getSplitCurves (cuts, oppositeCurve, fromCurve, toCurve) {
    let curves = []
    cut(cuts, (t) => {
      let start = new Point(this.x(t), this.y(t))
      // NOTE1: We must go backwards
      let end = new Point(oppositeCurve.x(1 - t), oppositeCurve.y(1 - t))
      let controlA = new Point(
        // NOTE2: Interpolate control points
        lerp(fromCurve.controlA.x, toCurve.controlA.x, t),
        lerp(fromCurve.controlA.y, toCurve.controlA.y, t)
      )
      let controlB = new Point(
        // NOTE2: Interpolate control points
        lerp(fromCurve.controlB.x, toCurve.controlB.x, t),
        lerp(fromCurve.controlB.y, toCurve.controlB.y, t)
      )
      curves.push(new Curve(
        start.x, start.y,
        controlA.x, controlA.y,
        controlB.x, controlB.y,
        end.x, end.y
      ))
    })
    return curves
  }
}

There are some fishy things with the code above.

NOTE1: Since the curves are represented in the order you draw them, the opposing sides face different directions. For instance, the top side is drawn left-to-right, but the bottom one right-to-left. Maybe an image will help:

NOTE2: This is how we get the control points for the Béziers splitting the shape. t interpolation on the segment connecting the control points of opposing sides.

Here are those segments. Their endpoints are the control points of respective curves.

This is the final result when we render the curves:

You can see the live example and full code on Codepen here.

Where to go from here

More intersections

This obviously isn't the final result. We still need to find the intersection points of the generated curves. However, finding the intersections of two Bezier curves is non-trivial. Here's a nice StackOverflow answer on the topic which will lead you to this neat library that will do the heavy lifting for you (look at the code of bezier3bezier3() and you'll understand)

Splitting the curves

Once you find the intersection points, you will want to find at which t they occur. Why t you ask? So you can split the curve.

The actual final result

At the end you'll need to pick those fractions of the curves and arrange them to represent individual fields of the grid.

As you can see, you still have a long journey to go, I only went a fraction of it (and still managed to write a lengthy answer :D ).

Answer 2

If your four sides are cubic Bezier curves, how about something relatively simple:

To make the horizontal dividers (from top to bottom), make new cubic Bezier curves by interpolating the control points of the top and bottom sides:

Then, divide the left and right sides into the same number of points..

..and stretch the divider curves so they connect to those points:

Then, do the same from left to right to create the vertical dividers.

Here is a pen to test different shapes: https://codepen.io/Sphinxxxx/pen/pKddee

The important parts are in BezierWrapper.lerpCurve() and BezierWrapper.fitCurve(), and also the Bezier class taken from https://gamedev.stackexchange.com/a/5427 to get evenly spaced points along a curve (.samples):

class BezierWrapper {
    constructor(controls, sampleCount, classname) {
        this.controls = controls;
        this.classname = classname;

        if(sampleCount) {
            function point2obj(p) {
                return { x: p[0], y: p[1] };
            }
            //https://gamedev.stackexchange.com/a/5427
            const interpolator = new Bezier(point2obj(controls[0]),
                                            point2obj(controls[1]),
                                            point2obj(controls[2]),
                                            point2obj(controls[3]));
            const samples = this.samples = [];
            for(let i = 1; i <= sampleCount; i++) {
                const t = i / (sampleCount+1);
                samples.push([interpolator.mx(t), interpolator.my(t)]);
            }
        }
    }

    static lerpCurve(source, target, t) {

        function lerpCoord(from, to, t) {
            const diffX = to[0] - from[0],
                  diffY = to[1] - from[1],
                  lerpX = from[0] + (diffX * t),
                  lerpY = from[1] + (diffY * t);
            return [lerpX, lerpY];
        }

        const middle = source.map((c, i) => lerpCoord(c, target[i], t));
        return middle;
    }

    static fitCurve(source, start, end) {

        function distance(p1, p2) {
            const dx = p2[0] - p1[0],
                  dy = p2[1] - p1[1];
            return Math.sqrt(dx*dx + dy*dy);
        }

        //https://gist.github.com/conorbuck/2606166
        function angle(p1, p2) {
            const dx = p2[0] - p1[0],
                  dy = p2[1] - p1[1],
                  radians = Math.atan2(dy, dx);
            return radians;
        }

        //https://stackoverflow.com/questions/2259476/rotating-a-point-about-another-point-2d
        function rotate(p, radians) {
            const x = p[0],
                  y = p[1],
                  cos = Math.cos(radians),
                  sin = Math.sin(radians);

            return [cos*x - sin*y, sin*x + cos*y];
        }

        const sourceStart = source[0],
              sourceEnd = source[3],
              scale = distance(start, end)/distance(sourceStart, sourceEnd),
              rot = angle(start, end) - angle(sourceStart, sourceEnd);

        //Translate, scale and rotate the source control points to make them fit the start and end points:
        const sourceNorm = source.map(c => [c[0] - sourceStart[0], c[1] - sourceStart[1]]),
              fittedNorm = sourceNorm.map(c => rotate([c[0]*scale, c[1]*scale], rot)),
              fitted = fittedNorm.map(c => [c[0] + start[0], c[1] + start[1]]);

        return fitted;
    }
}