空间判断点是否在线段上

目录

• 1. 概述
• 2. 详论
• 3. 参考

1. 概述

判断点是否在线段上的算法非常简单，有很多种实现方式，总结一下我自己的实现。

2. 详论

个人认为通过向量计算的方式是比较好的，因为可以保证在二维和三维的情况都成立。判断空间中点P是否在线段P1P2上，算法思想是分成两部分：

1. 计算

vec{P1P2}

与

vec{P1P}

的向量叉积，可以判断是否存在一条直线上。原理是向量叉积的模（长度）表示两个向量组成的平面四边形的面积，如果叉积的模为0，说明两者共线，无法组成平行四边形。

1. 计算向量点积，点积的几何意义是一个向量向另外一个向量的投影；如果满足如下公式，说明是在两个端点之间：

0<{vec{P1P}}cdot{vec{P1P2}}<{||vec{P1P2}||}^2

具体的代码实现如下所示：

代码语言：javascript复制

#include <Eigen/Eigen>
#include <iostream>

using namespace Eigen;
using namespace std;

using LineSegment = Vector2d[2];

const double epsilon = 0.000000001;

//判断点在线段上
bool PointInLine(const Vector2d& point, const LineSegment& lineSegment) {
  Vector3d P1P2;
  P1P2 << lineSegment[1] - lineSegment[0], 0;
  Vector3d P1P;
  P1P << point - lineSegment[0], 0;

  if (fabs((P1P2.cross(P1P)).norm()) > epsilon) {
    return false;
  }

  double dotProduct = P1P2.dot(P1P);
  if (dotProduct > 0 && dotProduct < P1P2.squaredNorm()) {
    return true;
  }

  return false;
}

int main() {
  // LineSegment lineSegment;
  // lineSegment[0] = Vector2d(0, 0);
  // lineSegment[1] = Vector2d(50, 100);
  // Vector2d c(25, 50);
  // Vector2d d(0, 8);

  LineSegment lineSegment;
  lineSegment[0] = Vector2d(2.6, 1.5);
  lineSegment[1] = Vector2d(24.5, 80.6);
  Vector2d ld = lineSegment[1] - lineSegment[0];
  Vector2d c = lineSegment[0]   0.46 * ld;
  Vector2d d(0, 8);

  cout << PointInLine(c, lineSegment) << endl;
  // cout << PointInLine(d, lineSegment) << endl;
}

说明一下代码实现：

1. 使用了Eigen中的矢量类，其实自己使用其他库的矢量类或者自己实现也是可以的。
2. 内置浮点型的精度有限，因此设置epsilon作为容差。
3. 由于是使用向量计算，因而是可以拓展到三维空间中使用的。

3. 参考

1. 判断点是否在线段上
2. How can you determine a point is between two other points on a line segment?

编程算法

0 人点赞