有人問我，怎么判斷一個點是不是在多邊形內，本來想著把這個多邊形分成一個又一個三角形，如圖，
然后判斷這個點是不是在某個三角形中，如果在，那就肯定在這個多邊形中，那問題接下來就轉化成判斷這個點是不是在三角形中了，只要這個點D和三角形的三個點A、B、C組合的三角形a、b、c的面積之和等于這個三角形的面積，就說明這個點在三角形中，如圖。
代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public boolean isInTriangle(Point A, Point B, Point C, Point P) { double ABC = triAngleArea(A, B, C); double ABp = triAngleArea(A, B, P); double ACp = triAngleArea(A, C, P); double BCp = triAngleArea(B, C, P); if ((int) ABC == (int) (ABp + ACp + BCp)) {// 若面積之和等于原三角形面積，證明點在三角形內,這里做了一個約等于小數點之后沒有算（25714.25390625、25714.255859375） return true; } else { return false; } } private double triAngleArea(Point A, Point B, Point C) {// 由三個點計算這三個點組成三角形面積 double result = Math.abs((A.getX() * B.getY() + B.getX() * C.getY() + C.getX() * A.getY() - B.getX() * A.getY() - C.getX() * B.getY() - A.getX() * C.getY()) / 2.0D); return result; } |
一切看起來那么合情合理，代碼寫完了，也測試了都沒有問題啦！但是最后我發現忽略了一個問題，還有一種多邊形的情況沒有考慮到，那就是香蕉形的多邊形，如圖：
這個問題一出來，我立刻蒙圈啦，這個應該怎么做，最后在網上找到了解決辦法，那就是沿著這個點做平行線，如果這個點單側和多邊形相交的點為奇數，就說明這個點在這個多邊形中，如圖：
代碼如下：
|
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
|
/** * 功能：判斷點是否在多邊形內 方法：求解通過該點的水平線與多邊形各邊的交點 結論：單邊交點為奇數，成立! * * @param point * 指定的某個點 * @param APoints * 多邊形的各個頂點坐標（首末點可以不一致） * @return */public boolean PtInPolygon(Point point, List<Point> APoints) { int nCross = 0; for (int i = 0; i < APoints.size(); i++) { Point p1 = APoints.get(i); Point p2 = APoints.get((i + 1) % APoints.size()); // 求解 y=p.y 與 p1p2 的交點 if (p1.getY() == p2.getY()) // p1p2 與 y=p0.y平行 continue; if (point.getY() < Math.min(p1.getY(), p2.getY())) // 交點在p1p2延長線上 continue; if (point.getY() >= Math.max(p1.getY(), p2.getY())) // 交點在p1p2延長線上 continue; // 求交點的 X 坐標 // -------------------------------------------------------------- double x = (double) (point.getY() - p1.getY()) * (double) (p2.getX() - p1.getX()) / (double) (p2.getY() - p1.getY()) + p1.getX(); if (x > point.getX()) nCross++; // 只統計單邊交點 } // 單邊交點為偶數，點在多邊形之外 --- return (nCross % 2 == 1); } |
項目下載：一個點是否在多邊形中
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/u014544193/article/details/50698015
