Determinant (computational geometry)

Question

Let p=(px,py),q=(qx,qy), and r=(rx,ry).Show that the sign of the determinant

    |1 px py|
  D=|1 qx qy|
    |1 rx ry|

determines whether a point r lies to the left or right of the directed line pq. ( I know that this true, not exactly sure how to show this)

Answer 1

We know that we can write the line $PQ$ as

$$k_1x+k_2y=1$$

And we know it is satisfied for both point $P$ and point $Q$. So we have a system of equations:

$$\begin{cases} k_1p_x+k_2p_y=1\\ k_1q_x+k_2q_y=1 \end{cases}$$

We can solve for both $k_1$ and $k_2$ because this is two equations and two unknowns.

$$k_1 = \frac{p_y-q_y}{p_yq_x-p_xq_y}$$ $$k_2 = \frac{q_x-p_x}{p_yq_x-p_xq_y}$$

Which just means we can rewrite our equations as:

$$(p_y-q_y)x+(q_x-p_x)y=p_yq_x-p_xq_y\tag{1}$$

Consider the matrix $A$

$$A=\left[\begin{matrix}1 & p_x & p_y\\ 1 & q_x & q_y\\ 1 & r_x & r_y\end{matrix}\right]$$

You can work out that $\det[A]=(p_xq_y-p_yq_x)+(p_yr_x-p_xr_y)+(q_xr_y-q_yr_x)$

---

Clearly, if $R$ is on the line, then $x=r_x$ and $y=r_y$ satisfies $(1)$ and we have

$$(p_yr_x-p_xr_y)+(q_xr_y-q_yr_x)=p_yq_x-p_xq_y$$

which is the same as

$$(p_yr_x-p_xr_y)+(q_xr_y-q_yr_x)+(p_xq_y-p_yq_x)=0=\det[A]$$

So if $\det[A]=0$, then the point $R$ is on the line $PQ$.

---

Now suppose that $\det[A]\ne0$ which means that $R$ is not on the line. Let $r_y'$ be such that the point $R'=(r_x,r_y')$ is on the line.

We can solve for $r_y'$ in $(1)$

$$r_y'=\frac{p_yq_x-p_xq_y+r_x(q_y-p_y)}{q_x-p_x}$$

If $\det[A]>0$ then $(p_yr_x-p_xr_y)+(q_xr_y-q_yr_x)+(p_xq_y-p_yq_x)>0$. We can isolate $r_y$ in this inequality and get

$$r_y>\frac{p_yq_x-p_xq_y+r_x(q_y-p_y)}{q_x-p_x}=r_y'$$

Therefore, if $\det[A]>0$ then $r_y>r_y'$. And since we know that $R$ and $R'$ share an $x$ value, we know that $r_y$ is above $r_y'$ which is on the line. And therefore we know that $r_y$ is above the line.

---

The exact same is followed for $\det[A]<0$ to show $r_y$ is below the line. It would be redundant to type it all out.

---

I'm sure there is a much more elegant solution using the fact that we are using a right hand coordinate system and we are essentially checking the direction of the cross-product of a particular pair of vectors that relates to the question. But this is a very fundamental way to show that it works.

Answer 2

By doing row transformations we get $$\det \left(\begin{matrix}1 & p_x & p_y\\ 1 & q_x & q_y\\ 1 & r_x & r_y\end{matrix}\right)= \det \left(\begin{matrix}0 & p_x- r_r & p_y- r_y\\ 0 & q_x- r_x & q_y- r_y\\ 1 & r_x & r_y\end{matrix}\right)= \det \left(\begin{matrix}p-r\\ q-r \end{matrix}\right)$$

Now a $2\times 2$ determinant with row vectors $v$, $w$ is positive if and only if $v$ rotates towards $w$ in the positive ( counter-clockwise) orientation ( think of $(1,0)$ and $(0,1)$). But $p-r$ rotates positively onto $q-r$ if and only if $r$ is on the left side of the directed line from $p$ to $q$.

Note: left and right are chosen so that the point $(-1,0)$ is on the left of the line from $(0,0)$ to $(0,1)$.