工作中的一件小事引發的思考

1 人贊了文章

今天和一個同事聊天，他突然提到他們正在做一個矩形的旋轉縮放等變換操作，然後怎麼去判斷一個人的操作是否還是在圖形裡面。

思索了一會，突然想起來這不是我之前在學校學過的凸包演算法嗎？判斷一個點是否在多邊形裡面，而這僅僅是一個簡單的矩形而已。不由得想起我的導師——劉少華老師，一位和藹可親的老師。不曾想到之前老師在課堂上講述的東西，今天竟然在這裡用上了。

於是和我同事講述到：先計算出矩形的變化之後的四個點的坐標，然後根據凸包演算法判斷點是否在圖形裡面即可。

下面附上原理和代碼

如何判斷一個點是否在多邊形內部？

(1)面積和判別法：判斷目標點與多邊形的每條邊組成的三角形面積和是否等於該多邊形，相等則在多邊形內部。

(2)夾角和判別法：判斷目標點與所有邊的夾角和是否為360度，為360度則在多邊形內部。

(3)引射線法：從目標點出發引一條射線，看這條射線和多邊形所有邊的交點數目。如果有奇數個交點，則說明在內部，如果有偶數個交點，則說明在外部。

具體做法：將測試點的Y坐標與多邊形的每一個點進行比較，會得到一個測試點所在的行與多邊形邊的交點的列表。在下圖的這個例子中有8條邊與測試點所在的行相交，而有6條邊沒有相交。如果測試點的兩邊點的個數都是奇數個則該測試點在多邊形內，否則在多邊形外。在這個例子中測試點的左邊有5個交點，右邊有三個交點，它們都是奇數，所以點在多邊形內。

public boolean isInPolygon(Point point, Point[] points, int n) {

int nCross = 0;

for (int i = 0; i < n; i++) {

Point p1 = points[i];

Point p2 = points[(i + 1) % n];

// 求解 y=p.y 與 p1 p2 的交點

// p1p2 與 y=p0.y平行

if (p1.y == p2.y)

continue;

// 交點在p1p2延長線上

if (point.y < Math.min(p1.y, p2.y))

continue;

// 交點在p1p2延長線上

if (point.y >= Math.max(p1.y, p2.y))

continue;

// 求交點的 X 坐標

double x = (double) (point.y - p1.y) * (double) (p2.x - p1.x)

/ (double) (p2.y - p1.y) + p1.x;

// 只統計單邊交點

if (x > point.x)

nCross++;

}

return (nCross % 2 == 1);

}

今日小記

雖然才畢業不到兩個月，但是卻有種感覺很久的感覺。也許是工作上的忙碌，已經忘記了時間的緣故吧。一件小事，勾起了對老師的懷念、對學校生活的懷念。也深感慚愧，在學校犯錯的時候，老師指出的時候，自己有時候嘻嘻哈哈敷衍了事，但是在工作如果還是敷衍了事，後果將不堪設想，所以也開始慢慢養成嚴謹的態度。

——2018.8.15記

下面是我的公眾號(zgzfblog)，如果有喜歡我的文字，歡迎關注，希望把正能量傳遞給更多的人。

長按下面的二維碼關注我的公眾號

http://weixin.qq.com/r/MylAWFrEowfcrR4793wh (二維碼自動識別)

推薦閱讀：