Trying to figure out if a curved path can constitute a portion of a perfect circle

[Eduard Buta]

Hello community,

I've been trying to use scripting to find out if a user-selected curved path (formed from two anchor points) can be part of a perfect circle, and if so, draw the circle with the appropriate circumference on the artboard.

It's a pretty complex topic that (in my mind) requires some mathematical knowledge to figure out. I've found the following article that does a pretty good job explaining how a circle can be approximated based on a cubic Bezier curve. However, I got stuck pretty early on because I didn't know exactly how to translate the two anchor point path I have on the screen into the four control points that form a cubic Bezier curve. Especially when it comes to referencing such coordinates via scripting.

Hoping that some of your bright minds might want to jump in on the challenge!

[Jacob Bugge]

Eduard,

As Kurt would have already told you, had he seen this before now, there are no perfect circles.

"I've been trying to use scripting to find out if a user-selected curved path (formed from two anchor points) can be part of a perfect circle, and if so, draw the circle with the appropriate circumference on the artboard."

Those made in applications based on Bezier curves have four Anchor Points a quarter of a circle apart, at they actually have eight symmetrical(ly placed) bulges, so it is even impossible to fit a curved path into such a circle unless the path is exactly a quarter of a circle, in which case it is easy of course.

[Eduard Buta]

Thank you for your response, Jacob.

To clarify a few things. I only used the term "perfect circle" to make it clear that I'm trying to figure out if a path can form a circle, not just any elliptical shape.

Also, I'm not trying to fit a path into a circle, I'm trying to see if an existing path, if extended given its curvature, can form a circle. I am not sure if the approach in the article is even right for the task at hand, but it was the best I could find as a starting point for my problem. Sergey's answer below does a pretty good job of visually demonstrating what I'm trying to do.

[femkeblanco]

The approximation in the link is only for a "unit right" circular arc, that is to say, an arc with a radius of 1 and an angle of 90°, or a quarter circle.  I presume you are dealing with arcs of unknown angles and radii, which is not as straightforward. 

[Eduard Buta]

Indeed. However, I was first trying to get it working for this particular use case you described, and figure out if it can then be tweaked for the more non-straightforward cases. I was pretty much counting on this part:

Q. What if we divide the circle into more than four arcs? 

A. We can achieve an arbitrarily-good approximation that way. Even a chord approximation can become arbitrarily good if the circle is subdivided into enough arcs.

[Sergey Osokin]

Please clarify the task. Do you want to determine from the anchor points and handles of the arcs shown in the screenshot that they are part of a "perfect circle" and draw such a circle?

[Eduard Buta]

Yes, @Sergey Osokin . This is pretty much what I meant to do! Thanks for the great visual example!

[Nicky G.]

You can do this in 2 seconds with an Astute Graphics plugin, do the geometric construction starting from a curve passing through two points, determining the center of the circle etc. it is a rather long, difficult operation and is always imprecise.
It is rightly a simple and essential function that dear Adobe has never given us the honor of integrating natively into AI. I wonder why! Mama Adobe cares a lot about her children, grandchildren and family it seems

[Eduard Buta]

I know there are plugins that do this, but thanks for the recommendation anyway. My plan is to integrate this script into something a bit more complex, that fits a specific use case I have in mind. So I need to keep looking for solutions to do this via scripting.

[Kurt Gold]

Eduard, one thing that may have to be clarified is if you already created some code to achieve what you want. If so, you could post it for inspection.

Or are you just looking for someone who may write the appropriate code for you?

[m1b]

Hi all, I got intrigued by this problem.

My idea to solve it is to find the intersection of a ray normal (perpendicular to the tangent) to the start and end points of the path segment. If the segment is circular, then the distance from the intersection and the start and end points should be the same (within a tolerance value). For extra check I test the distance between the halfway point of the segment and the intersection point too. If all good, we draw a circle centred on the intersection point.

It seems to work! The colored circles are generated by the script:

There are some fiddly bits, such as trying not to draw two almost-identical circles. @Eduard Buta, if this code is useful to you, you almost certainly won't need all of it; just consider it a demonstration. Hope it's useful.

