0
$\begingroup$

I'm trying to implement the InCircle test with this determinant from page 36: http://graphics.stanford.edu/courses/cs268-16-fall/Notes/torino.pdf

Several authors of their implementations use cofactors to get the 3x3 matrices and then convert calculating the area of the triangle with a 3×3 determinant to calculating the cross product:

\begin{vmatrix} x_A & y_A & 1\\ x_B & y_B & 1\\ x_C & y_C & 1\\ \end{vmatrix}

converts to:

\begin{vmatrix} x_B - x_A & x_C - x_A\\ y_B - y_A & y_C - y_A \end{vmatrix}

or (b.x - a.x)(c.y - a.y) - (b.y - a.y)(c.x - a.x) in code.

Someone suggested that it can be done with this: https://en.wikipedia.org/wiki/Dodgson_condensation, but I can't make it work. Which rule allows that transformation to happen? Please help.

You can see an example of an implementation here on page 10 (functions TriArea and InCircle): https://www.researchgate.net/profile/Dani_Lischinski/publication/262235495_Incremental_Delaunay_Triangulation/links/5af699330f7e9b026bceff5b/Incremental-Delaunay-Triangulation.pdf

$\endgroup$
4
  • $\begingroup$ Can you say what you want to prove? If you are trying to prove that the two determinants you actually write down are equal, that's very simple: take first row from each of other two. If you want to relate the first determinant to something in the enormous paper please edit the question (actually type it into the question) to make that clear. $\endgroup$ – ancient mathematician Dec 30 '20 at 10:44
  • $\begingroup$ I'm just looking for the rule which makes this transformation possible. I can sort of guess it, but I don't know what it is called. The overall goal is to compute the 4x4 determinanat (volume of the tetrahedron) using the cross product. $\endgroup$ – user143982 Dec 30 '20 at 11:05
  • $\begingroup$ Subtract 1st row from 2nd and 3rd row in first determinant, the last column becomes one which has one only one non-zero entry (at first row). expand whole thing against last column and transpose. The handling for tetrahedron is similar. $\endgroup$ – achille hui Dec 30 '20 at 11:41
  • $\begingroup$ Thanks, you really helped me the most. I have forgotten about elementary row operations. $\endgroup$ – user143982 Dec 30 '20 at 20:31
0
$\begingroup$

Swap two columns and then two rows, then use Dodgson condensation, take a transpose, and change the sign of off-diagonal elements:$$\begin{align}\left|\begin{array}{ccc}x_A&y_A&1\\x_B&y_B&1\\x_C&y_C&1\end{array}\right|&=-\left|\begin{array}{ccc}x_A&1&y_A\\x_B&1&y_B\\x_C&1&y_C\end{array}\right|\\&=\left|\begin{array}{ccc}x_B&1&y_B\\x_A&1&y_A\\x_C&1&y_C\end{array}\right|\\&=\left|\begin{array}{cc}x_B-x_A&y_A-y_B\\x_A-x_C&y_C-y_A\end{array}\right|\\&=\left|\begin{array}{cc}x_B-x_A&x_A-x_C\\y_A-y_B&y_C-y_A\end{array}\right|\\&=\left|\begin{array}{cc}x_B-x_A&x_C-x_A\\y_B-y_A&y_C-y_A\end{array}\right|.\end{align}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.