14 Replies Latest reply on Nov 20, 2014 1:01 PM by CarlosCanto

    How to check if a path fits inside of another path?

    Sturm359 Level 1

      I've just been told that I need a script that will check and see if a path fits entirely within another path? In my case, I need to see if a GroupItem fits within a circle of a specific size. I don't see any methods available for PageItem that will do it for me, so does anyone know of a workaround? (Preferably without having to check every single PathPoint of every single item in the group.) I am using Illustrator CS6 and do my scripting with Javascript.

        • 1. Re: How to check if a path fits inside of another path?
          Monika Gause Adobe Community Professional & MVP

          This script can do it for rectangles:

          https://forums.adobe.com/message/3699427#3699427

           

          Maybe you can learn from it?

          • 2. Re: How to check if a path fits inside of another path?
            Sturm359 Level 1

            I'm afraid I do not see anything in there which can help with ellipses/circles. It uses the visibleBounds property of paths, which only gives you a top, bottom, left, and right. It's entirely possible for an object's visibleBounds to be within an ellipse's bounds, but still have parts of it sticking outside of the ellipse. Thus, Carlos' method will not work in my case, sorry.

             

            I will say that, while looking at the DOM for Illustrator CS6, I noticed that there is an "inscribed" property (boolean, default true) that one can set when creating an ellipse through scripting. Any idea what that property actually means/does?

            • 3. Re: How to check if a path fits inside of another path?
              Sturm359 Level 1

              So, the "inscribed" property only sets how an ellipse is drawn. When you draw an ellipse in Illustrator, you drag your mouse from one corner to an opposite corner. This imaginary rectangle that you draw sets the boundary for the ellipse. By default, the ellipse is "inscribed" inside of that rectangle. The same thing happens with scripting. If you try to draw an ellipse with a script and set its "inscribed" property to false, then the ellipse will not be inside the rectangle, but outside of it; it will be essentially "circumscribed."

               

              However, I'm afraid none of this helps with trying to discover whether or not one path fits wholly inside of an ellipse. Any ideas?

              • 4. Re: How to check if a path fits inside of another path?
                Larry G. Schneider Adobe Community Professional & MVP

                You will probably have to compare arrays of pathPoints but it's likely to be wonky.

                • 5. Re: How to check if a path fits inside of another path?
                  Silly-V Adobe Community Professional

                  Point in polygon - Wikipedia, the free encyclopedia

                  You need a programming mathematician's help for that one-
                  It looks like it would be possible to get an approximate polygon of your ellipse (or any closed & whole bezier) and then check each single one of your path points in the groupItem's paths against it using the principles in the Wiki link above.  I think to get the approximate polygon you'd make a function to put bezier points along the ellipse and choose only a few of them for the polygon.

                  • 6. Re: How to check if a path fits inside of another path?
                    Sturm359 Level 1

                    I like the idea of using a Raycasting algorithm, as described in your link. It would work just perfectly for the ellipse/circle of which I speak. Now, the question is how to put said racasting algorithm into an ExtendScript script for Illustrator CS6?

                    • 7. Re: Re: How to check if a path fits inside of another path?
                      Silly-V Adobe Community Professional

                      This is good mind-exercise.
                      What I've come up with below will let you know whether your single path's entire set of anchor points is located wholly within a closed bezier path.

                       

                      What you need to do to start working on it is make a document, make your containing ellipse and call it "mycir" and test out a path called "mypth".  The script gets a bezier interpolated point-polygon from the ellipse and uses the raycasting to check anchors of a test path to see if all are inside.  Of course you may already see the problem of parts of your curve which are not anchors overlapping the ellipse and not being detected.  If that's such a big problem, you will need to change the process to create the bezier polygon of your test path and check that with the raycasting.  And that's just for one path- to do an entire group, yes, you'll need to adapt it to work on a whole group of paths.  One more thing- this is really based on points.. so if your group has.. some effects, or appearance which really goes outside the boundaries, you'll definitely need to find a way to expand those to find your true boundaries, and raster effects may be a real deal-breaker.

                       

                      #target illustrator
                      
                      
                      function test(){
                      
                      
                          Array.prototype.indexOf = function(search){
                              for(var i=0; i<this.length; i++){
                                  if(this[i] == search){
                                      return i;
                                  }
                              }
                              return -1;
                          }
                      
                      
                          function foreach(arr, func){
                              for(var i=0; i<arr.length; i++){
                                  func(arr[i]);
                              }
                          }
                          
                          function marker(xy, container){
                              var container = container || doc;
                              var z = container.pathItems.ellipse(xy[1]+2, xy[0]-2, 4, 4);
                              z.stroked = false;
                              z.filled = true;
                              z.fillColor = clr;
                          }
                      
                      
                          function getPathPoints(path){ // collects pathPoints of a path into segment arrays of 2 anchors & 2 controls between them
                              var arr=[];
                              for(var i=0, ln=path.pathPoints.length; i<ln; i++){ // designed to work on closed paths!
                                  if(i<ln-1){
                                      var p = path.pathPoints[i], pnext = path.pathPoints[i+1];
                                  } else {
                                      var p = path.pathPoints[i], pnext = path.pathPoints[0];
                                  }
                                  arr.push([p.anchor, p.rightDirection, pnext.leftDirection, pnext.anchor]); 
                              }
                              return arr;
                          }
                      
                      
                          function getBezierSegment(segArr){ // turns a pathPoint segment  (gotten with getPathPoints) into bezier interpolated points
                              var anch2 = segArr[3], cont2 = segArr[2], cont1 = segArr[1], anch1 = segArr[0];
                              var resultPts = [];
                              
                              var a = anch2[0] - 3*(cont2[0]) + 3*(cont1[0]) - anch1[0];
                              var b = 3*(cont2[0]) - 6*(cont1[0]) + 3*anch1[0];
                              var c = 3*(cont1[0]) - 3*(anch1[0]);
                              var d = anch1[0];
                              
                              var e = anch2[1] - 3*(cont2[1]) + 3*(cont1[1]) - anch1[1];
                              var f = 3*(cont2[1]) - 6*(cont1[1]) + 3*anch1[1];
                              var g = 3*(cont1[1]) - 3*(anch1[1]);
                              var h = anch1[1];
                              
                              var inc = 0.1;
                              for(var t=0; t<1; t+=inc){
                                  resultPts.push([
                                      a*Math.pow(t, 3) + b*Math.pow(t, 2) + (c*t) + d,
                                      e*Math.pow(t, 3) + f*Math.pow(t, 2) + (g*t) + h
                                  ]);
                              }
                              return resultPts;
                          }
                      
                      
                          function getBezierPath(pathPts){ // turns entire series of segments (gotten with getPathPoints)  into a complete set of interpolated bezier points
                              var pathArr = [];
                              for(var i=0; i<pathPts.length; i++){
                                  var thisPtSet = pathPts[i];
                                  var seg = getBezierSegment(thisPtSet);
                                  if(i>0 && (seg[0][0] == pathArr[pathArr.length-1][0] && seg[0][1] == pathArr[pathArr.length-1][1])){
                                      seg.splice(0,1);
                                  }
                                  pathArr = pathArr.concat(seg);
                              }
                              return pathArr;
                          }
                      
                      
                          function markBezierPoints(seg){
                              var grp = doc.groupItems.add(); grp.name="MyGroup";
                              for(var i=0; i<seg.length; i++){
                                  marker(seg[i], grp);
                              }
                          }
                      
                      
                          function makePolygon(pts){
                              var pth = doc.pathItems.add();
                              pth.setEntirePath(pts);
                              pth.filled=false; pth.stroked=true;
                              pth.strokeColor = clr; pth.strokeWidth = 1;
                          }
                      
                      
                          var RayCaster = { // the whole raycasting through polygon algorithm from http://rosettacode.org/wiki/Ray-casting_algorithm
                              // evaluates a single point to see if it's inside a polygon.
                              Point : function(x, y) {
                                this.x = x;
                                this.y = y;
                              },
                      
                      
                              pointInPoly : function(point, poly) {
                                var index, intersected, pointA, pointB, segment, segments;
                                segments = (function() {
                                  var _i, _len, _results;
                                  _results = [];
                                  for (index = _i = 0, _len = poly.length; _i < _len; index = ++_i) {
                                    pointA = poly[index];
                                    pointB = poly[(index + 1) % poly.length];
                                    _results.push([new RayCaster.Point(pointA[0],pointA[1]), new RayCaster.Point(pointB[0],pointB[1])]);
                                  }
                                  return _results;
                                })();
                                intersected = (function() {
                                  var _i, _len, _results;
                                  _results = [];
                                  for (_i = 0, _len = segments.length; _i < _len; _i++) {
                                    segment = segments[_i];
                                    if (RayCaster.rayIntersectsSegment(new RayCaster.Point(point[0],point[1]), segment)) {
                                      _results.push(segment);
                                    }
                                  }
                                  return _results;
                                })();
                                return intersected.length % 2 !== 0;
                              },
                      
                      
                              rayIntersectsSegment : function(p, segment) {
                                  var a, b, mAB, mAP, p1, p2, _ref;
                                  p1 = segment[0], p2 = segment[1];
                                  _ref = p1.y < p2.y ? [p1, p2] : [p2, p1], a = _ref[0], b = _ref[1];
                                  if (p.y === b.y || p.y === a.y) {
                                      p.y += Number.MIN_VALUE;
                                  }
                                  if (p.y > b.y || p.y < a.y) {
                                      return false;
                                  } else if (p.x > a.x && p.x > b.x) {
                                      return false;
                                  } else if (p.x < a.x && p.x < b.x) {
                                      return true;
                                  } else {
                                      mAB = (b.y - a.y) / (b.x - a.x);
                                      mAP = (p.y - a.y) / (p.x - a.x);
                                      return mAP > mAB;
                                  }
                              }
                          }
                      
                      
                          function pathAnchorsInPoly(myPath, polyPts){
                              var flag = false;
                              var all = [];
                              foreach(myPath.pathPoints, function(arg){
                                  if(RayCaster.pointInPoly(arg.anchor, polyPts) === false){
                                      all.push(false);
                                  }
                                  all.push(true);
                              });
                          
                              flag = (all.indexOf(false) != -1) ? false : true;
                          
                              if(flag === false){
                                  alert("NOT All Path Anchors are inside containing ellipse.");
                              } else {
                                  alert("Yay!  All Path Anchors are INSIDE the containing ellipse!");
                              }
                              return flag; // for use later (?)
                          }
                      
                      
                          if(app == "[Application Adobe Illustrator]" && app.documents.length>0){
                              
                              app.coordinateSystem = CoordinateSystem.ARTBOARDCOORDINATESYSTEM;
                              var clr = new CMYKColor();
                              clr.cyan=0;
                              clr.magenta=100;
                              clr.yellow=100;
                              clr.black=0;
                              
                              var doc=app.activeDocument;
                              
                              try{
                                  var m = doc.pathItems.getByName('mycir'); // my circle
                                  var mp = doc.pathItems.getByName('mypth'); // my test path
                              } catch(e) {
                                  alert("Put 2 paths into a document: a containing ellipse, name it 'mycir', and some random path- name it 'mypth'.  Then run.");
                                  return;
                              }
                              
                              var pts = getPathPoints(m);
                              
                              var bezPts = getBezierPath(pts);
                              
                              //markBezierPoints(bezPts);
                              //makePolygon(bezPts);
                              //foreach(bezPts, function(arg){$.writeln(arg)});
                              
                              pathAnchorsInPoly(mp, bezPts);
                              
                          }
                      }
                      
                      
                      test();
                      
                      • 8. Re: Re: How to check if a path fits inside of another path?
                        Sturm359 Level 1

                        Wow! Okay, I'm going to need some time to see if I can grok all of that code. You're using some syntax that I've never seen before, as well as object types that I didn't even know were possible in Illustrator (such as a bezier polygon being different from a normal path). It's clear you've got way more knowledge and skills in Illustrator scripting than I, Silly-V. I'll try out your code after I've had some time to try and understand it better, then I'll let you know if it handles our problem well. Thanks!

                        • 9. Re: How to check if a path fits inside of another path?
                          Silly-V Adobe Community Professional

                          Oh you have questions, feel free to ask 'em here!
                          First, the "bezier polygon" which I construct from path points using the Bezier equation is just an array of interpolated points..  see those commented-out lines toward the bottom, uncomment them to see what it being drawn. 

                          1. //markBezierPoints(bezPts); 
                          2. //makePolygon(bezPts);

                          It's not an object type, but rather just a set of points derived from the ellipse.  Each set of 2 of those points is then fed into a function which checks to see if a ray from a point you want to check intersects them. If it intersects them an even number, it means your point is outside the shape.

                          • 10. Re: How to check if a path fits inside of another path?
                            Sturm359 Level 1

                            Sorry for the very late response—things got really crazy busy around here and I had to put all scripting/programming on hold for a while. Okay, so I've finally had some time to examine your code more closely, Silly-V, and it now is beginning to make sense to me. The way the raycasting algorithm is implemented in the RayCaster object are beyond me, but at least most of the rest of your code is now understandable. I can see that converting all of the paths in the artwork to bezier paths and checking to see if each set of points is within the imprint area circle will slow down the script considerably, especially with heavily-detailed artwork. Thus, I won't take it to that extreme. It will be very rare that we'll run into such situations where curves, raster images, and effects will fall outside of the imprint circle. When it happens, we'll just deal with it manually; I don't think it'll be a problem.

                             

                            So I'll go ahead and mark your answer as the correct one and, with your permission, implement your code into our script here at work, giving you credit for it, of course. Thank you so much for finding a solution to a problem that's been plaguing me for months, and for being incredibly helpful, Silly-V!

                            • 11. Re: How to check if a path fits inside of another path?
                              Silly-V Adobe Community Professional

                              I hope it works out for you.  The raycasting is also beyond me, that is why it's wholly copied from rosettacode.org 

                              • 12. Re: How to check if a path fits inside of another path?
                                CarlosCanto Adobe Community Professional & MVP

                                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.

                                • 13. Re: How to check if a path fits inside of another path?
                                  Sturm359 Level 1

                                  That's… actually a pretty fantastic idea, CarlosCanto. The only hiccup I might see is if one of the paths is a clipping mask: If the masked paths fall outside of the imprint area (the starting circle), then it seems that your third condition gets triggered and the response would be that the art does not fit within the imprint area, even if the clipping mask path does. Otherwise, it's an excellent suggestion and I may consider it as a fallback position if Silly-V's snippet ends up slowing down the overall script too much. Thanks!

                                  • 14. Re: How to check if a path fits inside of another path?
                                    CarlosCanto Adobe Community Professional & MVP

                                    Good point, for clipping masks you could test the clipping path only