🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Checking if a point lies in a circle through 3 points in 2D

Started by
3 comments, last by CHAN HAENG Lee 5 years, 8 months ago

Hi. I'm studying collision detection by the book "Real Time Collision Detection"

And I have a question about the math of checking if a point lies in a circle through 3d points in 2D.

Actually, I understand the principle of the equation or algorithm. However, the determinant expression 

gif.latex?%5Cdpi%7B100%7D%20INCIRCLE2D%28A%2CB%2CC%2CD%29%20%3D%20%5Cbegin%7Bvmatrix%7D%20a_x%20%26%20a_y%20%26%20a%5E2_x%20+%20a%5E2_y%20%26%201%20%5C%5C%20b_x%20%26%20b_y%20%26%20b%5E2_x%20+%20b%5E2_y%20%26%201%20%5C%5C%20c_x%20%26%20c_y%20%26%20c%5E2_x%20+%20c%5E2_y%20%26%201%20%5C%5C%20d_x%20%26%20d_y%20%26%20d%5E2_x%20+%20d%5E2_y%20%26%201%20%5Cend%7Bvmatrix%7D%20%3D%20%5Cbegin%7Bvmatrix%7D%20a_x%20-%20d_x%20%26%20a_y%20-%20d_y%20%26%20a%5E2_x%20-%20d%5E2_x%20+%20a%5E2_y%20-%20d%5E2_y%5C%5C%20b_x%20-%20d_x%20%26%20b_y%20-%20d_y%20%26%20b%5E2_x%20-%20d%5E2_x%20+%20b%5E2_y%20-%20d%5E2_y%5C%5C%20c_x%20-%20d_x%20%26%20c_y%20-%20d_y%20%26%20c%5E2_x%20-%20d%5E2_x%20+%20c%5E2_y%20-%20d%5E2_y%5C%5C%20%5Cend%7Bvmatrix%7D%20%3D%20%5Cbegin%7Bvmatrix%7D%20a_x%20-%20d_x%20%26%20a_y%20-%20d_y%20%26%20%28a_x%20-%20d_x%29%5E2%20+%20%28a_y%20-%20d_y%29%5E2%5C%5C%20b_x%20-%20d_x%20%26%20b_y%20-%20d_y%20%26%20%28b_x%20-%20d_x%29%5E2%20+%20%28b_y%20-%20d_y%29%5E2%5C%5C%20c_x%20-%20d_x%20%26%20c_y%20-%20d_y%20%26%20%28c_x%20-%20d_x%29%5E2%20+%20%28c_y%20-%20d_y%29%5E2%5C%5C%20%5Cend%7Bvmatrix%7D

is hard to understand for me, especially converting the second expression to third expression.

 

I know the row replacement in the determinant doesn't change the value of the determinant. So, I have a grasp of converting the first expression to second expression.

However, I can't tell the second conversion, on the third column.

How is it possible gif.latex?A%5E2_x%20-%20D%5E2_x%20+%20A%5E2_y%20-%20D%5E2_y%20%3D%20%28A_x%20-%20D_x%29%5E2%20+%20%28A_y%20-%20D_y%29%5E2

I will appreciate you ahead if you let me know this.

 

You can check this equation in the wikipedia https://en.wikipedia.org/wiki/Delaunay_triangulation

 

Advertisement

Sorry, just woke up... I must have had Freshman’s Dream

🙂🙂🙂🙂🙂<←The tone posse, ready for action.

When computing a determinant, you can scale a column and add it to another column without changing the result. So if you add (-2D_x) times the first column and (-2D_y) times the second column to the third column, you'll get the transformation you see.

 

 

Thanks @alvaro !!

I didn't know why i didn't try to do a column replacement. 

Thanks to you, I can sleep well tonight.

This topic is closed to new replies.

Advertisement