How do I find the point intersecting a line?

user_6509751 0
Viewed 272

If I have the following chart in Flutter:

graph

Where the green graph is a Path object with many lineTo segments, how do I find the y-coordinate for a point with a given x-coordinate?

As you can see in the image, there is a gray dotted line at a specific point on the x-axis and I want to draw a point where it intersects with the green graph.

Here is an example path:

final path = Path();
path.moveTo(0, 200);
path.lineTo(10, 210);
path.lineTo(30, 190);
path.lineTo(55, 150);
path.lineTo(80, 205);
path.lineTo(100, 0);

And I want to find the y-coordinate for the point at dx = 75.

dart flutter 2d graphics canvas
1 Answers

The easiest way to achieve this for any path that only has a single point for every x (i.e. where there is only a single graph / line from left to right) is using the binary search algorithm.

You can then simply use the distance of the path, which is obtained using Path.computeMetrics, to perform binary search and find the offset via Path.getTangentForOffset:

const searchDx = 75;
const iterations = 12;
  
final pathMetric = path.computeMetrics().first;
final pathDistance = pathMetric.length;
late Offset closestOffset;
var closestDistance = pathDistance / 2;
for (var n = 1; n <= iterations; n++) {
  closestOffset = pathMetric.getTangentForOffset(closestDistance)!.position;
  if (closestOffset.dx == searchDx) break;
   
  final change = pathDistance / pow(2, n);
  if (closestOffset.dx < searchDx) {
    closestDistance += change;
  } else {
    closestDistance -= change;
  }
}
  
print(closestOffset); // Offset(75.0, 193.9)

Note that if you want to run significantly more iterations (which should not be necessary due to the nature of binary search), you should replace final change = pathDistance / pow(2, n); by a cheaper operation like storing the left and right points of your current search interval.

You can find the full working code as an example on Dartpad.

user_65097510
Related