Detect if Lines Intersect in Google Charts or Plot.ly

Question

I have seen scripts that claim to enter coordinates and it'll tell you if they intersect, but I have an array of X,Y values for a couple of "lines" but how do I cycle through the points to find out if they intersect?

I've included a photo of my graph and as you see, eventually my plots cross over, I just want to know if my values ever cross over (intersect).

How do I run through this to find out if any intersection ever occurs?

var Test = {
 x: [8043, 10695, 13292, 17163, 20716, 25270],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test'
};


var Test2 = {
 x: [8043, 10063, 12491, 16081, 19408, 23763],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test2'
};

var Test3 = {
 x: [4700,  5943,  7143,  8841, 10366, 13452],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test3'
};


var data = [Test, Test2, Test3];

var layout = {
width: 700,
height: 700,
xaxis: {
 type: 'log',
 range: [3,5] 
},
yaxis: {
 type: 'log',
 range: [-2,3] 
}

};

Plotly.newPlot('myDiv', data,layout);

Answer 1

Path intercepts

This answer is a follow on from my answer to your most resent question.

The code snippet below will find the intercepts of the paths in the tables as structured in this questions example data using a modified intercept function from the answer link in may comment from aforementioned answer.

Note I am assuming that each table eg Test in your example data represents a curve (Path as a set of line segments) and that intercepts are not expected within a table but rather between tables.

Basic solution

It does this by checking each line segment in one table against each line segment in the other and storing all intercepts in an array.

Note that if a intercept is found at the start or end point of a line it may appear in the array of intercepts twice as the intercept test includes these points.

Note lines that are parallel, even if they have matching start and or end points will not count as intercepts.

The example is run against the example data and has a verbose console output to guide, if needed, you working through what ever data sets you are wrangling. The console logs can be removed without ill effect.

var Test = {
 x: [8043, 10695, 13292, 17163, 20716, 25270],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test'
};


var Test2 = {
 x: [8043, 10063, 12491, 16081, 19408, 23763],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test2'
};

var Test3 = {
 x: [4700,  5943,  7143,  8841, 10366, 13452],
 y: [1000,   274,   100,  27.4,    10,  2.74],
 fill: 'tozeroy',
 type: 'scatter',
 name: 'Test3'
};


// Copy from here to end comment and place into you page (code base)

// lines outputting to the console eg console.log are just there to help you out
// and can be removed
const lineIntercepts = (() => {
 const Point = (x, y) => ({x, y});
 const Line = (p1, p2) => ({p1, p2});
 const Vector = line => Point(line.p2.x - line.p1.x, line.p2.y - line.p1.y);
 function interceptSegs(line1, line2) {
  const a = Vector(line1), b = Vector(line2);
  const c = a.x * b.y - a.y * b.x;
  if (c) {
   const e = Point(line1.p1.x - line2.p1.x, line1.p1.y - line2.p1.y);
   const u = (a.x * e.y - a.y * e.x) / c;
   if (u >= 0 && u <= 1) {
    const u = (b.x * e.y - b.y * e.x) / c;
    if (u >= 0 && u <= 1) {
     return Point(line1.p1.x + a.x * u, line1.p1.y + a.y * u);
    }
   }
  }
 } 
 const PointFromTable = (t, idx) => Point(t.x[idx], t.y[idx]);
 const LineFromTable = (t, idx) => Line(PointFromTable(t, idx++), PointFromTable(t, idx));
 return function (table1, table2) {
  const results = [];
  var i = 0, j;
  while (i < table1.x.length - 1) {
   
   const line1 = LineFromTable(table1, i);
   j = 0;
   while (j < table2.x.length - 1) {
    const line2 = LineFromTable(table2, j);
    const point = interceptSegs(line1, line2);
    if (point) { 
     results.push({
      description: `'${table1.name}' line seg index ${i}-${i+1} intercepts '${table2.name}' line seg index ${j} - ${j+1}`,

                    // The description (line above) can be replaced 
                    // with relevant data as follows
/*  remove this line to include additional info per intercept
                        tableName1: table1.name,
                        tableName2: table2.name,
                        table_1_PointStartIdx: i,
                        table_1_PointEndIdx: i + 1,   
                        table_2_PointStartIdx: j,
                        table_2_PointEndIdx: j + 1,   
and remove this line */

      x: point.x,
      y: point.y,
     });
    }
    j ++;
   }
   i++;
  }
  if (results.length) {
   console.log("Found " + results.length + " intercepts for '" + table1.name + "' and '" + table2.name + "'");
   console.log(results);
   return results;
  } 
  console.log("No intercepts found for  '" + table1.name + "' and '" + table2.name + "'");
 }
})();

// end of code



// Test and example code only from here down.     
var res1 = lineIntercepts(Test, Test2);    
var res2 = lineIntercepts(Test, Test3);    
var res3 = lineIntercepts(Test2, Test3);    
          
          

  

Using the above function

This bit of code illustrates how you extract intercepts from the function results

// find all the intercepts for the paths in tabels Test and Test2
const results = lineIntercepts(Test, Test2); // pass two tables

// If results not undefined then intercepts have been found
if (results) { // results is an array of found intercepts

    // to get the point/s as there could be several
    for (const intercept of results) {  // loop over every intercept 

        // a single intercept coordinate
        const x = intercept.x;  // get x
        const y = intercept.y;  // get y
    }
}

Better solutions

The paths look very much like they are a plot of some function thus there are even simpler solutions.

Rather than list out lines of code, I will direct you towards graphing calculators in case you are unaware of such useful time savers. They would have solved your problem in the time it takes to enter the data (by copy&paste thats not very long)

Online graphing calculators example apps Geogebra and Desmos and many more.