Inconsistent intersection points with line and path

[bob-pasabi]

I’m having an issue getting intersections to work correctly with a path and a line. I’ve been using kld-intersections to do intersections for my custom polygon nodes and it works great. I’ve been adding a cloud node to the DAG and wanted to get the edge arrows to line up nicely with the edges of the cloud but I can’t seem to get reliable intersection points for the path.

If I take a cloud path

ShapeInfo.path(“M80,80 a20,20 0 0,0 0,40 h50 a20,20 0 0,0 0,-40 a10,10 0 0,0 -15,-10 a15,15 0 0,0 -35,10z"

And a line through it like

ShapeInfo.line([-105, -45, 245, 230])

It won’t pick up the intersections on the arc part. If I move the line it may pick up intersections inside the cloud rather that along its path.
I'm not sure if I'm doing something wrong here, I've seen way more complicated path and line intersections working so I'm unsure what is going on.

(circles are drawn for reported intersections, I added a rect to the background as well just to check the line was ok)

[thelonious]

Thanks @bob-pasabi for reporting this. Due to the holidays, it may be a few days before I'll be able to look into this. Hopefully it's an easy fix :)

[thelonious]

@bob-pasabi, I believe I have a fix:

I need to write some proper tests and clean things up a bit. Once all of that is done, I'll push a new release and close this issue.

Thanks again for reporting this!

[bob-pasabi]

Thats great, no rush. Will give it a go once it's pushed and will let you know.

[rikkertkoppes]

Was this resolved? I believe I have a similar (if not the same) problem:

Looking for intersections of the red path to the small circles. The red path is comprised of Arc segments and straight lines (much like the cloud above). There may be a problem with the sweep and/or large arc flags. Note:

• no intersections with the lower left (small) circle found
• only one intersection with the lower right small circle found (expected none)
• intersections found for the upper two small circles (expected none)

[rikkertkoppes]

Fwiw, the problem is here: https://github.com/thelonious/kld-intersections/blob/development/lib/Intersection.js#L83-L110

here is my fix:

function restrictPointsToArc(intersections, center, radiusX, radiusY, startRadians, endRadians) {
    if (intersections.points.length === 0) {
        return intersections;
    }

    const result = new Intersection("No Intersection");

    //swap if end is lower, so start is always the lower one
    if (endRadians < startRadians) {
        [startRadians, endRadians] = [endRadians, startRadians];
    }
    //move everything to the positive domain, simultaniously
    if (startRadians < 0 || endRadians <0) {
        startRadians += TWO_PI;
        endRadians += TWO_PI;
    }

    for (const p of intersections.points) {
        let a = normalizeAngle(UNIT_X.angleBetween(Vector2D.fromPoints(center, p)));
        //a angle smaller than start, it may still be between
        //this happens if end > TWO_PI
        if (a < startRadians) a += TWO_PI;
        if (startRadians <= a && a <= endRadians) {
            result.appendPoint(p);
        }
    }

    if (result.points.length > 0) {
        result.status = "Intersection";
    }

    return result;
}

[thelonious]

Hi @rikkertkoppes. No, unfortunately, I thought I had a fix, but it ended up breaking other cases. Yes indeed, the problem is in that code, specifically, where I'm trying to canonicalize the starting and ending angles which are used to filter the results. I'm in the middle of a release right now, so I'm not sure when I'll get to this. Of course, if you find a fix, I would gladly accept a PR. My apologies for the trouble and delay

[rikkertkoppes]

The above fix does seem to work, math seems right to me too. I'll see if I can find some time to add tests and commit a pr

[ghost]

Oh, OK. Great! I will give this a try. I can take care of committing it. No need for a PR

[ghost]

Yeah, that looks like its working well. If you can, would you test using the development branch? I had some visual tests that I was using. Here's the process I used:

cd kld-intersections
git checkout development
git pull origin development
npm update
npm run rollup
http-server .

Opened browser to http://localhost:8080/visual-test/ and opened these visual tests:

• line_rounded_rect
• line_rounded_rect_2
• arc-fail

