文章/答案/技术大牛

发布

社区首页 >问答首页 >确定两个线段是否相交的C++过程

问确定两个线段是否相交的C++过程
EN

Stack Overflow用户

提问于 2013-03-09 21:05:42

回答 1查看 5.6K关注 0票数 6

我最近在做一些计算几何的工作，我试图找到一种方法来检查两条线段是否相交。我想我可以使用逆时针方向(简称CCW)来确定这一点。到目前为止，我的代码如下：

struct point { double x, y };

double CCW(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }

int intersect(point a, point b, point c, point d)
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); }

上面的代码适用于我输入的测试用例，可读性很好，很容易实现。但在网上搜索后，我发现了另一种解决分段相交问题的方法。代码类似于我的代码，但是它有一些我的实现省略的if语句。代码如下：

struct line { point s, e; };

int middle(int a, int b, int c) {
  int t;    
  if ( a > b ) {
    t = a;
    a = b;
    b = t;
  }
  if ( a <= c && c <= b ) return 1;
  return 0;
}

int intersect(line a, line b) {
  if ( ( CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0 ) &&
     ( CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0 ) ) return 1;

  if ( CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y) ) return 1;
  if ( CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y) ) return 1;
  if ( CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y) ) return 1;
  if ( CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y) ) return 1;

    return 0;
}

谁能解释一下这两种实现之间的区别，以及使用哪种实现更安全？提前谢谢。

c++

algorithm

geometry

computational-geometry

segments

回答 1

Stack Overflow用户

回答已采纳

发布于 2013-03-09 21:13:51

您找到的函数还会检查线段位于同一条线内的情况。在这种情况下，查找两条线段是否重叠就变成了一个一维问题。在这种情况下，您的代码将返回false。这是否是首选取决于应用程序。

示例：

point a={1,0}, b={3,0}, c={2,0}, d={4,0};

intersect(a,b,c,d); // your function will return false, 
                    // but the one you found will return true

您找到的函数还会查看一条直线段的端点位于另一条直线段的情况：

示例：

point a={1,0}, b={3,0}, c={2,0}, d={2,3};

intersect(a,b,c,d); // your function will return false, 
                    // but the one you found will return true

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15311018

复制

相似问题

问确定两个线段是否相交的C++过程
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问确定两个线段是否相交的C++过程EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问确定两个线段是否相交的C++过程
EN