Shape subdivision

index.html

<h2>Shape subdivision</h2>

<section id="app">
    <label>
        <span>Dividers</span>
        <input type="number" v-model.number="svg.dividers" min="1">
    </label>
    <svg :width="svg.size[0]" :height="svg.size[1]">
        <corner v-for="c in getCorners()" :c="c"></corner>
        <bezier v-for="b in getBeziers()" :wrapper="b" />

        <drag-node class="resizer" v-model="svg.size" :r="20"></drag-node>
    </svg>

    <details>
        <summary>Advanced</summary>
        <div>
            <label>
                <input type="radio" v-model="svg.divideByDist" :value="true">
                <span>Divide by distance</span>
            </label>
            <label>
                <input type="radio" v-model="svg.divideByDist" :value="false">
                <span>Divide by <i>t</i></span>
            </label>
            <label>
                <input type="checkbox" v-model="debugSinglePath">
                <span>Single path</span>
            </label>
        </div>
    </details>
</section>

<p>
    <a href="https://stackoverflow.com/questions/50784235/subdivision-of-four-sided-2d-shape">https://stackoverflow.com/questions/50784235/subdivision-of-four-sided-2d-shape</a>
</p>

<script>
    /**
     * https://gamedev.stackexchange.com/questions/5373/moving-ships-between-two-planets-along-a-bezier-missing-some-equations-for-acce
     * https://gamedev.stackexchange.com/a/5427
     */
    class Bezier {

        constructor(a, b, c, d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;

            this._samples = 20;
            this.arcLengths = new Array(this._samples + 1);
            this.arcLengths[0] = 0;

            let [x1, y1] = this.pointAtT(0),
                clen = 0,
                step = 1 / this._samples;
            for(var i = 1; i <= this._samples; i += 1) {
                const [x2, y2] = this.pointAtT(i * step);
                const dx = x1 - x2,
                      dy = y1 - y2;        
                clen += Math.hypot(dx, dy);
                this.arcLengths[i] = clen;

                x1 = x2, y1 = y2;
            }
            this.length = clen;    
        }

        pointAtDist(u) {
            const targetLength = u * this.length;
            let low = 0, high = this._samples, index = 0;
            while (low < high) {
                index = low + Math.trunc((high - low) / 2);
                if (this.arcLengths[index] < targetLength) {
                    low = index + 1;
                } else {
                    high = index;
                }
            }
            if (this.arcLengths[index] > targetLength) {
                index--;
            }

            const lengthBefore = this.arcLengths[index];
            let lerpIndex = index;
            if (targetLength > lengthBefore) {
                const lengthAfter = this.arcLengths[index + 1];
                lerpIndex += (targetLength - lengthBefore) / (lengthAfter - lengthBefore);
            }
            const t = lerpIndex / this._samples;
            return this.pointAtT(t);
        }

        pointAtT(t) {
            const _t = 1 - t;

            const x =    _t * _t * _t * this.a[0]
                   + 3 * _t * _t *  t * this.b[0]
                   + 3 * _t *  t *  t * this.c[0]
                   +      t *  t *  t * this.d[0];

            const y =    _t * _t * _t * this.a[1]
                   + 3 * _t * _t *  t * this.b[1]
                   + 3 * _t *  t *  t * this.c[1]
                   +      t *  t *  t * this.d[1];

            return [x, y];
        }
    }
</script>

script.babel

