C++判斷點在圖形內的條件

crazyway888

(1)題目:判斷點在三角形內，直角上點位於 (0,0) 另外兩點 (200 ，0) 、(0 ，100)。 請撰寫一程式，提示使用者輸入X與Y座標點，接著判斷點是否在三角形內 。(2)題目:請撰寫一程式，提示使用者輸入兩個矩形中心點X與Y，以及長與寬，接著判斷第二個矩形是否位於第一個矩形內或與第一個矩形重疊。
...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

1) 已知三角形ABC，求任意一點P是否在 ABC 內（習慣上，若P剛好在邊上也算在「內」）

方法依個人感覺由難到簡單排序

i)  "P 在 ABC 內" 若且唯若 "A和P在BC的同一半面 且 B和P在AC的同一半面 且 C和P在AB的同一半面"。

ii) 取三角形外任意一點Q，且 Q != P，作線段QP，
...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

2)

先從一維情形開始，也就是給定數線上兩個區間 A=[ Al, Ar ] 、B=[ Bl, Br ]，如何決定兩區間的關係？
為了方便，假設 A 的左端比較B的左端來的更左，也就是 Al <= Bl

a) 包含：Br <= Ar
b) 重疊：Bl <= Ar 且 Br > Ar
c) 分離：Bl > Ar

現在回到題目部份。題目給了長方形的中心點和邊長，所以我們可以求出長方形所在的二維區間，也就是找出這個長方形的x軸範圍是多少、y軸範圍是多少。接著就可以針對每一維去判斷重疊關係。
...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

不考慮誤差的話：

(2) 當 |x2-x1| <= (width1 + width2)/2 且 |y2-y1| <= (height1 + height2)/2 時兩矩形重疊，
     若重疊，再來考慮「第二個矩形是否位於第一個矩形內」？此時這問題容易處理，就略過囉

1.
   (0, 0), (200, 0), (0, 100) => 三邊為 x=0, y=0, x+2y=200

   所以輸入 X, Y 只要 X, Y 的值滿足 X > 0 and Y > 0 and X+2Y < 200
   X, Y 就在三角形內部
   
  if (X > 0 && Y > 0 && X+2*Y < 200)
  {
   // X, Y 在三角形內部
...

瀏覽完整內容，請先 註冊 或 登入會員

2.
    兩中心點X的距離小於兩矩形寬度和的一半且兩中心點Y的距離小於兩矩形高度和的一半則兩矩形有重疊

1. if (2*abs(x1-x2) < w1+w2 && 2*abs(y1-y2) < h1+h2) {
   
2. // 兩矩形有重疊
   
3. }

複製代碼

2. 第2矩形在第1矩形內部條件

   第2矩形的寬度及高度皆小於第1矩形(想當然爾, 不然如何包起來?)
   兩中心點X的距離+第2矩形的寬度一半小於第1矩形寬度的一半且
   兩中心點Y的距離+第2矩形的高度一半小於第1矩形高度的一半則第2矩形在第1矩形內部

1. if (w2<w1 && h2<h1 && 2*abs(x1-x2)+w2<w1 && 2*abs(y1-y2)+h2<h1)
   
2. {
   
3. //第2矩形在第1矩形內部
   
4. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

chevylin0802

gitlab 發表於 2015-1-21 04:38 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

1) 已知三角形ABC，求任意一點P是否在 ABC 內（習慣上，若P剛好在邊上也算在「內」）

方法依個人感覺由難 ...

...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

樓上顯然是錯的

考慮三角形A(0,0),  B(0,1) , C(1,0)
AB=AC=1, AC=sqrt(2)=1.414..

再考慮一點 P(0.5,0.55) ，明顯 P 在 ABC 之外
然而 PA=0.5 < PB=PC=sqrt(0.5^2+0.55^2)=0.743... < 1

事實上，以A為圓心、AB為半徑做弧BC
由弧BC和直線BC所圍起來的弓形區域，
裡面每一點都在ABC之外，而且與A,B,C的距離都小於1...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

chevylin0802 發表於 2015-9-18 11:26 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

太麻煩了
公式沒那麼複雜

不是很能理解你給的「公式」？

原以為你是不是給到必要條件了？

...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

gitlab 發表於 2015-9-19 12:31 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

樓上顯然是錯的

考慮三角形A(0,0),  B(0,1) , C(1,0)

幫你修正一點小瑕疵，這行

  PA=0.5 < PB=PC=sqrt(0.5^2+0.55^2)=0.743... < 1
...

瀏覽完整內容，請先 註冊 或 登入會員