JavaScript – How to check if a shape is inside another curved shape?

I came across your post from a post I made recently.

Could this script/algorithm be modified to check whether text is inside a shape?

I'm looking for ways to mass center text in irregular shapes, with each shape having a single text box in it.

Finding a way to ensure that the text itself would physically be in the shape would help towards that path.

I currently have a script that will automatically place text in the 'center' of an object, but for some irregular shaped objects this causes the text to fall outside the boundry of the object itself.

Here is a technique that also may be useful for you : https://community.adobe.com/t5/illustrator/how-to-check-if-a-path-fits-inside-of-another-path/m-p/6348976?page=1

The basic idea is to turn the beziers into sets of points so they make a polygon (this can be a very fine polygon, and will take longer to process) and then compare each such point using raycasting algorithm to determine if any of the points are inside or outside the comparing polygon.

I've done a quick modification to Hiroyuki Sato's Divide script so that it divides paths based on an absolute distance, rather than number of divisions. The result will serve to approximate the curved paths with points approximately every n pts apart, and I hope you might be able to use for your purpose. Here's the modified script:

// Divide (length)

// divides each selected segment into specified number. based on the length.
// Length of each segment in each divided segments is equal.


// test env: Adobe Illustrator CS3, CS6 (Windows)

// Copyright(c) 2006 Hiroyuki Sato
// https://github.com/shspage
// This script is distributed under the MIT License.
// See the LICENSE file for details.

// 2018.07.20, modified to ignore locked/hidden objects in a selected group

// 2021.01.11, modified by m1b in attempt to divide paths based on an absolute distance
//             "targetSpecifier": "illustrator-25.064"


var ver10 = (version.indexOf('10') == 0);

// Settings ====================

var absoluteDistanceMode = true; // divides a path segment to keep approximately n pts distance between added points
var straightLinesOnlyMode = true; // convert curves to straight lines
var divisionsOrApproximateDistanceBetweenPoints = 10; // in absoluteDistanceMode it is the (approximate) distance between points, measured in pts, otherwise it is the number of divisions

// =============================

main();
function main() {
    var paths = [];
    getPathItemsInSelection(n, paths);
    if (paths.length < 1) return;

    var n = divisionsOrApproximateDistanceBetweenPoints; // default dividing number, or in absolute distance mode it is the (approximate) distance between points, measured in pts

    // =============================
    // not ver.10 : input a number with a prompt box
    // if (!ver10) {
    //     n = prompt("divide each selected segment into ... (based on its length)", n);
    //     if (!n) {
    //         return;
    //     } else if (isNaN(n) || n < 2) {
    //         alert("Please input a number greater than 1 with 1 byte characters.");
    //         return;
    //     }
    //     n = parseInt(n);
    // }

    var i, j, k, p, q;
    var pnts, len, ar, redrawflg;

    for (var h = 0; h < paths.length; h++) {
        redrawflg = false;
        pnts = [];
        p = paths[h].pathPoints;

        for (i = 0; i < p.length; i++) {
            j = parseIdx(p, i + 1);
            if (j < 0) break;
            if (!sideSelection(p[i], p[j])) continue;

            ar = [i];
            q = [p[i].anchor, p[i].rightDirection, p[j].leftDirection, p[j].anchor];

            if (absoluteDistanceMode) {
                var fullLen = getT4Len(q, 0);
                var n2 = Math.ceil(fullLen / (n + 1));
                len = fullLen / n2;
                $.writeln(i + ': fullLen = ' + fullLen + '\tlen = ' + len + '\tn2 = ' + n2);
            } else {
                len = getT4Len(q, 0) / n;
                n2 = n;
            }

            if (len <= 0) continue;

            redrawflg = true;

            for (k = 1; k < n2; k++) {
                ar.push(getT4Len(q, len * k));
            }
            pnts.push(ar);
        }
        if (redrawflg) addPnts(paths[h], pnts, false);
    }
    activeDocument.selection = paths;
}