- Mark

/**
 * Demonstration of technique for checking if a path segment
 * is circular, and drawing circles where they are.
 * @author m1b
 * @discussion https://community.adobe.com/t5/illustrator-discussions/trying-to-figure-out-if-a-curved-path-can-constitute-a-portion-of-a-perfect-circle/m-p/14239684
 */
(function () {

    var doc = app.activeDocument;
    drawCirclesForSegments(doc, doc.selection);

})();


/**
 * Draws a circle to match any circular
 * path segments of `pageItems`.
 * @author m1b
 * @version 2023-11-18
 * @param {Document} doc - an Illustrator Document.
 * @param {PageItem|Array<PageItem>} pageItems - Any container of path items.
 * @param {Number} tolerance - the absolute tolerance used to determine if a circle is circular (default: 0.1).
 */
function drawCirclesForSegments(doc, pageItems, tolerance) {

    if (tolerance == undefined)
        tolerance = 0.1;

    var items = getPathItems(pageItems),
        alreadyDrawn = {};

    for (var i = 0; i < items.length; i++) {

        var item = items[i];

        for (var j = 0, len = item.pathPoints.length - 1; j <= len; j++) {

            var p1 = item.pathPoints[j],
                p2 = j < len ? item.pathPoints[j + 1] : item.pathPoints[0];

            // check if the segment is circular
            var circular = segmentIsCircular(p1, p2, tolerance);

            // this gives a rough description of the circle
            // so we can make sure we don't draw it twice
            var sameCircle = stringify(circular, -1);

            if (
                circular == undefined
                || alreadyDrawn[sameCircle] == true
            )
                continue;

            // draw circle
            var circle = drawCircle(doc, circular.center, circular.radius);

            // mark this as drawn already
            alreadyDrawn[sameCircle] = true;

            var isDemo = true;
            if (isDemo)
                // just for demonstration purposes only!
                circle.fillColor = doc.swatches[4 + j].color;

        }

    }

};


/**
 * Stringifier for purposes of
 * differentiating between objects.
 * @author m1b
 * @version 2023-11-18
 * @param {*} obj - the object to stringify
 * @param {Number} precision - the number of decimal places to round numbers, can be negative.
 * @returns {String}
 */
function stringify(obj, precision) {

    if (precision == undefined)
        precision = 0;

    var str = '';
    if (obj == undefined)
        str += obj;

    else if (obj.constructor.name === 'Array')
        for (var i = 0; i < obj.length; i++)
            str += stringify(obj[i], precision);

    else if (obj.constructor.name === 'Object') {

        for (var key in obj)
            if (obj.hasOwnProperty(key))
                str += stringify(obj[key], precision);

    }

    else if (obj.constructor.name === 'Number') {
        str += String(round(obj, precision));
    }

    else
        str += String(obj);

    return str;

};


/**
 * Determines if a segment (PathPoints p1 and p2)
 * is circular. If so, will return the center
 * position and radius of the circle.
 * @author m1b
 * @version 2023-11-18
 * @param {PathPoint} p1 - the first point of the segment.
 * @param {PathPoint} p2 - the last point of the segment.
 * @param {Number} tolerance
 */
function segmentIsCircular(p1, p2, tolerance) {

    if (tolerance == undefined)
        tolerance = 0.1;

    // can't be circular if no control points
    if (
        arraysAreEqual(p1.anchor, p1.rightDirection)
        || arraysAreEqual(p2.anchor, p2.leftDirection)
    )
        return;

    // find the intersection of rays normal to the two anchor points
    var intersectionPoint = bezierIntersection(
        p1.anchor,
        p1.rightDirection,
        p2.leftDirection,
        p2.anchor
    );

    var halfwayPoint = bezierPointAtT(
        p1.anchor,
        p1.rightDirection,
        p2.leftDirection,
        p2.anchor,
        0.5
    );

    // check length between intersection point and of start middle and end points
    var r1 = distanceBetweenPoints(intersectionPoint, p1.anchor),
        r2 = distanceBetweenPoints(intersectionPoint, p2.anchor),
        r3 = distanceBetweenPoints(intersectionPoint, halfwayPoint);

    var isCircle = range([r1, r2, r3]) < tolerance;

    if (isCircle)
        return {
            center: intersectionPoint,
            radius: r2,
        };

};


