今天下午在图书馆待了一下午的时间做出来这个作业题，首先来看以下这个题目

题目

这个题目标着三颗星，看起来很难，做起来有点难。

难点

我个人认为有以下几个难点：

  1. 判定一个点在三角形内是最难的
  2. 其实是一个三角形在另一个三角形内
  3. 其次是一个三角形和一个三角形重叠。

解决方案

  1. 判定一个点在三角形内。
    这个判定，我在网上搜索了很久并理解了很久才明白(hmmm，可能是我天资愚钝吧，好长时间才弄明白)
    1. 下图中的p 点在三角形p1p2p3中，我们可以看到向量p1->p2, 或者 p2->p3, 或者p3->p1，按照这个方向行走的话，这个p点始终在向量的右侧, 这样判定三次（三条边）就可以完成
    2. 但是在程序中我们就不能分辨出左右来，然后我们就判定p和向量的另外一点在同一侧就好了。例如向量p1->p2, 可见p和p3都在向量p1->p2的同侧，这样判定三次就可以判定出一个点在三角形内。

解决方案的代码如下

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
/** If p is in this triangle, return true; */
	public boolean contains(MyPoint p) {
		// The first edge
		boolean bool1 = sameSide(p1, p2, p, p3);
		boolean bool2 = sameSide(p1, p3, p, p2);
		boolean bool3 = sameSide(p2, p3, p, p1);

		if (bool1 && bool2 && bool3)
			return true;
		else
			return false;
	}

/** If p and p3 is on the same side, return true */
	public boolean sameSide(MyPoint p1, MyPoint p2, MyPoint p, MyPoint p3) {
		// Save the the product of the two vector product
		double a = vectorProduct(p1, p2, p3) * vectorProduct(p1, p2, p);
		if (a > 0)
			return true;
		else
			return false;
	}

/** Return the vector product for p->p2 and p2->p1 */
	public double vectorProduct(MyPoint p1, MyPoint p2, MyPoint p) {
		double x1 = p2.getX() - p.getX();
		double y1 = p2.getX() - p.getX();
		double Xab = p1.getX() - p2.getX();
		double Yab = p1.getX() - p2.getY();
		double vectorProduct = Xab * y1 - x1 * Yab;
		// double vectorProduct = x1 * Xab + y1 * Yab;
		return vectorProduct;
	}
  1. 一个三角形在另一个三角形内

我们判定成功了一个点在一个三角形内，那么我们就比较容易判定一个三角形在另一个三角形内了，我们只需要一个三角形中的三个点全部在另一个三角形中就好了
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
/** If t contains this triangle or this on the contrary, return true */
	public boolean contains(Triangle2D t) {
		// thisTriangle contains t
		boolean b1 = contains(t.getP1()) && contains(t.getP2()) && contains(t.getP3());
		boolean b2 = t.contains(p1) && t.contains(p2) && t.contains(p3);
		return b1 ^ b2;

		/*
		 * if(b1 && b2) { // If t contains this triangle and this triangle contains t,
		 * the two triangles are same }
		 */
	}
  1. 判定一个三角形和另一个三角形重叠
    1. 该怎么判定呢？三个点都在三角形外？显然不符合实际。一个点在三角形内也可以重叠啊
    2. 判定的方法是，只要有任意一条边与另外三遍有相交就好。。
      代码如下
      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
      /**
      	 * If this triangle overlaps t, return true Solution: any line has intersections
      	 * with the other triangle, then the two triangle overlap
      	 */
      	public boolean overlaps(Triangle2D t) {
      		// p1_p2 of triangle t and 3 edges in this
      		boolean b1 = lineIntersection(p1, p2, t.getP1(), t.getP2());
      		boolean b2 = lineIntersection(p2, p3, t.getP1(), t.getP2());
      		boolean b3 = lineIntersection(p1, p3, t.getP1(), t.getP2());
      		// p1_p3 of triangle t and 3 edges in this
      		boolean b4 = lineIntersection(p1, p2, t.getP1(), t.getP3());
      		boolean b5 = lineIntersection(p2, p3, t.getP1(), t.getP3());
      		boolean b6 = lineIntersection(p1, p3, t.getP1(), t.getP3());
      		// p2_p3 of triangle t and 3 edges in this
      		boolean b7 = lineIntersection(p1, p2, t.getP2(), t.getP3());
      		boolean b8 = lineIntersection(p2, p3, t.getP2(), t.getP3());
      		boolean b9 = lineIntersection(p1, p3, t.getP2(), t.getP3());
      		// return b1 || b2 || b3 || b4 || b5 || b6 || b7 || b8 || b9;
      		return b1 && b2 && b3 && b4 && b5 && b6 && b7 && b8 && b9;
      	}

      /** If two line intersect with each other, return true */
      	public boolean lineIntersection(MyPoint p1, MyPoint p2, MyPoint p3, MyPoint p4) {
      		double a = p1.getY() - p2.getY();
      		double b = p2.getX() - p1.getX();
      		double c = p3.getY() - p4.getY();
      		double d = p4.getX() - p3.getX();
      		double denominator = a * d - b * c;
      		if (denominator != 0) {
      			return true;
      		} else {
      			return false;
      		}
      	}