// ----------------------------------------------
// addPnts: adds anchors to pathitem "pi"
// an example of usage:
/* var pi=activeDocument.selection[0];
var pnts = [ [0,  0.3,0.8,0.5],
             [3,  0.5] ];  // [ [i, t,t,t,t...],[i, t,t..
addPnts(pi,pnts,true);
 */
function addPnts(pi, pnts, need2sort) { // target pathItem, list, need to sort the parameters
    // pnts = [ [index,  t,t,t,t...],[index,  t,t..
    // items must be ordered by index
    // an item without t ([index]) is acceptable.  an empty allay is not acceptable.
    // an index out of bounds is acceptable.  the range of t is 0 < t < 1.
    var p = pi.pathPoints;
    var pnts2 = [];
    var adjNextLDir = 0;
    var adjFirstLDir = 0;
    var idx = (pi.closed && pnts[pnts.length - 1][0] == p.length - 1) ? 0 : pnts[0][0];
    var ar = pnts.shift();
    var nidx = ar.shift();
    var j, pnt, q;
    for (var i = idx; i < p.length; i++) {
        pnts2.push(getDat(p[i]));
        if (adjNextLDir > 0) {
            pnts2[pnts2.length - 1][2] = adjHanP(p[i], 0, 1 - adjNextLDir);
        }
        if (nidx == i) {
            if (ar.length > 0) {
                if (need2sort) {
                    ar.sort();
                    ar = getUniq(ar);
                }
                if (i == p.length - 1 && idx == 0) {
                    adjFirstLDir = ar[ar.length - 1];
                }
                pnts2[pnts2.length - 1][1] = adjHanP(p[i], 1, ar[0]),
                    ar.unshift(0);
                ar.push(1);
                nxi = parseIdx(p, i + 1);
                if (nxi < 0) break;
                q = [p[i].anchor, p[i].rightDirection,
                p[nxi].leftDirection, p[nxi].anchor];
                if (arrEq(q[0], q[1]) && arrEq(q[2], q[3])) {
                    for (j = 1; j < ar.length - 1; j++) {
                        pnt = bezier(q, ar[j]);
                        pnts2.push([pnt, pnt, pnt, PointType.CORNER]);
                    }
                } else {
                    for (j = 1; j < ar.length - 1; j++) {
                        pnts2.push(getDivPnt(q, ar[j - 1], ar[j], ar[j + 1]));
                    }
                }
                adjNextLDir = ar[ar.length - 2];
            } else {
                adjNextLDir = 0;
            }
            if (pnts.length > 0) {
                ar = pnts.shift();
                nidx = ar.shift();
            }
        } else {
            adjNextLDir = 0;
        }
    }
    if (adjFirstLDir > 0) pnts2[0][2] = adjHanP(p[0], 0, 1 - adjFirstLDir);
    if (pnts2.length > 0) applyData2AfterIdx(p, pnts2, idx - 1);
}
// ----------------------------------------------
function getUniq(ar) { // Array (sorted)
    if (ar.length < 2) return ar;
    var ar2 = [ar[0]];
    var torelance = 0.01;
    for (var i = 1; i < ar.length; i++) {
        if (ar[i] - ar2[ar2.length - 1] > torelance) ar2[ar2.length] = ar[i];
    }
    return ar2;
}
// ----------------------------------------------
// returns an array for properties of a pathpoint
function getDat(p) { // pathPoint
    with (p) return [anchor, rightDirection, leftDirection, pointType];
}
// ----------------------------------------------
// magnifies a handle by m
function adjHanP(p, n, m) { // p=pathpoint, n=0:leftDir, n=1:rightDir, m=magnification rate
    with (p) {
        var d = (n == 1 ? rightDirection : leftDirection);
        return [anchor[0] + (d[0] - anchor[0]) * m,
        anchor[1] + (d[1] - anchor[1]) * m];
    }
}
// ----------------------------------------------
// returns an array for properties of a pathpoint
// that corresponds to the parameter "t1"
// q=4 points, t0-2=parameters, anc=coordinate of anchor
function getDivPnt(q, t0, t1, t2, anc) {
    if (!anc) anc = bezier(q, t1);
    var r = defDir(q, 1, t1, anc, (t2 - t1) / (1 - t1));
    var l = defDir(q, 0, t1, anc, (t1 - t0) / t1);
    if (straightLinesOnlyMode) {
        return [anc, anc, anc, PointType.SMOOTH];
    } else {
        return [anc, r, l, PointType.SMOOTH];
    }
}
// ----------------------------------------------
// returns the [x, y] coordinate of the handle of the point on the bezier curve
// that corresponds to the parameter "t"
// q=4 points, t=paramter, anc=coordinate of anchor, m=magnification ratio
function defDir(q, n, t, anc, m) { // n=0:ldir, n=1:rdir
    var dir = [t * (t * (q[n][0] - 2 * q[n + 1][0] + q[n + 2][0]) + 2 * (q[n + 1][0] - q[n][0])) + q[n][0],
    t * (t * (q[n][1] - 2 * q[n + 1][1] + q[n + 2][1]) + 2 * (q[n + 1][1] - q[n][1])) + q[n][1]];
    return [anc[0] + (dir[0] - anc[0]) * m,
    anc[1] + (dir[1] - anc[1]) * m];
}
// ----------------------------------------------
// return the [x, y] coordinate on the bezier curve
// that corresponds to the paramter "t"
function bezier(q, t) {
    var u = 1 - t;
    return [u * u * u * q[0][0] + 3 * u * t * (u * q[1][0] + t * q[2][0]) + t * t * t * q[3][0],
    u * u * u * q[0][1] + 3 * u * t * (u * q[1][1] + t * q[2][1]) + t * t * t * q[3][1]];
}
// ----------------------------------------------
function applyData2Path(p, pnts) { // pathpoint, list
    // (format:[[ anchor, rightDirection, leftDirection, poinType ],...]
    if (pnts.length < 1) return;

    var pt;

    while (p.length > pnts.length) {
        p[p.length - 1].remove();
    }

    for (var i in pnts) {
        pt = i < p.length ? p[i] : p.add();
        with (pt) {
            anchor = pnts[i][0];
            rightDirection = pnts[i][1];
            leftDirection = pnts[i][2];
            pointType = pnts[i][3];
        }
    }
}
// ----------------------------------------------
function applyData2AfterIdx(p, pnts, idx) { // pathpoint, list, index
    if (idx == null || idx < 0) {
        applyData2Path(p, pnts);
        return;
    }
    var pt;

    while (p.length - 1 > idx) {
        p[p.length - 1].remove();
    }

    for (var i = 0; i < pnts.length; i++) {
        pt = p.add();
        with (pt) {
            anchor = pnts[i][0];
            rightDirection = pnts[i][1];
            leftDirection = pnts[i][2];
            pointType = pnts[i][3];
        }
    }
}