/**
 * Returns the position of the intersection between
 * rays normal to the start and end of the bezier.
 * @author ChatGPT 3.5 and m1b
 * @param {Array<Number>} p0 - point 1 of bezier curve [x, y].
 * @param {Array<Number>} p1 - point 2 of bezier curve [x, y].
 * @param {Array<Number>} p2 - point 3 of bezier curve [x, y].
 * @param {Array<Number>} p3 - point 4 of bezier curve [x, y].
 * @returns {Array<Number>} - [x, y].
 */
function bezierIntersection(p0, p1, p2, p3) {

    // calculate the normal angles at the start and end of the curve
    var startAngleRad = bezierNormalAngle(p0, p1, p2, p3, 0, false);
    var endAngleRad = bezierNormalAngle(p0, p1, p2, p3, 1, false);

    // calculate the slopes of the lines normal to the start and end points
    var startSlope = Math.tan(startAngleRad + Math.PI / 2);
    var endSlope = Math.tan(endAngleRad + Math.PI / 2);

    // calculate the y intercepts of the lines
    var startYIntercept = p0[1] - startSlope * p0[0];
    var endYIntercept = p3[1] - endSlope * p3[0];

    // calculate the intersection point
    var xIntersection = (startYIntercept - endYIntercept) / (endSlope - startSlope);
    var yIntersection = startSlope * xIntersection + startYIntercept;

    return [xIntersection, yIntersection];

};


/**
 * Returns the position of a point at `t`
 * on the bezier curve (p0,p1,p2,p3).
 * @author ChatGPT 3.5
 * @param {Array<Number>} p0 - point 1 of bezier curve [x, y].
 * @param {Array<Number>} p1 - point 2 of bezier curve [x, y].
 * @param {Array<Number>} p2 - point 3 of bezier curve [x, y].
 * @param {Array<Number>} p3 - point 4 of bezier curve [x, y].
 * @param {Number} t - parameter 0..1 where 0 is start and 1 is end of curve.
 * @returns {Array<Number>} - [x,y].
 */
function bezierPointAtT(p0, p1, p2, p3, t) {

    var u = 1 - t,
        tt = t * t,
        uu = u * u,
        uuu = uu * u,
        ttt = tt * t,

        p = [];

    p[0] = uuu * p0[0] + 3 * uu * t * p1[0] + 3 * u * tt * p2[0] + ttt * p3[0];
    p[1] = uuu * p0[1] + 3 * uu * t * p1[1] + 3 * u * tt * p2[1] + ttt * p3[1];

    return p;

};


/**
 * Returns the normal angle (perpendicular to tangent) at `t`
 * in either radians (default) or degrees.
 * @param {Array<Number>} p0 - point 1 of bezier curve [x, y].
 * @param {Array<Number>} p1 - point 2 of bezier curve [x, y].
 * @param {Array<Number>} p2 - point 3 of bezier curve [x, y].
 * @param {Array<Number>} p3 - point 4 of bezier curve [x, y].
 * @param {Number} t - parameter 0..1 where 0 is start and 1 is end of curve.
 * @param {Boolean} convertToDegrees - whether to convert to degrees (default: false).
 * @returns {Number} - [x,y].
 */
function bezierNormalAngle(p0, p1, p2, p3, t, convertToDegrees) {

    var smidgeon = 1e-5,

        // tiny amount on either side
        t1 = Math.max(0, t - smidgeon),
        t2 = Math.min(1, t + smidgeon),

        point1 = bezierPointAtT(p0, p1, p2, p3, t1),
        point2 = bezierPointAtT(p0, p1, p2, p3, t2),

        // 90°
        dx = point2[0] - point1[0],
        dy = point2[1] - point1[1],

        // Calculate the angle in radians
        angleRad = Math.atan2(dy, dx);

    if (convertToDegrees === true)
        return (angleRad * 180) / Math.PI;
    else
        return angleRad;

};


