Is there something wrong with my simplified in-circle predicate?

Question

My larger goal is to write a program that performs 2D constrained Delaunay triangulations.

My smaller, current goal right now is to write a predicate function that determines if an edge is locally Delaunay.

Suppose the edge uv in the triangulation T is shared by the triangles uvp and uvq. We call uv locally Delaunay, or lD for short, if q lies on or outside the circle that passes through u, v, p. Source.

This link contains a written predicate function in an existing implementation of what I am trying to do (in a different language, as part of licensed code) that involves calculating some nasty looking determinants (bottom half of the image below, imagine that d is q and abc is upv).

My idea, however, is to use the inscribed angle theorem. In particular, see the image in the top right of the article linked. My algorithm goes like this

Given the method angle(abc) that returns the positive angle between a, b, and c.
This method determines if d is inside the circle defined by abc.
isInCircle(u, p, v, a):
    angle_upv = angle(upv) // this is the black theta on the wikipedia link
    angle_uqv_prime = pi - angle(uqv) // this is the green theta on the wikipedia link
    if angle_uqv_prime < angle_upv:
        // It is inside the circle.
        return True
    // It is not inside the circle.
    return False

My justification for why this would work is this: If I am dealing with triangles and not completely free-floating points, I know that p is always on the opposite side of edge uv as q (otherwise the triangle upv and uqv would intersect, and T would not be a valid triangulation). This means that for all points q, pi-uqv is == upv if and only if q is on the circle, < if it is inside the circle, and > if it is outside the circle.

My question is if this is in general true? If not why? If yes how would I go about formally proving this?

Answer 1

Your method is valid, and somewhat more clever than determinants (I can't speak for efficiency).

Let $U, P, V$ be points forming a triangle, and let $(UPV)$ be the circumcircle. Let $Q$ lie on the opposite side of $UV$ than $P$. There are three cases.

Case 1: $Q \in (UPV)$.

Then $\angle UQV = 180^\circ - \angle UPV$.

Case 2: $Q$ is in the interior of $(UPV)$.

Let $U' = \overline{UQ} \cap (UPV)$ and $V' = \overline{VQ} \cap(UPV)$. Clearly, $U' \neq V'$, so $\angle UPV' + \angle U'PV < \angle UPV$. By the Inscribed Angle Theorem,

$$\angle UQV = 180^\circ - (\angle U'UV + \angle V'VU) = 180^\circ - (\angle UPV' + \angle U'PV)$$

Therefore, $\angle UQV > 180^\circ - \angle UPV$.

Case 3: $Q$ is in the exterior of $(UPV)$.

Again, let $U' = \overline{UQ} \cap (UPV)$ and $V' = \overline{VQ} \cap(UPV)$. Clearly, $U' \neq V'$, so $\angle UPU' + \angle VPV' > \angle UPV$. By the Inscribed Angle Theorem,

$$\angle UQV = 180^\circ - (\angle UVU' + \angle VUV') = 180^\circ - (\angle UPU' + \angle VPV')$$

Therefore, $\angle UQV < 180^\circ - \angle UPV$.

Answer 2

Determining if a point is inside a circle accurately is critical for the implementation of a robust Delaunay triangulation algorithm. I wish you good luck using angles.

The beauty of Shewchuk's approach is that it is robust and fast - neither of these you will be able to beat with angles. You may want to read the literature on the subject which is very mature by now.

Why are you developing your own Delaunay tessellation in two-dimensions? There are libraries with very robust implementations that you could use - triangle.c by Shewchuk, CGAL, etc.