The Mouth Algorithm

A Dual of Ear Clipping for Point-in-Polygon Testing

D. CANGIALOSI · 2025 · COMPUTATIONAL GEOMETRY

ABSTRACT

We present pip_mouth, a novel algorithm for point-in-polygon testing on simple polygons. The algorithm is the geometric dual of ear clipping: where ear clipping iteratively removes ears — convex vertices whose triangles lie entirely inside the polygon — pip_mouth iteratively removes mouths — reflex vertices whose triangles lie entirely outside.

A point is tested against each mouth triangle as it is removed. Since mouth triangles are guaranteed external, a point inside such a triangle is immediately classified as outside the polygon. After all mouths are consumed, the reduced polygon is convex and a direct convex test is applied.

Correctness rests on the Mouth Lemma: every simple polygon with at least one reflex vertex has at least two valid mouths. We prove this by duality — the reversed polygon R is also simple, its ears correspond exactly to the mouths of P, and Meisters' Theorem (1975) guarantees R has at least two ears.

STATUS

CORRECTNESS
Proved (Meisters duality) + 30k empirical tests
COMPLEXITY
O(n³) per query · O(n) space
NOVELTY
Mouth Lemma and pip_mouth not found in literature
PRACTICAL VALUE
Limited — ray casting O(n) dominates

CONTRIBUTIONS

1. The concept of a mouth as the geometric dual of an ear.

2. The Mouth Lemma: every simple polygon with ≥1 reflex vertex has ≥2 mouths.

3. A proof of the Mouth Lemma via the reversed polygon and Meisters' Theorem.

4. The pip_mouth algorithm with formal correctness argument.

5. Identification that chord_ok is necessary for mouths but redundant for ears — an asymmetry not previously noted explicitly.

OPEN QUESTIONS

— Degenerate cases: collinear vertices, vertices on polygon edges.

— Can O(n²) be achieved by maintaining a mouth list dynamically?

— Does an analogous "mouth-based triangulation" exist with useful properties?

Proofs

MOUTH LEMMA · TRIANGLE EXTERNALITY · ALGORITHM CORRECTNESS

DEFINITIONS

Let P be a simple polygon with vertices listed in CCW order. The signed area (shoelace formula) is positive for CCW polygons. A vertex V with neighbors A (prev) and B (next) is reflex if the interior angle exceeds 180°, equivalently if cross(A, V, B) < 0 for CCW orientation.

DEFINITION — MOUTH

A vertex V of a simple polygon P is a mouth if: (1) V is reflex; (2) the chord AB does not properly intersect any non-adjacent edge of P; (3) no vertex of P other than A, V, B lies inside or on the triangle △AVB.

LEMMA 1 — TRIANGLE EXTERNALITY

THEOREM

If V is a mouth of simple polygon P, then the triangle △AVB lies entirely outside P (its interior does not intersect the interior of P).

PROOF
1
Since V is reflex, the interior of P locally at V lies on the opposite side of the triangle from V — the triangle is on the exterior side of the reflex angle.
2
Condition (2) ensures no edge of P crosses into △AVB through the chord AB or any other side of the triangle. The boundary of P does not pierce △AVB.
3
Condition (3) ensures no vertex of P lies inside △AVB. Combined with (2), no part of P's boundary enters the triangle. Since P is simple, its interior cannot reach △AVB without crossing its boundary.
4
Therefore △AVB ∩ interior(P) = ∅. △AVB lies entirely outside P.
□

LEMMA 2 — MOUTH LEMMA

THEOREM (MOUTH LEMMA)

Every simple polygon P with n ≥ 3 vertices and at least one reflex vertex has at least two mouths.