/**
 * Returns distance between two points.
 * @author m1b
 * @version 2022-07-25
 * @param {Array} p1 - a point array [x, y].
 * @param {Array} p2 - a point array [x, y].
 * @returns {Number} - distance in points.
 */
function distanceBetweenPoints(p1, p2) {

    var a = p1[0] - p2[0];
    var b = p1[1] - p2[1];

    return Math.abs(Math.sqrt(a * a + b * b));

};


/**
 * Draws and returns a circle.
 * @param {Document} doc - an Illustrator Document.
 * @param {Array<Number>|PathPoint} c - center of circle [cx, cy].
 * @param {Number} radius - radius of circle.
 * @returns {PathItem}
 */
function drawCircle(doc, center, radius, appearance) {

    if (center.hasOwnProperty('anchor'))
        center = center.anchor;

    var circle = doc.pathItems.ellipse(-(-center[1] - radius), center[0] - radius, radius * 2, radius * 2);

    return circle;

};


/**
 * Returns the range of an array of numbers,
 * ie. the difference between the highest
 * and lowest members of the array.
 * @param {Array} arr - the array.
 * @returns {Number}
 */
function range(arr) {

    if (arr.length == 0)
        return 0;

    return Math.max.apply(null, arr) - Math.min.apply(null, arr);

};


/**
 * Returns true when arrays are equal.
 * @param {Array} arr1 - an array of comparable objects.
 * @param {Array} arr2 - an array of comparable objects.
 * @returns {Boolean}
 */
function arraysAreEqual(arr1, arr2) {

    if (arr1.length != arr2.length)
        return false;

    for (var i = 0; i < arr1.length; i++)
        if (arr1[i] !== arr2[i])
            return false;

    return true;

};


/**
 * Rounds a single number or an array of numbers.
 * @author m1b
 * @version 2022-08-02
 * @param {Number|Array<Number>} nums - a Number or Array of Numbers.
 * @param {Number} [places] - round to this many decimal places (default: 0).
 * @return {Number|Array<Number>} - the rounded Number(s).
 */
function round(nums, places) {

    if (places == undefined)
        places = 0;

    places = Math.pow(10, places);

    var result = [];

    if (nums.constructor.name != 'Array')
        nums = [nums];

    for (var i = 0; i < nums.length; i++)
        result[i] = Math.round(nums[i] * places) / places;

    return nums.length == 1 ? result[0] : result;

};


/**
 * Returns every PathItem found
 * in `container`
 * @author m1b
 * @date 2023-11-18
 * @param {*} container - any Illustrator DOM object that can contain path items.
 * @returns {Array<PathItem>}
 */
function getPathItems(container) {

    var items = [];

    if (container.constructor.name == 'Array')
        for (var i = 0, len = container.length; i < len; i++)
            items = items.concat(getPathItems(container[i]));

    else if (container.constructor.name == 'GroupItem')
        for (var i = 0, len = container.pageItems.length; i < len; i++)
            items = items.concat(getPathItems(container.pageItems[i]));

    else if (container.constructor.name == 'CompoundPathItem')
        for (var i = 0, len = container.pathItems.length; i < len; i++)
            items = items.concat(getPathItems(container.pathItems[i]));

    else if (container.constructor.name == 'PathItem')
        items.push(container);

    return items;

};

Edit 2023-11-20: just added the isDemo variable to make the meaning explicit: this is just a demo—you will want to do something else with the results.

[Kurt Gold]

Excellent, Mark.

Thanks for sharing.

[renél80416020]

Bonjour Marc,
Félicitation pour ce script qui est vraiment bien conçu et d'une efficacité sans faille.
Vu le temps passé pour la réalisation, c'est un très beau cadeau!
Coïncidence, je viens de travailler sur le même sujet (même méthode) mais mon script est limité aux arcs isolés.
René

[m1b]

