计算几何01-判定两条线段是否相交

两条线段相交当且仅当下面两个条件至少成立一个：

1.每条线段都跨越了包含另一条线段的直线。
2.一条线段的某个端点落在了另一条线段上。（这一情况来自于边界情况）

在判断线段的相交时我们可以利用向量的叉积。当两条向量在一条直线上时，向量的叉积等于 0 ，即上面的第二种情况，所以判断两条线段相交就分为两种情况讨论：1.向量的叉积不等于 0 ；2.向量的叉积等于 0 。

一.叉积不等于 0

首先：我们要判断点 p3，p4 分布在线段 p1 p2 两边。如下图所示：

① 根据向量的叉积，如果 p1p4 * p1p2 > 0 则表示向量 p1p2 在向量 p1p4 的逆时针方向，根据 p1p2 * p1p3 > 0，可以判断 p1p3 在 p1p2 的逆时针方向。这时就可以判断点p3，p4 在线段 p1p2 的两端。

② 同理，我们可以判断 p1,p2 分布在线段 p3 p4 的两端。

如果同时满足①，② 成立，则这两个线段就相交

二.叉积等于 0

当叉积等于 0 的时候，只需要判断这三个点是否在同一条直线上就可以了。

java 代码如下：

/**
 * @author corlymeng.com
 * @date  2015年9月16日
 */
package geometry;

import java.util.Scanner;

public class Segment {
	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	private int direction(int[] pi, int[] pj, int[] pk){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	/**
	 * 判断点pk是否在线段 pi,pj 上
	 * @return boolean
	 */
	private boolean onSegment(int[] pi, int[] pj, int[] pk) {
		if ( Math.min(pi[0], pj[0]) <= pk[0] && pk[0] <= Math.max(pi[0], pj[0]) && 
			 Math.min(pi[1], pj[1]) <= pk[1] && pk[1] <= Math.max(pi[1], pj[1]) ) {
			return true;
		}else {
			return false;
		}
	}
	// 判断线段 p1,p2 和线段 p3,p4 是否相交
	public boolean segmentInsert(int[] p1, int[] p2, int[] p3, int[] 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;
		}
	}
	
	public static void main(String[] args){
		Segment segment = new Segment();
		Scanner in = new Scanner(System.in);
		int[] p1 = {in.nextInt(), in.nextInt()};
		int[] p2 = {in.nextInt(), in.nextInt()};
		int[] p3 = {in.nextInt(), in.nextInt()};
		int[] p4 = {in.nextInt(), in.nextInt()};
		if (segment.segmentInsert(p1, p2, p3, p4)) {
			System.out.println("相交");
		} else {
			System.out.println("不相交");
		}
	}
}