C++/STL实现判断平面内两条线段的位置关系代码示例

概念

平面内两条线段位置关系的判定在很多领域都有着广泛的应用,比如游戏、CAD、图形处理等,而两线段交点的求解又是该算法中重要的一环。本文将尽可能用通俗的语言详细的描述一种主流且性能较高的判定算法。

外积,又称叉积,是向量代数(解析几何)中的一个概念。两个二维向量v1(x1,y1)和v2(x2,y2)的外积v1×v2=x1y2-y1x2。如果由v1到v2是顺时针转动,外积为负,反之为正,为0表示二者方向相同(平行)。此外,文中涉及行例式和方程组的概念,请参阅线性代数的相关内容。

为方便计算,对坐标点的大小比较作如下定义:x坐标较大的点为大,x坐标相等但y坐标较大的为大,x与y都相等的点相等。一条线段中较小的一端为起点,较大的一端为终点。

问题

给定两条线段的端点坐标,求其位置关系,并求出交点(如果存在)。

分析

两条线段的位置关系大体上可以分为三类:有重合部分、无重合部分但有交点(相交)、无交点。为避免精度问题,首先要将所有存在重合的情况排除。

重合可分为:完全重合、一端重合、部分重合三种情况。显然,两条线段的起止点都相同即为完全重合;只有起点相同或只有终点相同的为一端重合(注意:坐标较小的一条线段的终点与坐标较大的一条线段的起点相同时应判定为相交)。要判断是否部分重合,必须先判断是否平行。设线段L1(p1->p2)和L2(p3->p4),其中p1(x1,y1)为第一条线段的起点,p2(x2,y2)为第一条线段的终点,p3(x3,y3)为第二条线段的起点,p4(x4,y4)为第二段线段的终点,由此可构造两个向量:

v1(x2-x1,y2-y1),v2(x4-x3,y4-y3)

若v1与v2的外积v1×v2为0,则两条线段平行,有可能存在部分重合。再判断两条平行线段是否共线,方法是用L1的一端和L2的一端构成向量vs并与v2作外积,如果vs与v2也平行则两线段共线(三点共线)。在共线的前提下,若起点较小的线段终点大于起点较大的线段起点,则判定为部分重合。

没有重合,就要判定两条线是否相交,主要的算法还是依靠外积。然而外积的计算开销比较大,如果不相交的情况比较多,可先做快速排斥实验:将两条线段视为两个矩形的对角线,并构造出这两个矩形。如果这两个矩形没有重叠部分(x坐标相离或y坐标相离)即可判定为不相交。

然后执行跨立试验。两条相交的线段必然相互跨立,简单的讲就是p1和p2两点位于L2的两侧且p3和p4两点位于L1的两侧,这样就可利用外积做出判断了。分别构造向量s1(p3,p1),s2(p3,p2),如果s1×v2与s2×v2异号(s1->v2与s2->v2转动的方向相反),则说明p1和p2位于L2的两侧。同理可判定p3和p4是否跨立L1。如果上述四个叉积中任何一个等于0,则说明一条线段的端点在另一条线上。

当判定两条线段相交后,就可以进行交点的求解了。当然,求交点可以用平面几何方法,列点斜式方程来完成。但这样作会难以处理斜率为0的特殊情况,且运算中会出现多次除法,很难保证精度。这里将使用向量法求解。

设交点为(x0,y0),则下列方程组必然成立:

x0-x1=k1(x2-x1)

y0-y1=k1(y2-y1)

x0-x3=k2(x4-x3)

y0-y3=k2(y4-y3)

其中k1和k2为任意不为0的常数(若为0,则说明有重合的端点,这种情况在上面已经被排除了)。1式与2式联系,3式与4式联立,消去k1和k2可得:

x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)

x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3)

将含有未知数x0和y0的项移到左边,常数项移动到右边,得:

