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

Community Beginner ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

Hi

I’ve a Illustrator design with curved and nested shapes. I’ve created JavaScript for Illustrator to identify if a shape (foreach) is lying inside another shape, it is based on the algo posted by 56ka in post java - Algorithm to verify if a shape is inside another - javafx - Stack Overflow but I realized that it doesn’t work for curved shapes ☹ because this algo assumes straight lines between anchor points, see picture below where algo fails for checking s_0_0 inside s_1_1:

intersect.jpg

I wonder if somebody has overcome this type of problem for Illustrator JavaScript for design with curved and nested shapes if yes can share the used algo?

Thank you in advance for your help!

TOPICS
Scripting

Views

207

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines

correct answers 3 Correct Answers

Engaged , Jan 10, 2021 Jan 10, 2021
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. // tes...

Likes

translate

Translate

Translate
Adobe Community Professional , Jan 10, 2021 Jan 10, 2021
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.

Likes

translate

Translate

Translate
Adobe Community Professional , Jan 10, 2021 Jan 10, 2021
I posted the algorithm to a possible solution in the link provided above.   here's what I suggested back then "what if we have two paths, select them both and do a Path Finder Unite operation?   ...if we end up with a group, the test path is outside of the Container path (the Ellipse)   ...if we end up with the exact same path as the Ellipse, the test path was fully contained inside of it   ...if we end up with a path "different" than the starting Ellipse, then the test path was partially outsid...

Likes

translate

Translate

Translate
Engaged ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

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

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Engaged ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

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

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Adobe Community Professional ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

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/63...

 

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.

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Engaged ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

That looks really cool! I couldn't get the test to run though. The error was "Error Code# 21: undefined is not an object" on this line:

 

if (RayCaster.rayIntersectsSegment(new RayCaster.Point(point[0], point[1]), segment)) {

 

 

Does it work on your current system? - Mark

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Adobe Community Professional ,
Jan 11, 2021 Jan 11, 2021

Copy link to clipboard

Copied

It seems the new forums had mangled some of the code and removed the [i] accessors inside loops.

I went through the code and fixed it and edited the reply to the working version.

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Adobe Community Professional ,
Jan 10, 2021 Jan 10, 2021

Copy link to clipboard

Copied

I posted the algorithm to a possible solution in the link provided above.

 

here's what I suggested back then

"what if we have two paths, select them both and do a Path Finder Unite operation?

 

...if we end up with a group, the test path is outside of the Container path (the Ellipse)

 

...if we end up with the exact same path as the Ellipse, the test path was fully contained inside of it

 

...if we end up with a path "different" than the starting Ellipse, then the test path was partially outside

 

no math required."

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Community Beginner ,
Jan 24, 2021 Jan 24, 2021

Copy link to clipboard

Copied

Hi everybody and thank you for your replies and your time!

When looking at the proposed (sophisticated) algos I’m concerned about the processing time it would take to process all my shapes (>1000 in my current design, my code is currently not performance optimized). In the end, with your feedback, I’ll accept/ deal with the few exceptions for which the ‘standard’ ray-casting algo doesn’t work. Thank you again for your valuable feedbacks!

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Explorer ,
Feb 25, 2021 Feb 25, 2021

Copy link to clipboard

Copied

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.

Likes

translate

Translate

Translate

Report

Report
Community Guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines