如何找到与一条直线相交的点？

Question

如果我在Flutter中有以下图表：

绿色图表是一个Path对象，包含许多lineTo线段，如何找到给定x坐标的点的y坐标？

正如您在图像中所看到的那样，存在一个灰色虚线，位于x轴上的特定点，我想找到它与绿色图形相交的点。

---

这里是一个示例路径：

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);

我想要找到在dx = 75时该点的纵坐标。

- creativecreatorormaybenot

Answer 1

对于任何只有一个点的路径（即从左到右只有一条图形/线路），实现这一点最简单的方法是使用二分查找算法。然后，您可以使用路径的距离（使用Path.computeMetrics获得）执行二分查找并通过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)

注意，如果你想运行更多的迭代次数（由于二分搜索的性质，这应该是不必要的），你应该将 final change = pathDistance / pow(2, n); 替换为一种更便宜的操作，例如存储当前搜索区间的左右点。

---

您可以在Dartpad上的示例中找到完整的可运行代码。

- creativecreatorormaybenot