(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1

(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3

设两个常数项分别为b1和b2:

b1=(y2-y1)x1+(x1-x2)y1

b2=(y4-y3)x3+(x3-x4)y3

系数行列式为D,用b1和b2替换x0的系数所得系数行列式为D1,替换y0的系数所得系数行列式为D2,则有:

|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)

|D1|=b2(x2-x1)-b1(x4-x3)

|D2|=b2(y2-y1)-b1(y4-y3)

由此,可求得交点坐标为:

x0=|D1|/|D|,y0=|D2|/|D|

解毕。

C++/STL实现

#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
  return (abs(f1 - f2) < 1e-4f);
}
//判断两点是否相等
bool operator==(const POINTF &p1, const POINTF &p2) {
  return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
//比较两点坐标大小,先比较x坐标,若相同则比较y坐标
bool operator>(const POINTF &p1, const POINTF &p2) {
  return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
//计算两向量外积
float operator^(const POINTF &p1, const POINTF &p2) {
  return (p1.x * p2.y - p1.y * p2.x);
}
//判定两线段位置关系,并求出交点(如果存在)。返回值列举如下:
//[有重合] 完全重合(6),1个端点重合且共线(5),部分重合(4)
//[无重合] 两端点相交(3),交于线上(2),正交(1),无交(0),参数错误(-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
  //保证参数p1!=p2,p3!=p4
  if (p1 == p2 || p3 == p4) {
    return -1; //返回-1代表至少有一条线段首尾重合,不能构成线段
  }
  //为方便运算,保证各线段的起点在前,终点在后。
  if (p1 > p2) {
    swap(p1, p2);
  }
  if (p3 > p4) {
    swap(p3, p4);
  }
  //判定两线段是否完全重合
  if (p1 == p3 && p2 == p4) {
    return 6;
  }
  //求出两线段构成的向量
  POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
  //求两向量外积,平行时外积为0
  float Corss = v1 ^ v2;
  //如果起点重合
  if (p1 == p3) {
    Int = p1;
    //起点重合且共线(平行)返回5;不平行则交于端点,返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果终点重合
  if (p2 == p4) {
    Int = p2;
    //终点重合且共线(平行)返回5;不平行则交于端点,返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果两线端首尾相连
  if (p1 == p4) {
    Int = p1;
    return 3;
  }
  if (p2 == p3) {
    Int = p2;
    return 3;
  }//经过以上判断,首尾点相重的情况都被排除了
  //将线段按起点坐标排序。若线段1的起点较大,则将两线段交换
  if (p1 > p3) {
    swap(p1, p3);
    swap(p2, p4);
    //更新原先计算的向量及其外积
    swap(v1, v2);
    Corss = v1 ^ v2;
  }
  //处理两线段平行的情况
  if (Equal(Corss, 0)) {
    //做向量v1(p1, p2)和vs(p1,p3)的外积,判定是否共线
    POINTF vs = {p3.x - p1.x, p3.y - p1.y};
    //外积为0则两平行线段共线,下面判定是否有重合部分
    if (Equal(v1 ^ vs, 0)) {
      //前一条线的终点大于后一条线的起点,则判定存在重合
      if (p2 > p3) {
        Int = p3;
        return 4; //返回值4代表线段部分重合
      }
    }//若三点不共线,则这两条平行线段必不共线。
    //不共线或共线但无重合的平行线均无交点
    return 0;
  } //以下为不平行的情况,先进行快速排斥试验
  //x坐标已有序,可直接比较。y坐标要先求两线段的最大和最小值
  float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
  if (ymax1 < ymin1) {
    swap(ymax1, ymin1);
  }
  if (ymax2 < ymin2) {
    swap(ymax2, ymin2);
  }
  //如果以两线段为对角线的矩形不相交,则无交点
  if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
    return 0;
  }//下面进行跨立试验
  POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
  POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
  float s1v2, s2v2, t1v1, t2v1;
  //根据外积结果判定否交于线上
  if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
    Int = p1;
    return 2;
  }
  if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
    Int = p2;
    return 2;
  }
  if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
    Int = p3;
    return 2;
  }
  if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
    Int = p4;
    return 2;
  } //未交于线上,则判定是否相交
  if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
    return 0;
  } //以下为相交的情况,算法详见文档
  //计算二阶行列式的两个常数项
  float ConA = p1.x * v1.y - p1.y * v1.x;
  float ConB = p3.x * v2.y - p3.y * v2.x;
  //计算行列式D1和D2的值,除以系数行列式的值,得到交点坐标
  Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
  Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
  //正交返回1
  return 1;
}
//主函数
int main(void) {
  //随机生成100个测试数据
  for (int i = 0; i < 100; ++i) {
    POINTF p1, p2, p3, p4, Int;
    p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
    p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
    p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
    p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
    int nr = Intersection(p1, p2, p3, p4, Int);
    cout << "[(";
    cout << (int)p1.x << ',' << (int)p1.y << "),(";
    cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
    cout << (int)p3.x << ',' << (int)p3.y << "),(";
    cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
    cout << nr;
    if (nr > 0) {
      cout << '(' << Int.x << ',' << Int.y << ')';
    }
    cout << endl;
  }
  return 0;
}