// ------------------------------------------------
// returns true, if a segment between pathpoints ps1 and ps2 is selected
function sideSelection(ps1, ps2) {
    return (ps1.selected != PathPointSelection.NOSELECTION
        && ps1.selected != PathPointSelection.LEFTDIRECTION
        && ps2.selected != PathPointSelection.NOSELECTION
        && ps2.selected != PathPointSelection.RIGHTDIRECTION);
}
// ------------------------------------------------
// if the contents of both arrays are equal, return true (lengthes must be same)
function arrEq(arr1, arr2) {
    for (var i in arr1) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}

// ------------------------------------------------
// return the bezier curve parameter "t"
// at the point which the length of the bezier curve segment
// (from the point start drawing) is "len"
// when "len" is 0, return the length of whole this segment.
function getT4Len(q, len) {
    var m = [q[3][0] - q[0][0] + 3 * (q[1][0] - q[2][0]),
    q[0][0] - 2 * q[1][0] + q[2][0],
    q[1][0] - q[0][0]];
    var n = [q[3][1] - q[0][1] + 3 * (q[1][1] - q[2][1]),
    q[0][1] - 2 * q[1][1] + q[2][1],
    q[1][1] - q[0][1]];
    var k = [m[0] * m[0] + n[0] * n[0],
    4 * (m[0] * m[1] + n[0] * n[1]),
    2 * ((m[0] * m[2] + n[0] * n[2]) + 2 * (m[1] * m[1] + n[1] * n[1])),
    4 * (m[1] * m[2] + n[1] * n[2]),
    m[2] * m[2] + n[2] * n[2]];

    var fullLen = getLength(k, 1);

    if (len == 0) {
        return fullLen;

    } else if (len < 0) {
        len += fullLen;
        if (len < 0) return 0;

    } else if (len > fullLen) {
        return 1;
    }

    var t, d;
    var t0 = 0;
    var t1 = 1;
    var torelance = 0.001;

    for (var h = 1; h < 30; h++) {
        t = t0 + (t1 - t0) / 2;
        d = len - getLength(k, t);

        if (Math.abs(d) < torelance) break;
        else if (d < 0) t1 = t;
        else t0 = t;
    }

    return t;
}