完整的测试代码如下

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
package answer.homework;

/**
 * @author Lutong99
 *
 */
public class Answer10_12 {
	/** Main method, in other word, this is testTriangle2D */
	public static void main(String[] args) {
		Triangle2D t1 = new Triangle2D(new MyPoint(2.5, 2), new MyPoint(4.2, 3), new MyPoint(5, 3.5));
		System.out.println("The area of the triangle t1 " + t1.toString() + " is " + t1.getArea()
				+ ", and its perimeter is " + t1.getPerimeter());
		System.out.println("t1.contains(3, 3) is " + t1.contains(new MyPoint(3, 3)));
		System.out.println("t1.contains(new Triangle2D(new MyPoint(2.9, 2), new MyPoint(4, 1), MyPoint(1, 3.4))) is "
				+ t1.contains(new Triangle2D(new MyPoint(2.9, 2), new MyPoint(4, 1), new MyPoint(1, 3.4))));
		System.out
				.println("t1.overlaps(new Triangle2D(new MyPoint(2, 5.5), new MyPoint(4, -3), new MyPoint(2, 6.5))) is "
						+ t1.overlaps(new Triangle2D(new MyPoint(2, 5.5), new MyPoint(4, -3), new MyPoint(2, 6.5))));
//		System.out
//				.println("t1.overlaps(new Triangle2D(new MyPoint(2.9, 2), new MyPoint(4, 1), new MyPoint(1, 3.4)))) is "
//						+ t1.overlaps(new Triangle2D(new MyPoint(2.9, 2), new MyPoint(4, 1), new MyPoint(1, 3.4))));
	}
}

class Triangle2D {
	private MyPoint p1;
	private MyPoint p2;
	private MyPoint p3;

	public Triangle2D() {
		this.p1 = new MyPoint(0, 0);
		this.p2 = new MyPoint(1, 1);
		this.p3 = new MyPoint(2, 5);
	}

	public Triangle2D(MyPoint p1, MyPoint p2, MyPoint p3) {
		this.p1 = p1;
		this.p2 = p2;
		this.p3 = p3;
	}

	public MyPoint getP1() {
		return p1;
	}

	public void setP1(double x, double y) {
		p1 = new MyPoint(x, y);
	}

	public MyPoint getP2() {
		return p2;
	}

	public void setP2(double x, double y) {
		p2 = new MyPoint(x, y);
	}

	public MyPoint getP3() {
		return p3;
	}

	public void setP3(double x, double y) {
		p3 = new MyPoint(x, y);
	}

	public double getPerimeter() {
		return p1.distance(p2) + p1.distance(p3) + p2.distance(p3);
	}

	public double getArea() {
		double a = p1.distance(p2);
		double b = p1.distance(p3);
		double c = p2.distance(p3);
		double p = this.getPerimeter() / 2;
		return Math.sqrt(p * (p - a) * (p - b) * (p - c));
//		return Math.sqrt(this.getPerimeter() / 2 * (this.getPerimeter() / 2 - p1.distance(p2))
//				* (this.getPerimeter() / 2 - p1.distance(p3)) * (this.getPerimeter() / 2 - p2.distance(p3)));
	}

	/** If p is in this triangle, return true; */
	public boolean contains(MyPoint p) {
		// The first edge
		boolean bool1 = sameSide(p1, p2, p, p3);
		boolean bool2 = sameSide(p1, p3, p, p2);
		boolean bool3 = sameSide(p2, p3, p, p1);

		if (bool1 && bool2 && bool3)
			return true;
		else
			return false;

	}

	/** If t contains this triangle or this on the contrary, return true */
	public boolean contains(Triangle2D t) {
		// thisTriangle contains t
		boolean b1 = contains(t.getP1()) && contains(t.getP2()) && contains(t.getP3());
		boolean b2 = t.contains(p1) && t.contains(p2) && t.contains(p3);
		return b1 ^ b2;

		/**
		 * if(b1 && b2) { // If t contains this triangle and this triangle contains t,
		 * the two triangles are same } but maybe it is not right
		 */
	}