关于stl,貌似用的不多了,不是过时了,而是有控制的使用,每个项目都有自己的使用场景,根据自己的需要选择合适的技术。

总结

以上就是本文关于C++/STL实现判断平面内两条线段的位置关系代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

C++递归算法实例代码

C++中函数指针详解及代码分享

C/C++ 编译器优化介绍

如有不足之处,欢迎留言指出。

(0)

相关推荐

  • 浅谈c++中的stl中的map用法详解

    Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道.这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的,后边我们会见识到有序的好处. 下面举例说明什么是一对一的数据映射.比如一个班级中,每个学生的学号跟他的姓名就存在着一一

  • C++ STL list 遍历删除出错解决方案

    C++ STL list 遍历删除崩溃 错误用法一 下面这种用法会在for的地方崩溃,分析 第一次for循环的时候 it=0,当t.erase(it)执行完成之后 it就变成了 -17891602 表明it不能再作为迭代器进行运算,自然会报错. #include <map> #include <list> using namespace std; typedef std::list<int > TESTLIST; int _tmain(int argc, _TCHAR*

  • C++标准模板库STL的介绍

    介绍 STL(standard template library)标准模板库,是一种高效的C++程序库. STL分为三类:container(容器),iterator(迭代器)和algorithm(算法). 容器(container) 容器是用来管理某一类对象的集合,包括序列式容器和关联式容器. 序列式容器:vector,list,deque 关联式容器:map,set 遵循规则: 1.所有容器中存放的都是值而非引用.因此容器中的每个元素必须能够被拷贝,如想存放的不是副本,容器元素只能是指针.

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

  • C++中 STL list详解及简单实例

    C++中 STL list详解 1.List: 内部实现是一个双向链表,可以高效的进行插入删除,但不能够进行随机访问 2..示例程序: #include "stdafx.h" #include <iostream> #include <list> #include <iterator> #include <algorithm> using namespace std; const int num[5] = {1,3,2,4,5}; boo

  • 浅谈c++ stl迭代器失效的问题

    之前看<C++ Primier>的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究.今天写程序的时候遇到了这个问题. 1 莫名其妙的Erase 最初我的程序是酱紫的,别说话,我知道这样是有问题的,可这样是最直观的想法 int arr[]={0,1,2,3,4,5,6,7,8,9,10}; vector<int> a(arr,arr+sizeof(arr)/sizeof(*arr));for (auto it = a.begin(); it !=

  • C++ STL入门教程(7) multimap、multiset的使用

    一.multimap(一对多索引) C++ multimap和map所支持的操作相同(除了multimap不支持下标运算),但是multimap允许重复的元素. 完整程序代码: /*请务必运行以下程序后对照阅读*/ ///头文件依旧是map #include <map> #include <string> #include <iostream> using namespace std; int main() { ///1. 初始化 multimap<int, st

  • C++ STL入门教程(1) vector向量容器使用方法

    一.简介 Vectors 包含着一系列连续存储的元素,其行为和数组类似. 访问Vector中的任意元素或从末尾添加元素都可以在O(1)内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是O(N). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <vector> #include <iostream> #include <algorithm> #include <stdexcept> using namespace

  • C++ STL入门教程(6) set(集合)的使用方法

    一.简介 集合(Set)是一种包含已排序对象的关联容器,不允许有重复元素. 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <set> #include <iostream> using namespace std; int main() { ///1. 初始化 set<int> num; set<int>::iterator iter; cout << num.max_size() << endl;///s

  • C++ STL入门教程(3) deque双向队列使用方法

    一.简介 deque(Double Ended Queues,双向队列)和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <deque> #include <iostream> #include <algorithm> #include <stdexcept> using namespace std; void print(int num) { cout <&

随机推荐