Thanks René, you are very kind. I am pleased to hear from you. I think I am getting better at structure of the code, even if I leave the hard parts to others. 🙂

- Mark

[femkeblanco]

My thinking was similar to @m1b , except I wasted my time doing the math long hand.  As far as I can tell, the math is correct, any desired result depending on the tolerance (line 1). 

var tolerance = 1;  // points
var doc = app.activeDocument;
var pathItems = doc.selection;
for (var i = 0; i < pathItems.length; i++) {
    main(pathItems[i])
}

function main(pathItem) {
    var points = pathItem.pathPoints;
    var P0 = points[0].anchor;
    var P1 = points[0].rightDirection;
    var P2 = points[1].leftDirection;
    var P3 = points[1].anchor;

    // handles, i.e. distances between (1) P0 and P1 and (2) P2 and P3
    var handle1 = Math.sqrt(
        (P0[0] - P1[0]) * (P0[0] - P1[0]) + (P0[1] - P1[1]) * (P0[1] - P1[1])
    );
    var handle2 = Math.sqrt(
        (P2[0] - P3[0]) * (P2[0] - P3[0]) + (P2[1] - P3[1]) * (P2[1] - P3[1])
    );

    // theta / 2 is angle between handle and line between anchors
    var opposite1 = P1[1] - P0[1];
    var adjacent1 = P1[0] - P0[0];
    var angle1 = Math.atan2(opposite1, adjacent1);
    var opposite2 = P3[1] - P0[1];
    var adjacent2 = P3[0] - P0[0];
    var angle2 = Math.atan2(opposite2, adjacent2);
    var theta = (angle1 - angle2) * 2;
    if (opposite2 < 0) {
        theta = theta * -1;
    }

    // radii, if arc were circular
    var alpha = 4 / 3 * Math.tan(theta / 4);
    var R = handle1 / alpha;

    // midpoint of curve
    var M = [
        (P0[0] + 3 * P1[0] + 3 * P2[0] + P3[0]) / 8,
        (P0[1] + 3 * P1[1] + 3 * P2[1] + P3[1]) / 8
    ];

    // midpoint of line between anchors
    var Q = [(P0[0] + P3[0]) / 2, (P0[1] + P3[1]) / 2];

    // centre of circle
    var opposite = R * Math.sin(theta / 2);
    var adjacent = R * Math.cos(theta / 2);
    var dx1 = Q​[0] - P0[0];
    var dy1 = Q[1] - P0[1];
    var angle1 = Math.atan(dx1 / dy1​);
    var angle2 = Math.PI / 2 - angle1;
    var dx2 = adjacent * Math.sin(angle2);
    var dy2 = adjacent * Math.cos(angle2);
    var O = [Q[0] + dx2, Q[1] - dy2];

    // distances between M and O
    var MO = Math.sqrt(
        (M[0] - O[0]) * (M[0] - O[0]) + (M[1] - O[1]) * (M[1] - O[1])
    );

    // true radii
    R1 = Math.sqrt(
        (O[0] - P0[0]) * (O[0] - P0[0]) + (O[1] - P0[1]) * (O[1] - P0[1])
    );
    R2 = Math.sqrt(
        (O[0] - P3[0]) * (O[0] - P3[0]) + (O[1] - P3[1]) * (O[1] - P3[1])
    );

    if (areEqual(R1, MO) &&
        areEqual(R2, MO)) {
            var circle = doc.pathItems.ellipse(
                O[1] + R, O[0] - R, R * 2, R * 2
            );
            circle.zOrder(ZOrderMethod.SENDTOBACK);
            circle.strokeColor = doc.swatches["Black"].color;
            circle.filled = false;
    }

    function areEqual(a, b) {
        return Math.abs(a - b) < tolerance;
    }
}

[Kurt Gold]

That's excellent as well, Femke.

Just one note: The line:

doc.swatches["Black"].color;

may declare an error if one is using a non-English version of Illustrator.

[femkeblanco]

Thanks @Kurt Gold .  The line can be deleted if it's causing an error. 

[m1b]

