计算几何——线段的性质

本次我们研究线段的一些性质，并且可以用一些数学知识设计一些算法来解决一些问题。

问题：

对于这些问题，我们都需要使用一个计算公式——叉积（又称向量积、外积）。

向量积/叉积

叉积的计算是线段方法的核心。

如果p1=(x1, y1)，p2=(x2,y2)。那么p1×p2 = x1y2 - x2y1。

可以看作行列式的计算即

情况有：

1.若p1 × p2为正值，那么相对于原点(0, 0)来说，p1位于p2的顺时针方向；

2.相反为负值，则p1位于p2的逆时针方向。

3.如果叉积值为0，那么就出现了边界情况。这个情况下，两个向量共线。

利用叉积解决线段问题：

问题一：

对于给定的两个有向线段p0p1和p0p2，相对于它们的公共端点p0来说，p0p1是否在p0p2的顺时针方向？

假设p0=(x0, y0) , p1=(x1, y1) , p2=(x2, y2)

那么p1-p0 = (x0-x1 , y0-y1) ; p2-p0 = (x0-x2 , y0-y2)

解决：

根据上面的叉积公式我们可以通过求(p1 - p0) × (p2 - p1) 判断值的正负性从而判断出p0p1是在p0p2的顺时针还是逆时针。

问题二：

对于给定的两个线段p0p1和p1p2，如果先沿着p0p1再沿着p1p2前进，那么在点p1处是向左转还是向右转怎么判断。

解决：

我们只需判断一下有向线段p0p2是位于p0p1的顺时针方向还是逆时针方向就可以了。所以计算一下(p2 - p0) × (p1 - p0)，判断值的正负性即可，如果为负，则p0p2位于p0p1的逆时针方向，在p1处左转，同理为正，则顺时针，右转。

问题三：

判断线段p1p2和p3p4是否相交？

判断两线段是否相交，需要检查每条线段是否跨越了包含另一条线段的直线。如果点p1位于某条直线的一边，而点p2位于该直线的另一边，则称p1p2跨越了这条边。

代码如下：

#include
#include
using namespace std;
struct Node{int x, y;
};
int Direction(Node a, Node b, Node c)
{return (c.x-a.x) * (b.y-a.y) - (b.x-a.x) * (c.y - a.y);
}bool OnSegment(Node a, Node b, Node c)
{ if(min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x) && min(a.y, b.y) <= c.y && c.y <= (a.y, b.y)){return true;}else return false;
}bool SegmentIntersect(Node p1, Node p2, Node p3, Node p4)
{int d1 = Direction(p3, p4, p1);int d2 = Direction(p3, p4, p2);int d3 = Direction(p1, p2, p3);int d4 = Direction(p1, p2, p4);if((d1<0&&d2>0) || (d1>0&&d2<0) || (d3<0&&d4>0) || (d3>0&&d4<0)){return true;}else if(d1==0 && OnSegment(p3, p4, p1)){return true;}else if(d2==0 && OnSegment(p3, p4, p2)){return true;}else if(d3==0 && OnSegment(p1, p2, p3)){return true;}else if(d4==0 && OnSegment(p1, p2, p4)){return true;}else return false;
}int main()
{Node a, b, c, d;printf("输入两条直线：");printf("直线ab:\n"); printf("点a:");scanf("%d%d",&a.x,&a.y);printf("点b:");scanf("%d%d",&b.x,&b.y);printf("直线cd:\n"); printf("点c:");scanf("%d%d",&c.x,&c.y);printf("点d:");scanf("%d%d",&d.x,&d.y);if(SegmentIntersect(a,b,c,d)){printf("ab与cd相交\n");}else{printf("ab与cd不相交\n"); } return 0;
}