记录一道很简单很简单的入门题…核心就是一个我高中就学过的数学知识…叉积…可惜年久不用…在面试的紧要关头就显得呆若木鸡…很遗憾没有表现出自己的真实水平…

/* *

* 在一个平面中.任意一个直线线段可以由2个点表示,任意一个点可以由X,Y坐标值表示.

*例如线段 J 由 点A(x1, y1), B(x2, y2)表示. 其中坐标值 x,y 都为int.

 *求写出一个方法, boolean checkIntersect(Line J, Line K);

 *检查在平面中给出的2个线段是否相交, return true 代表线段相交, false 为不想交.

 *请自行定义线段Line的数据结构, 并可以假设传入参数Line J 和 Line K 为有效输入.

 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package aiqyInterview;
public class CheckIntersect {
	/**
	 * 
	 * @author EdwardZhang
	 * 判断线段相交：
	 * 两个线段的交点个数可能有0个 1个或者无数个
	 * 判断两个线段相交，可以按照如下步骤：
	 * 判断A点B点是否在线段CD的两侧，即计算叉积时异号
	 * 判断C点和D点是否在线段AB的两侧，即计算叉积时异号
	 * 然后在处理特殊情况，即ABCD四个点有至少三个点共线的情况，
	 * 即出现叉积为零的情况，如果A点与线段CD共线，
	 * 则要查看A点是否在线段CD上，其它情况依次类推。
	 */
	class Point {
		int x;
		int y;
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}
	}
	class Line {
		Point A = new Point();
		Point B = new Point();
		public Point getA() {
			return A;
		}
		public void setA(int i, int j) {
			A.x = i;
			A.y = j;
		}
		public Point getB() {
			return B;
		}
		public void setB(int i, int j) {
			B.x = i;
			B.y = j;
		}
	}
	public static float direct(Point i, Point j, Point k) { // 计算叉积
		return (k.x - i.x) * (j.y - i.y) - (j.x - i.x) * (k.y - i.y);
	}
	public static boolean onSegment(Point a, Point b, Point c) { // 共线时，判断点是否落在线段
		float minx = Math.min(a.x, b.x);
		float maxx = Math.max(a.x, b.x);
		float miny = Math.min(a.y, b.y);
		float maxy = Math.max(a.y, b.y);
		if (c.x >= minx && c.x <= maxx && c.y >= miny && c.y <= maxy) {
			return true;
		}
		return false;
	}
	public static boolean checkIntersect(Line X, Line Y) {
		float d1 = direct(Y.A, Y.B, X.A);
		float d2 = direct(Y.A, Y.B, X.B);
		float d3 = direct(X.A, X.B, Y.A);
		float d4 = direct(X.A, X.B, Y.B);
		if (d1 * d2 < 0 && d3 * d4 < 0)
			return true;
		else if (d1 == 0 && onSegment(Y.A, Y.B, X.A))
			return true;
		else if (d2 == 0 && onSegment(Y.A, Y.B, X.B))
			return true;
		else if (d3 == 0 && onSegment(X.A, X.B, Y.A))
			return true;
		else if (d4 == 0 && onSegment(X.A, X.B, Y.B))
			return true;
		return false;
	}
	public static void main(String[] args) {
		CheckIntersect checkIntersect = new CheckIntersect();
		Line a = checkIntersect.new Line();
		Line b = checkIntersect.new Line();
		a.setA(0, 0);
		a.setB(2, 2);
		b.setA(2, 0);
		b.setB(0, 2);
		System.out.println(checkIntersect(a,b));//相交 true
		a.setA(0, 0);
		a.setB(2, 2);
		b.setA(2, 0);
		b.setB(1, 0);
		System.out.println(checkIntersect(a,b));//相离 false
		a.setA(0, 0);
		a.setB(2, 2);
		b.setA(2, 0);
		b.setB(4, 2);
		System.out.println(checkIntersect(a,b));//平行 false
		a.setA(0, 0);
		a.setB(2, 2);
		b.setA(1, 1);
		b.setB(3, 3);
		System.out.println(checkIntersect(a,b));//在一条直线上 true
	}
}