Thanks @femkeblanco, this is great! I wish my maths were as good as yours. I just took the mathy parts from "the shoulders of giants", as I usually do. Alas. Still, it was fun to make, and I'm sure you had fun too. 🙂

- Mark

[Jacob Bugge]

Femke, Sergey, Mark,

I knew that Eduard was after a scripting solution, but I had a look at how I should prefer to do it.

And then I wondered how close that would be to a scripting solution.

If I needed to find out for a few curves, my choice would be to just draw the few simple bits (using Smart Guides, Line Segment Tool, Document Info, Transform palette) and let Illy make the calculations and measurements for my assessment, much like the proof of the pudding, or the duck.

The images show the way I chose, working on a copy that was rotated to have the end Anchor Points aligned horizontally, and:

Optionally looking at the two Handles H1 and H2 in red hopefully identical (within a reasonable limit) length and W/B and/or

Crucially looking at the three hopefully identical (within a reasonable limit) values of the radius, R1, R2, RM in red, the latter being enough I believe as the proof of the pudding/duck.

RM is needed because L1 = L2 and R1 = R2 also apply for symmetrical parts of ellipses.

Click to see in full, Click again to get closer.

I can see that the (first) two specific scripting approaches are related to that.

Am I right in believing that the scripting solutions rely on there being only the two end Anchor Points as in the cases stated by Eduard (or H1 and H2 would almost always have different lengths)?

For the drawn solution H1 and H2 could have different lengths, and the R1, R2, RM part would still work in the general case with a third Anchor Point (as in some cases where the curved path was cut out from an actual circle (to be reestablished) in the first place.

[m1b]

@Jacob Bugge, this is pretty much spot on! It is almost exactly what @femkeblanco and I did in our scripts.

The only note I would make is that you and I added the extra step of checking the radius at the midpoint of the curve segment (RM in your diagram) and I don't think it's necessary; I don't think Femke's code does it.

Your observation that the length of the control handles H1 and H2 should be the same if the curve is circular seems to me to be absolutely correct. I didn't even think of that! If performance became an issue, it might be worth adding in a check for that before doing the more expensive bezier calculations. Good thinking. For now I will leave it, because it's pretty fast already.

- Mark

[Kurt Gold]

Mark, allow me one question.

The animated .gif file in your first post above indicates that your script works with multiple selected arcs. As far as I can see it does not do it (which is fine for me). Seems like the script does only process the path that is at the top of the stacking order if multiple arcs are selected.

Am I wrong or am I overlooking something?

[m1b]

Hi Kurt, just as I posted the script above, I added one line "if (isDemo)" but I forgot to declare the variable, so maybe because that line was throwing an error it stopped there and you only see one circle? Please try again. Yes you should be able to select multiple page items. Please let me know if it isn't working and I will fix.

A little unimportant background info: many people seem to misunderstand that sometimes I post a script to solve a specific problem, but often (as in this case) the script is a demonstration only—and while the code has broad applicability to the problem, the script is just a demo—the scripter is expected to use the functions, not the entire script. So I have had cases in the past where I use colors from the document to highlight the script functions (as I did here) and then someone complains that the script doesn't work—because they don't have enough swatches in their document! I thought adding the predicate "isDemo" might make it clearer, but probably not... and worse I introduced an error with last-minute carelessness!

- Mark

[Kurt Gold]

Thanks, Mark. Now it works very well with multiple selected arcs.

I like the declaration "isDemo". It's a versatile motto in many cases.

And as for your additional background info: I completely agree with that.

[m1b]

Good! Thanks for trying it out and reporting the bug.

[Jacob Bugge]

Mark,

"The only note I would make is that you and I added the extra step of checking the radius at the midpoint of the curve segment (RM in your diagram) and I don't think it's necessary;"

I am afraid it is: R1 = R2 only ensures symmetry.

Below I have made two sets, the original to the left, and a new one to the right where the Handle length is reduced by about 15% as the only change (same width of the path, same Handle angle).

R1 = R2 still, but RM is shorter; I have shown the R1 = R2 length which extends above the middle of the path.

Click to see in full, Click again to get closer