If everything looks good for you, I can push a new release.

Thanks for the help!

[rikkertkoppes]

This was my reasoning:

• ASSUMPTION: startRadians and endRadians given are between -TWO_PI and TWO_PI
• ASSUMPTION: endRadians < startRadians for ccw arcs
• ASSUMPTION: the area of interest is between the two

These are the steps then:

1. if e < s, swap the two
2. s < e < 0: add TWO_PI, we end up in 4.
3. s < 0 < e: add TWO_PI, note that this means e > TWO_PI, we and up in 4
4. 0 < s < e

So we now always have 0 < s < e, and e may be > TWO_PI. The angle we need to check (a) is now normalized: 0 < a < TWO_PI

• if a < s, we may still have a match in the TWO_PI - e range, so a += TWO_PI
• if s < a < e, we have a match

[rikkertkoppes]

All tests seem fine to mee. Also, this is my original use case, which is now also fixed:

Mine is an interactive environment, you can drag stuff around. By doing so, I have not encountered any problems

[thelonious]

@bob-pasabi @rikkertkoppes: I've pushed 0.7.0 with rikkertkoppes fixes. Thanks so much for reporting the issue and, especially, for providing a fix. That's a big help!

I'm closing this, but if you see any other related issues, please feel free to re-open

[iosonosempreio]

Hi, I think I bumped into a very similar problem using [email protected].
I post this, in the hope that it may help to find a solution and to help others with similar issue.

I am looking for intersection between circle #0 and the yellow path.

Red rings show intersections found with this code:

const path = ShapeInfo.path(pathSegments);
const circle = ShapeInfo.circle({center: {x: circle_x, y: circle_y}, radius: circle_r});
const intersections_data = Intersection.intersect(path, circle);

It looks very strange to me: it is detecting intersections with other two circles, that are not even visible to kld.

Same issue with different geometries:

This is the strangest case I found: it detects 2 fake intersections and then it detects two actual ones:

To solve I found a workaround, that is to transform the path into a polygon, sampling it with a certain precision rate. Then I look for intersections with the polygon, which is working great!

//  Create a (ghost) path element
var pathToSample = document.createElementNS('http://www.w3.org/2000/svg','path');
pathToSample.setAttribute('d', pathSegments);
const length = pathToSample.getTotalLength();
const rate = 50;  //  I saw 50 is producing good results in my case
const unit = length/rate;
const sampledPoints = [];
for (let j=0; j<rate; j++) {
    sampledPoints.push(pathToSample.getPointAtLength(unit*j))
}
const polygon = ShapeInfo.polygon(sampledPoints);
const circle = ShapeInfo.circle({center: {x: circle_x, y: circle_y}, radius: circle_r});
const intersections_data = Intersection.intersect(polygon, circle);

I have some performances issue to deal with now (I have to check many many shapes), but at least it is working correctly.

[rikkertkoppes]

What comprises the yellow path? Looks like arcs and beziers?

Can you provide the geometries or a test repo?

[rikkertkoppes]

It looks like it is intersecting with the green path drawn (mad paint skillz)
Judging by eye, there seems to be a problem every time the sweep around an arc is more than 180 degrees. It then seems to follow the other part of the circle. This would explain all your cases.

[thelonious]

@iosonosempreio, I know @rikkertkoppes asked already, but if you can provide an example that recreates the original issue, that would be really helpful.

[iosonosempreio]

Hi, sorry for keeping you guys waiting.
Here is my example, as you can see intersections are marked as black points.
The yellow path is created using arcs and beziers. It looks like @rikkertkoppes idea might be correct, in fact I am sweeping around certain arcs!