PROOF — BY DUALITY WITH MEISTERS (1975)
1
Construct R: let R be the polygon with the same vertices as P but in reversed order. R has opposite orientation; normalize to CCW by reversing once more (equivalently, R traverses P's vertices in CW order, which as a CCW polygon is the reversal). R is simple because P is simple — the same edges exist, only traversal direction changes.
2
Orientation duality: reversing traversal direction negates all cross products. A vertex V with cross(A,V,B) < 0 in P (reflex) has cross(B,V,A) > 0 in R (convex). So: reflex vertices of P = convex vertices of R.
3
Ears of R are mouths of P: an ear of R is a convex vertex of R whose triangle contains no other vertices of R (and by the ear property, chord_ok holds automatically for ears of simple polygons). This vertex is reflex in P, its triangle is the same △AVB, contains no other vertices, and chord_ok holds. Therefore it satisfies all three conditions of a mouth in P.
4
Apply Meisters' Theorem: every simple polygon with n ≥ 3 has at least two ears. R is simple with n ≥ 3. Therefore R has ≥ 2 ears. Each ear of R corresponds to a mouth of P. P has ≥ 2 mouths.
□

THEOREM — CORRECTNESS OF pip_mouth

THEOREM

pip_mouth correctly classifies a query point p as inside or outside any simple polygon P.

PROOF — BY INDUCTION ON n = |P|
B
Base (n = 3): P is a triangle. No reflex vertices exist (simple triangle). in_convex_ccw correctly classifies p. ✓
I
Inductive step: assume the algorithm is correct for all simple polygons with < n vertices. Let P have n vertices.
a
No reflex vertex: P is convex. in_convex_ccw is correct for convex polygons. ✓
b
Has reflex vertex: by the Mouth Lemma, a mouth M with neighbors A, B exists. By Lemma 1, △AMB lies entirely outside P.
c
If p ∈ △AMB: since △AMB is entirely outside P, p is outside P. Returning false is correct. ✓
d
If p ∉ △AMB: remove M, forming P' = P \ {M}. P' is simple (chord AB is valid by mouth conditions). P' has n-1 vertices. The interior of P' equals interior(P) ∪ △AMB minus their shared boundary. Since p ∉ △AMB, p ∈ interior(P) iff p ∈ interior(P'). By the inductive hypothesis, the algorithm correctly classifies p for P'. ✓
□

ASYMMETRY: chord_ok FOR MOUTHS VS EARS

EAR (convex vertex)
Triangle is inside P.
If an edge CD crosses chord AB, at least one of C,D is inside the triangle → excluded by condition (3).
∴ chord_ok is implied by condition (3).
MOUTH (reflex vertex)
Triangle is outside P.
An edge CD can cross chord AB with both C and D outside the triangle — neither is caught by condition (3).
∴ chord_ok is necessary as condition (2).

Algorithm

PSEUDOCODE · IMPLEMENTATION · COMPLEXITY

PSEUDOCODE

// pip_mouth: point-in-polygon via mouth removal
// Input:  p — query point
//         P — simple polygon, vertices in any order
// Output: true if p is strictly inside P

function pip_mouth(p, P):
  P ← ensure_ccw(P)           // normalize via shoelace area

  while |P| ≥ 3:
    M ← first_mouth(P)         // find first valid mouth

    if M = null:               // no reflex vertices remain
      return in_convex(p, P)  // P is now convex

    A, B ← neighbors(M, P)

    if in_triangle(p, A, M, B):
      return false              // p is in external triangle → outside

    P ← P \ {M}                // remove mouth, polygon stays simple

  return false
// is_mouth: three necessary and sufficient conditions
function is_mouth(V, P):
  A ← prev(V, P),  B ← next(V, P)

  // 1. V is reflex (CCW: interior cross product negative)
  if cross(A, V, B) ≥ 0: return false

  // 2. Chord AB does not cross any non-adjacent edge of P
  //    (NOT implied by condition 3 for mouths)
  if ¬chord_ok(V, P): return false

  // 3. No other vertex of P lies inside △AVB
  for each vertex Q ∈ P \ {A, V, B}:
    if in_triangle(Q, A, V, B): return false

  return true

COMPLEXITY

first_mouth
O(n²) per call
(n vertices × O(n) is_mouth)
ITERATIONS
At most n − 3
(one vertex removed per step)
TOTAL
O(n³) per query
O(n) space
VS RAY CASTING
O(n) per query
Practical choice for large n

JAVASCRIPT IMPLEMENTATION

// cross product: (A-O)×(B-O)
function cross(O, A, B) {
  return (A.x-O.x)*(B.y-O.y) - (A.y-O.y)*(B.x-O.x);
}

// ensure CCW orientation via shoelace area
function ensure_ccw(poly) {
  let a = 0;
  for (let i=0; i<poly.length; i++) {
    const j = (i+1) % poly.length;
    a += poly[i].x*poly[j].y - poly[j].x*poly[i].y;
  }
  return a > 0 ? [...poly] : [...poly].reverse();
}

function is_mouth(vi, poly) {
  const n=poly.length, I=i=>((i%n)+n)%n;
  const A=poly[I(vi-1)], V=poly[vi], B=poly[I(vi+1)];
  if (cross(A,V,B) >= 0) return false;     // not reflex
  if (!chord_ok(vi, poly)) return false;   // chord crosses edge
  for (let j=0; j<n; j++) {
    if (j===I(vi-1)||j===vi||j===I(vi+1)) continue;
    if (in_tri(poly[j],A,V,B)) return false; // vertex inside △
  }
  return true;
}

function pip_mouth(p, poly) {
  poly = ensure_ccw([...poly]);
  while (poly.length >= 3) {
    const n=poly.length, I=i=>((i%n)+n)%n;
    let mi = -1;
    for (let i=0; i<n; i++) if (is_mouth(i,poly)){mi=i;break;}
    if (mi === -1) return in_convex_ccw(p, poly);
    if (in_tri(p, poly[I(mi-1)], poly[mi], poly[I(mi+1)]))
      return false;
    poly.splice(mi, 1);
  }
  return false;
}

Interactive Demo

Click the canvas to test any point. Green = inside, grey = outside.

SCENARIO
RESULTS
Ray Cast
O(n) · ground truth
–
pip_mouth
O(n³) · this algorithm
–
⚠ DISAGREE — bug found!
✓ Agree
MOUTHS REMOVED
–
LEGEND
◉ P_i — mouth vertex (removed)
● P_i — reflex, not a mouth
● P_i — convex vertex
● test point — inside polygon
● test point — outside polygon
M1, M2… — mouth triangles in order