(function() {
    "use strict";
    console.clear();
    
    class Shape {
        constructor(corners) {
            this.corners = corners || [];
        }
    }
    
    class Corner {
        constructor(point, controlOffsets) {
            this.point = point;
            this.controlOffsets = controlOffsets;
        }
        
        absControls() {
            const center = this.point;
            return this.controlOffsets.map(x => [x[0] + center[0], x[1] + center[1]]);
        }
    }
    
    class BezierWrapper {
        constructor(controls, sampleCount, sampleByDist, classname) {
            this.controls = controls;
            this.classname = classname;

            if(sampleCount) {
                function point2obj(p) {
                    return 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(sampleByDist ? interpolator.pointAtDist(t) : interpolator.pointAtT(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;
        }
    }
    

    //Global state model. Can be changed from within Vue or from the outside.
    const _svgState = {
        size: [400, 400],
        shape: new Shape([
            new Corner(
                [65, 78],
                [ [-38, 79], [63, -52] ]
            ),
            new Corner(
                [336, 101],
                [ [-46, -57], [8, 76] ]
            ),
            new Corner(
                [113, 356],
                [ [-83, -40], [56, -53] ]
            ),
            new Corner(
                [282, 248],
                [ [-52, -37], [30, -59] ]
            )
        ]),
        dividers: 3,
        divideByDist: true,
    };


    Vue.component('drag-node', {
        template: '<circle data-draggable @dragging="onDragging" :cx="absCoord[0]" :cy="absCoord[1]" :r="r" />',
        props: {
            coord: Array,
            //If 'coord' is relative to some other point:
            offsetCenter: Array,

            r: {
                default: 16,
            }
        },
        model: {
            prop: 'coord',
            event: 'do_it',
        },
        computed: {
            absCoord() {
                const point = this.coord,
                      center = this.offsetCenter,
                      absCoord = center ? [ point[0] + center[0], point[1] + center[1] ]
                                        : point;
                return absCoord;
            },
        },
        methods: {
            onDragging(e) {
                const point = e.detail.pos,
                      center = this.offsetCenter,
                      relCoord = center ? [ point[0] - center[0], point[1] - center[1] ]
                                        : point;
                this.$emit('do_it', relCoord);
            },
        },
    });

    Vue.component('connector', {
        template: '<line class="connector" :x1="start[0]" :y1="start[1]" :x2="end[0]" :y2="end[1]" />',
        props: ['start', 'end'],
    });

    Vue.component('bezier', {
        template:
`<g class="bezier" :class="wrapper.classname">
    <path :d="pathData" />
    <rect v-for="s in wrapper.samples" :x="s[0]-2" :y="s[1]-2" width="4" height="4" />
</g>`,
        props: ['wrapper'],
        computed: {
            pathData() {
                const cs = this.wrapper.controls;
                return `M${cs[0]} C${cs[1]} ${cs[2]} ${cs[3]}`;
            }
        },
    });

    Vue.component('corner', {
        template:
`<g class="corner">
    <connector :start="c.point" :end="absControls[0]" />
    <connector :start="c.point" :end="absControls[1]" />
    <drag-node class="corner-point"   v-model="c.point"  />
    <drag-node class="corner-control" v-model="c.controlOffsets[0]" :offsetCenter="c.point" />
    <drag-node class="corner-control" v-model="c.controlOffsets[1]" :offsetCenter="c.point" />
</g>`,
        props: {
            c: Object,
        },
        computed: {
            absControls() {
                return this.c.absControls();
            },
        },
        methods: {
        },
    });

    new Vue({
        el: '#app',
        data: {
            svg: _svgState,
            debugSinglePath: false,
        },
        computed: {
        },
        methods: {
            getCorners() {
                const corners = this.svg.shape.corners;
                if(this.debugSinglePath) {
                    return corners.slice(0, 2);
                }
                return corners;
            },
            getBeziers() {
                const corners = this.svg.shape.corners,
                      endpoints = corners.map(x => x.point),
                      controls = corners.map(x => x.absControls()),
                      dividers = this.svg.dividers;
                
                const ctlTop    = [endpoints[0], controls[0][1], controls[1][0], endpoints[1]],
                      ctlBottom = [endpoints[2], controls[2][1], controls[3][0], endpoints[3]],
                      ctlLeft   = [endpoints[0], controls[0][0], controls[2][0], endpoints[2]],
                      ctlRight  = [endpoints[1], controls[1][1], controls[3][1], endpoints[3]];
                if(this.debugSinglePath) {
                    return [new BezierWrapper(ctlTop, dividers, this.svg.divideByDist)];
                }
                
                const ctlDividersHoriz = [],
                      ctlDividersVert = [];
                for(let i = 1; i <= dividers; i++) {
                    const t = i / (dividers+1),
                          ctlHoriz = BezierWrapper.lerpCurve(ctlTop, ctlBottom, t),
                          ctlVert  = BezierWrapper.lerpCurve(ctlLeft, ctlRight, t);
                    ctlDividersHoriz.push(ctlHoriz);
                    ctlDividersVert.push(ctlVert);
                }
                
                const byDist = this.svg.divideByDist;
                const bezTop    = new BezierWrapper(ctlTop,    dividers, byDist),
                      bezBottom = new BezierWrapper(ctlBottom, dividers, byDist),
                      bezLeft   = new BezierWrapper(ctlLeft,   dividers, byDist),
                      bezRight  = new BezierWrapper(ctlRight,  dividers, byDist);
                
                const bezDividersHoriz = ctlDividersHoriz.map((c, i) => {
                    const fitted = BezierWrapper.fitCurve(c, bezLeft.samples[i], bezRight.samples[i]);
                    return new BezierWrapper(fitted, 0, false, 'divider');
                });
                const bezDividersVert = ctlDividersVert.map((c, i) => {
                    const fitted = BezierWrapper.fitCurve(c, bezTop.samples[i], bezBottom.samples[i]);
                    return new BezierWrapper(fitted, 0, false, 'divider');
                });

                return [bezTop, bezBottom, bezLeft, bezRight].concat(bezDividersHoriz).concat(bezDividersVert);
            }
        },
        filters: {
            prettyCompact: function(obj) {
                if(!obj) return '';
                const pretty = JSON.stringify(obj, null, 2),
                      //Collapse simple arrays (arrays without objects or nested arrays) to one line:
                      compact = pretty.replace(/\[[^[{]*?]/g, (match => match.replace(/\s+/g, ' ')))

                return compact;
            }
        },
    });


    //Vue replaces the original <svg> element, so we must wait until now to enable dragging:
    dragTracker({
        container: document.querySelector('#app svg'), 
        selector: '[data-draggable]',
        callback: (node, pos) => {
            //var event = new CustomEvent('dragging', { detail: { pos } });
            var event = document.createEvent('CustomEvent');
            event.initCustomEvent('dragging', true, false, { pos });

            node.dispatchEvent(event);
        },
    });

})();

scripts

<script src="https://cdnjs.cloudflare.com/ajax/libs/vue/2.5.3/vue.min.js"></script>
<script src="https://unpkg.com/drag-tracker@1"></script>

shape-subdivision.markdown

Shape subdivision

https://stackoverflow.com/questions/50784235/subdivision-of-four-sided-2d-shape

A Pen by Andreas Borgen on CodePen.

License.

style.scss

body {
    display: flex;
    margin: 0;
    min-height: 100vh;
    flex-flow: column nowrap;
    align-items: center;
    font-family: Georgia, sans-serif;
    
    h2 {
        font-size: 1.1em;
        text-align: center;
    }
    input {
        font-size: inherit;
    }
}

#app {
    display: flex;
    flex-flow: column nowrap;
    align-items: flex-start;
    gap: .5em;
    
    summary, label {
        cursor: pointer;
    }
    label {
        display: block;
        
        input[type="number"] {
            width: 3em;
        }
    }
}

svg {
    $border-color: #aaa;
    
    //Keeps the nodes draggable if they go outside the SVG area:
    position: relative;
    overflow: visible;

    background: white;
    outline: 3px dashed $border-color;

    .connector, .bezier {
        stroke-width: 2;
        fill: none;
        pointer-events: none;
    }
    .connector {
        stroke: dodgerblue;
        stroke-dasharray: 8;
    }
    .bezier {
        stroke: black;
        &.divider {
            stroke: limegreen;
        }

        rect {
            stroke: orange;
            //stroke-width: 1;
        }
    }

    [data-draggable] {
        stroke: black;
        stroke-width: 2;
        stroke-dasharray: 6 4;
        fill: transparent;
        cursor: move;

        &.corner-control {
            stroke: dodgerblue;
        }
        &.resizer {
            stroke: $border-color;
            fill: rgba($border-color, .5);
        }
    }
}