	/**
	 * If this triangle overlaps t, return true Solution: any line has intersections
	 * with the other triangle, then the two triangle overlap
	 */
	public boolean overlaps(Triangle2D t) {
		// p1_p2 of triangle t and 3 edges in this
		boolean b1 = lineIntersection(p1, p2, t.getP1(), t.getP2());
		boolean b2 = lineIntersection(p2, p3, t.getP1(), t.getP2());
		boolean b3 = lineIntersection(p1, p3, t.getP1(), t.getP2());
		// p1_p3 of triangle t and 3 edges in this
		boolean b4 = lineIntersection(p1, p2, t.getP1(), t.getP3());
		boolean b5 = lineIntersection(p2, p3, t.getP1(), t.getP3());
		boolean b6 = lineIntersection(p1, p3, t.getP1(), t.getP3());
		// p2_p3 of triangle t and 3 edges in this
		boolean b7 = lineIntersection(p1, p2, t.getP2(), t.getP3());
		boolean b8 = lineIntersection(p2, p3, t.getP2(), t.getP3());
		boolean b9 = lineIntersection(p1, p3, t.getP2(), t.getP3());
		// return b1 || b2 || b3 || b4 || b5 || b6 || b7 || b8 || b9;
		return b1 && b2 && b3 && b4 && b5 && b6 && b7 && b8 && b9;
	}

	/** If p and p3 is on the same side, return true */
	public boolean sameSide(MyPoint p1, MyPoint p2, MyPoint p, MyPoint p3) {
		// Save the the product of the two vector product
		double a = vectorProduct(p1, p2, p3) * vectorProduct(p1, p2, p);
		if (a > 0)
			return true;
		else
			return false;
	}

	/** Return the vector product for p->p2 and p2->p1 */
	public double vectorProduct(MyPoint p1, MyPoint p2, MyPoint p) {
		double x1 = p2.getX() - p.getX();
		double y1 = p2.getX() - p.getX();
		double Xab = p1.getX() - p2.getX();
		double Yab = p1.getX() - p2.getY();
		double vectorProduct = Xab * y1 - x1 * Yab;
		// double vectorProduct = x1 * Xab + y1 * Yab;
		return vectorProduct;
	}

	/** If two line intersect with each other, return true */
	public boolean lineIntersection(MyPoint p1, MyPoint p2, MyPoint p3, MyPoint p4) {
		double a = p1.getY() - p2.getY();
		double b = p2.getX() - p1.getX();
		double c = p3.getY() - p4.getY();
		double d = p4.getX() - p3.getX();
		double denominator = a * d - b * c;
		if (denominator != 0) {
			return true;
		} else {
			return false;
		}
	}

	/** Decide if a point p is on the line p1->p2 */
	public boolean onSegment(MyPoint p1, MyPoint p2, MyPoint p) {
		double parameter = (p2.getX() - p1.getX()) * (p.getY() - p1.getY())
				- (p.getX() - p1.getX()) * (p2.getY() - p1.getY());
		if (parameter == 0 && p.getX() <= Math.max(p1.getX(), p2.getX()) && p.getX() >= Math.min(p1.getX(), p2.getX())
				&& p.getY() <= Math.max(p1.getY(), p2.getY()) && p.getY() >= Math.min(p1.getY(), p2.getY()))
			return true;
		else
			return false;
	}

	/** Return the point intersection */
	public MyPoint getIntersection(MyPoint p1, MyPoint p2, MyPoint p3, MyPoint p4) {
		MyPoint point;
		double a = p1.getY() - p2.getY();
		double b = p2.getX() - p1.getX();
		double c = p3.getY() - p4.getY();
		double d = p4.getX() - p3.getX();
		double e = (p1.getY() - p2.getY()) * p1.getX() - (p1.getX() - p2.getX()) * p1.getY();
		double f = (p3.getY() - p4.getY()) * p3.getX() - (p3.getX() - p4.getX()) * p3.getY();
		double denominator = a * d - b * c;
		if (denominator != 0) {
			double x = (e * d - b * f) / denominator;
			double y = (a * f - e * c) / denominator;
			point = new MyPoint(x, y);
		} else {
			point = new MyPoint(-999, -999); // If there is no intersection, return point (-999, -999)
		}
		return point;
	}

	@Override
	public String toString() {
		return "[" + p1.toString() + "," + p2.toString() + ", " + p3.toString() + "]";
	}
}

运行结果如下

1
2
3
4
The area of the triangle t1 [(2.5, 2.0),(4.2, 3.0), (5.0, 3.5)] is 0.02500000000000299, and its perimeter is 5.831182352959913
t1.contains(3, 3) is false
t1.contains(new Triangle2D(new MyPoint(2.9, 2), new MyPoint(4, 1), MyPoint(1, 3.4))) is false
t1.overlaps(new Triangle2D(new MyPoint(2, 5.5), new MyPoint(4, -3), new MyPoint(2, 6.5))) is true

以上如果有错误

以上如果有错误，欢迎联系我改正，非常欢迎大家帮助我，谢谢