<g transform="translate(460.5,180)">

  <circle fill="transparent" stroke="blue" r="19" cx="28.872594624821176" cy="-6.462574457633673"></circle>
  <circle fill="transparent" stroke="blue" r="22" cx="-8.764180155357014" cy="9.831110728196155"></circle>
  <circle fill="transparent" stroke="blue" r="22" cx="-1.862118062382238" cy="-33.57402393232108"></circle>
  <circle fill="transparent" stroke="blue" r="17" cx="24.565523482491404" cy="29.462855834865223"></circle>
  <circle fill="transparent" stroke="blue" r="22" cx="-42.95061531484777" cy="-17.630785564329774"></circle>
  <circle fill="transparent" stroke="blue" r="8" cx="28.024718838989763" cy="-33.46557754335759"></circle>
  <circle fill="transparent" stroke="blue" r="19" cx="-4.621995356444165" cy="50.33325063945469"></circle>
  <circle fill="transparent" stroke="blue" r="11" cx="-31.319515343944115" cy="-48.51310195277438"></circle>
  <circle fill="transparent" stroke="blue" r="15" cx="53.64721765609639" cy="16.38828281034695"></circle>

  <path class="metaball" fill="none" stroke="#e6ae55" stroke-width="2" d="M -23.018688132109176,45.58333538570597 C -17.339063084276454,23.585823534628638 -22.979713991625157,10.247056126036032 -48.450517187609435,3.670648175913925A 22,22, 0 0,1, -48.507634814709846, -38.917390138055296C -42.410881407526524,-40.508990970974736 -41.16831384220903,-42.68840737104629 -41.96343577135703,-45.73696111792788A 11,11, 0 0,1, -21.73309268252158, -53.90758993186604C -15.259707107611579,-42.403882738159 15.73512234968161,-35.7296045153667 24.101454854195822,-40.43752129711943A 8,8, 0 0,1, 35.77986947235321, -31.50149031162817C 33.42296479427791,-22.195309551592032 39.88079229052129,-2.571820898600704 57.32988121558905,1.847375372790486A 15,15, 0 0,1, 50.2534112063797, 30.999308707999088C 32.72018012919713,26.926740968339075 19.04388991748457,32.42331277799791 13.88530411391521,54.63207214242915A 19,19, 0 1,1, -23.018688132109176, 45.58333538570597 Z"></path>

  <text x="28.872594624821176" y="-1.4625744576336732" text-anchor="middle">0</text>
  <text x="-8.764180155357014" y="14.831110728196155" text-anchor="middle">1</text>
  <text x="-1.862118062382238" y="-28.574023932321083" text-anchor="middle">2</text>
  <text x="24.565523482491404" y="34.46285583486522" text-anchor="middle">3</text>
  <text x="-42.95061531484777" y="-12.630785564329774" text-anchor="middle">4</text>
  <text x="28.024718838989763" y="-28.46557754335759" text-anchor="middle">5</text>
  <text x="-4.621995356444165" y="55.33325063945469" text-anchor="middle">6</text>
  <text x="-31.319515343944115" y="-43.51310195277438" text-anchor="middle">7</text>
  <text x="53.64721765609639" y="21.38828281034695" text-anchor="middle">8</text>

</g>

You should be able to reproduce it using the SVG code I provided plus these KLD functions, for everyone of the circles above:

const path = ShapeInfo.path(segments);
const circle = ShapeInfo.circle(circle.x, circle.y, circle.r);            
const intersections_data = Intersection.intersect(path, circle);

Generate circles using this data:

[
  {
    "x": 28.872594624821176,
    "y": -6.462574457633673,
    "r": 19
  },
  {
    "x": -8.764180155357014,
    "y": 9.831110728196155,
    "r": 22
  },
  {
    "x": -1.862118062382238,
    "y": -33.57402393232108,
    "r": 22
  },
  {
    "x": 24.565523482491404,
    "y": 29.462855834865223,
    "r": 17
  },
  {
    "x": -42.95061531484777,
    "y": -17.630785564329774,
    "r": 22
  },
  {
    "x": 28.024718838989763,
    "y": -33.46557754335759,
    "r": 8
  },
  {
    "x": -4.621995356444165,
    "y": 50.33325063945469,
    "r": 19
  },
  {
    "x": -31.319515343944115,
    "y": -48.51310195277438,
    "r": 11
  },
  {
    "x": 53.64721765609639,
    "y": 16.38828281034695,
    "r": 15
  }
]