// ------------------------------------------------
// return the length of bezier curve segment
// in range of parameter from 0 to "t"
// "m" and "n" are coefficients.
function getLength(k, t) {
    var h = t / 128;
    var hh = h * 2;

    var fc = function (t, k) {
        return Math.sqrt(t * (t * (t * (t * k[0] + k[1]) + k[2]) + k[3]) + k[4]) || 0
    };

    var total = (fc(0, k) - fc(t, k)) / 2;

    for (var i = h; i < t; i += hh) {
        total += 2 * fc(i, k) + fc(i + h, k);
    }

    return total * hh;
}

// ------------------------------------------------
// extract PathItems from the selection which length of PathPoints
// is greater than "n"
function getPathItemsInSelection(n, paths) {
    if (documents.length < 1) return;

    var s = activeDocument.selection;

    if (!(s instanceof Array) || s.length < 1) return;

    extractPaths(s, n, paths);
}

// --------------------------------------
// extract PathItems from "s" (Array of PageItems -- ex. selection),
// and put them into an Array "paths".  If "pp_length_limit" is specified,
// this function extracts PathItems which PathPoints length is greater
// than this number.
function extractPaths(s, pp_length_limit, paths) {
    for (var i = 0; i < s.length; i++) {
        if (s[i].locked || s[i].hidden) {
            continue;
        } else if (s[i].typename == "PathItem") {
            if (pp_length_limit
                && s[i].pathPoints.length <= pp_length_limit) {
                continue;
            }
            paths.push(s[i]);

        } else if (s[i].typename == "GroupItem") {
            // search for PathItems in GroupItem, recursively
            extractPaths(s[i].pageItems, pp_length_limit, paths);

        } else if (s[i].typename == "CompoundPathItem") {
            // searches for pathitems in CompoundPathItem, recursively
            // ( ### Grouped PathItems in CompoundPathItem are ignored ### )
            extractPaths(s[i].pathItems, pp_length_limit, paths);
        }
    }
}

// ----------------------------------------------
// return pathpoint's index. when the argument is out of bounds,
// fixes it if the path is closed (ex. next of last index is 0),
// or return -1 if the path is not closed.
function parseIdx(p, n) { // PathPoints, number for index
    var len = p.length;
    if (p.parent.closed) {
        return n >= 0 ? n % len : len - Math.abs(n % len);
    } else {
        return (n < 0 || n > len - 1) ? -1 : n;
    }
}

The settings are these:

var absoluteDistanceMode = true; // divides a path segment to keep approximately n pts distance between added points
var straightLinesOnlyMode = true; // convert curves to straight lines
var divisionsOrApproximateDistanceBetweenPoints = 10; // in absoluteDistanceMode it is the (approximate) distance between points, measured in pts, otherwise it is the number of divisions

@HiroyukiSato Thanks for writing such terrific scripts! 🙂 Hope I haven't made too much of a mess of the above modification.

- Mark

Interesting problem. My first thought is to cause the script to approximate the curves with small straight line segments, by using say, Zig Zag or Scribble or something like that, with settings that add anchor points but don't actually deform the path. Another idea is to modify Hiroyuki Sato's script Divide to calculate the points for you. Then you'd be able to run your algorithm.

I'm interested to know how you go, so please post back if you get anywhere with it. Also wondered if you'd like to post the algorithm you ported from Java? - Mark