首页 > 其他分享 >空间判断点是否在线段上

空间判断点是否在线段上

时间:2023-01-27 22:46:05浏览次数:57  
标签:判断 线段 Vector2d LineSegment P1P2 lineSegment 空间 向量

目录

1. 概述

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

2. 详论

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

  1. 计算\(\vec{P1P2}\)与\(\vec{P1P}\)的向量叉积,可以判断是否存在一条直线上。原理是向量叉积的模(长度)表示两个向量组成的平面四边形的面积,如果叉积的模为0,说明两者共线,无法组成平行四边形。
  2. 计算向量点积,点积的几何意义是一个向量向另外一个向量的投影;如果满足如下公式,说明是在两个端点之间:

\[0<{\vec{P1P}}\cdot{\vec{P1P2}}<{||\vec{P1P2}||}^2 \]

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

#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?

标签:判断,线段,Vector2d,LineSegment,P1P2,lineSegment,空间,向量
From: https://www.cnblogs.com/charlee44/p/17069469.html

相关文章

  • [Oracle19C 数据库管理] 管理回滚表空间(UNDO Tablespace)
    当对数据进行修改时,Oracle数据库会将旧的数据存储到UNDO表空间(回滚表空间)。回滚表空间让用户可以rollback到修改前的数据,提供了读一致性,并支持闪回查询过去的数据。Undo......
  • 判断素数
    判断素数输入一个大于1的整数x,若x是素数,则输出Yes,否则输出Noimportjava.util.Scanner;publicclassPrimeNumber{staticbooleanIsPrimeNumber(intx){......
  • 判断回文数
    判断回文数输入一个大于0的整数x,若x是回文数,则输出Yes,否则输出Noimportjava.util.Scanner;publicclassPalindromicNumber{publicstaticvoidmain(String[......
  • 向量叉积判断三角形是否进行了三维旋转
    2023牛客寒假算法一E叉积判断三维旋转鸡在玩铁丝。具体来说,二维平面上有一根L型的铁丝,由AB和BC两条线段组成,鸡可以用以下三种操作玩铁丝:1、在平面内任意地平移铁丝,即......
  • oracle表空间
    SQLServer数据库与Oracle数据库之间最大的区别要属表空间设计。Oracle数据库开创性地提出了表空间的设计理念,这为Oracle数据库的高性能做出了不可磨灭的贡献。可以这么说,Or......
  • C语言:判断回文字符串
    #include<stdio.h>#include<string.h>intfh(charab[]){intlen=strlen(ab),a=0;for(a=0;a<=len;a++)if(ab[a]!=ab[len-a-1])return0;retur......
  • JavaScript:判断数组对象值是否相同的函数声明
    varobj1={name:"w",};varobj2={name:"w",};functionisObjectValueEqual(a,b){//判断两个对......
  • Java之判断今天是今年的第几天!...
    importjava.util.Date;publicclasswhichDay{publicstaticvoidmain(String[]args){//获取系统时间Datedate=newDate();//%tj表......
  • js中判断数据类型的方法有哪些
    判断数据类型可以使用typeof但是typeof判断数组和函数时返回的都是Object不能具体判断,这时使用instanceof可以判断对象是否是另一个函数创造的;用法:typeof([]) ......
  • MySQL 哈希索引、空间数据索引、全文索引
    1.哈希索引哈希索引基于哈希表实现,仅支持精确匹配索引所有列的查询。对于每行数据,存储引擎都会对所有的索引列计算出一个哈希码。哈希索引将所有的哈希码存储在索引中,同时保......