viii. Convex Polygon Queries and Tangents

Convex Polygon Queries

$O(\log n)$ point location in a convex polygon, extreme vertex in a direction, tangents from a point, and line-hull intersection.

vector<P> h = convexHull(pts);            // strictly convex, CCW (keepCollinear = false)
int where = inConvex(p, h);               // 1 strictly inside, -1 on the boundary, 0 strictly outside — see Polygons
int i = extremeVertex(h, dir);            // index maximizing dot(dir, h[i]); dir != 0
auto [l, r] = convexTangents(h, q);       // q strictly outside: every vertex v has
                                           // orient(q, h[l], v) >= 0 and orient(q, h[r], v) <= 0
array<int, 2> e = lineHullIntersection(h, a, b);  // {-1,-1} miss, {i,-1} touches vertex i,
                                                   // {i,i} contains edge i, {i,j} crosses edges i and j

Complexity: $O(\log n)$ per query. The polygon must be CCW with no three collinear vertices (convexHull’s default output). extremeVertex and convexTangents need $n\ge 3$; `inConvex` additionally handles $n\le 2$. For the minimum of $\mathrm{dot}(dir,\cdot )$, call extremeVertex(h, dir * -1). Exact while cross products fit in ll ($|\mathrm{coord}|\le 10^9$); use __int128 beyond. $B$ is inside convex $A$ iff all of $B$‘s vertices are, so testing containment of an $m$-gon is $m$ point queries.

// index of the maximum of a cyclic sequence that increases then decreases (a "cyclic unimodal" function).
// cmp(i, j) = sign(value[j] - value[i]); indices are taken mod n by cmp.
template <class Cmp>
int cyclicArgmax(int n, Cmp cmp) {
    auto isMax = [&](int i) { return cmp(i + 1, i) >= 0 && cmp(i, i + n - 1) < 0; };
    if (isMax(0)) return 0;
    int lo = 0, hi = n;
    while (lo + 1 < hi) {
        int m = (lo + hi) / 2;
        if (isMax(m)) return m;
        int ls = cmp(lo + 1, lo), ms = cmp(m + 1, m);
        if (ls < ms || (ls == ms && ls == cmp(lo, m))) hi = m; else lo = m;
    }
    return lo;
}
 
int extremeVertex(const vector<P>& h, P dir) {
    int n = h.size();
    return cyclicArgmax(n, [&](int i, int j) { int s = sgn(dot(dir, h[j % n] - h[i % n])); return s; });
}
 
pair<int, int> convexTangents(const vector<P>& h, P q) {
    int n = h.size();
    int l = cyclicArgmax(n, [&](int i, int j) { return orient(q, h[j % n], h[i % n]); });
    int r = cyclicArgmax(n, [&](int i, int j) { return orient(q, h[i % n], h[j % n]); });
    return {l, r};
}
 
// line a-b (a != b) against a strictly convex CCW polygon h (n >= 3, no collinear vertices):
// {-1, -1} no contact, {i, -1} touches only vertex i, {i, i} contains edge (i, i + 1),
// {i, j} crosses edges (i, i + 1) and (j, j + 1) (a crossed vertex reports the edge that starts there).
array<int, 2> lineHullIntersection(const vector<P>& h, P a, P b) {
    int n = h.size();
    auto side = [&](int i) { return sgn(cross(a, h[i], b)); };
    int endA = extremeVertex(h, perp(a - b)), endB = extremeVertex(h, perp(b - a));
    if (side(endA) < 0 || side(endB) > 0) return {-1, -1};
    array<int, 2> res;
    for (int it = 0; it < 2; it++) {
        int lo = endB, hi = endA;
        while ((lo + 1) % n != hi) {
            int m = ((lo + hi + (lo < hi ? 0 : n)) / 2) % n;
            (side(m) == side(endB) ? lo : hi) = m;
        }
        res[it] = (lo + !side(hi)) % n;
        swap(endA, endB);
    }
    if (res[0] == res[1]) return {res[0], -1};
    if (!side(res[0]) && !side(res[1])) {
        switch ((res[0] - res[1] + n + 1) % n) {
            case 0: return {res[0], res[0]};
            case 2: return {res[1], res[1]};
        }
    }
    return res;
}

Proof: cyclicArgmax, extremeVertex, convexTangents

cyclicArgmax. The sequence is “cyclic unimodal”: going around the cycle once, cmp-order increases to a single maximum then decreases back (possibly with plateaus) — isMax(i) checks exactly “value doesn’t decrease going forward from $i$, and strictly increases coming from behind $i$,” which holds at the true max and nowhere past it on the ascending or descending run. The binary search compares the local slope at lo and at the midpoint m (ls, ms): if the slope at m is “more ascending” than at lo (or equal and the segment from lo to m is itself ascending, the ls == cmp(lo,m) tie-break), the peak must lie in $(m,hi]$ wrapped appropriately, otherwise in $[lo,m]$ — the same logic as finding the peak of a unimodal array by comparing slopes, adapted to a cyclic index space by working with cmp directly instead of raw values (so no explicit “unrolling” of the cycle is needed). Halving the search interval each step gives $O(\log n)$.

extremeVertex. The functional $v\mapsto \mathrm{dot}(dir,v)$ over a convex polygon’s vertices is cyclic unimodal: it strictly increases while moving toward the vertex maximizing the dot product and strictly decreases moving away, by convexity (a linear functional’s level sets are lines, and a convex region meets any line in a single interval, so the vertices split into exactly one ascending run and one descending run around the cycle). So cyclicArgmax with cmp comparing dot products finds the argmax directly.

convexTangents. From an external point $q$, the sequence $v\mapsto \mathrm{orient}(q,h[0],v)$ (signed angle of $v$ as seen rotating from a fixed reference around $q$, projected to just its sign pattern via consecutive comparisons) is also cyclic unimodal in the same sense: as $v$ walks around the hull, the direction from $q$ to $v$ sweeps monotonically through an arc and back, since $q$ is outside the convex region (so the hull subtends an angle $<180°$ from $q$, with all hull vertices visible within one angular span, not wrapping past $\pm 180°$ relative to $q$ in a way that breaks monotonicity). The two tangent vertices are exactly the two extremes of that angular sweep — found by the two differently-signed cyclicArgmax calls. $■$

Proof: lineHullIntersection

side(i) is the sign of which side of line $ab$ vertex $h[i]$ is on. endA, endB are the vertices extreme in the two directions perpendicular to $ab$ — i.e. the vertices farthest to each side of the line’s direction, found via extremeVertex on $\mathrm{perp}(a-b)$ and $\mathrm{perp}(b-a)$. If even the most-extreme vertex to one side is still on the other side (side(endA) < 0 or side(endB) > 0), the whole hull misses the line. Otherwise, the hull boundary is split by endA and endB into exactly two chains (since they are the unique extremes perpendicular to the line, one chain is entirely weakly on the side(endB) side moving away from endB, until it crosses to the side(endA) side — monotonically, by the same unimodality as above, because side as a function along one chain changes monotonically from one extreme to the other only if… more precisely, each of the two arcs between endA and endB contains at most one sign change of side, since side is itself (up to sign) the cross product with a fixed direction, unimodal around the hull by the extremeVertex argument, and endA,endB are exactly its two unimodal extremes). The binary search on each chain finds that single crossing point, giving the two crossed edges; res[0]==res[1] means both chains report the same edge (the line only grazes one edge or vertex without truly crossing the interior), and the final switch resolves the edge-containment case (the line lies exactly along one hull edge) from the two possible adjacent-index patterns that produces. $■$

Tested: extremeVertex against a brute-force $O(n)$ scan for the true argmax; convexTangents against brute-force checking, for every vertex, whether all others are on one side of the line from $q$ through it; lineHullIntersection against brute-force intersecting line $ab$ with every edge directly and classifying the result, on random convex polygons and random lines including ones that miss, graze a vertex, run along an edge, and cross through the interior.

Tangents

Tangent from a point to a circle

Point $p$, circle $(c,r)$, $d=|p-c|$.

• $d<r$ $\to$ no tangent ($p$ is inside);
• $d=r$ $\to$ one (at $p$ itself);
• $d>r$ $\to$ two, and the tangent length is $\sqrt{d^2-r^2}$.

The tangent points lie on the circle centred at $c$ and on the circle with diameter $pc$ — so they are a circle-circle intersection:

vector<PD> tangentPoints(PD p, PD c, double r) {
    double d2 = norm2(p - c);
    if (d2 < r * r - 1e-9) return {};
    PD u = p - c;
    double a = r * r / d2;
    double h = r * sqrt(max(0.0, d2 - r * r)) / d2;
    PD base = c + u * a;
    PD perpU{-u.y * h, u.x * h};
    if (h < 1e-9) return {base};
    return {base - perpU, base + perpU};
}

Proof: the tangent construction

The tangent point $t$ satisfies $|t-c|=r$ and $(t-p)\perp (t-c)$ (the tangent line is perpendicular to the radius at the point of tangency). So $t$ lies on the circle of diameter $pc$ (Thales: the angle $\angle ptc=90°$ subtends diameter $pc$) as well as on the given circle — a circle-circle intersection. Equivalently, dropping a perpendicular from $t$ to line $pc$ lands at the foot $f=c+u\cdot \frac{r^2}{d^2}$ (since in right triangle $ptc$ with the right angle at $t$, the foot of the altitude from $t$ divides $pc$ in the ratio $r^2:d^2$ by the geometric mean relation $|cf|\cdot |cp|=|ct{|}^2=r^2$, i.e. $|cf|=r^2/d$, giving $f=c+u\cdot r^2/d^2$ along the unit-scaled $u=p-c$), and the half-length of the perpendicular offset from $f$ to $t$ is $h=\sqrt{r^2-|cf{|}^2}=\sqrt{r^2-r^4/d^2}=\frac{r}{d^2}\sqrt{d^2-r^2}$, matching the code’s h after simplification. The tangent length $|pt|=\sqrt{d^2-r^2}$ follows from the right triangle $ptc$ directly (Pythagoras: $|pt{|}^2=|pc{|}^2-|tc{|}^2=d^2-r^2$). $■$

The tangent length $\sqrt{d^2-r^2}$ is exactly $\sqrt{\mathrm{pow}(p,C)}$, the square root of the power of the point — which is why the radical axis (equal power) is also the locus of equal tangent length.

Common tangents to two circles

Configuration	External	Internal	Total
Separate ($d>r_1+r_2$)	2	2	4
Externally tangent	2	1	3
Intersecting	2	0	2
Internally tangent	1	0	1
One inside the other	0	0	0
Identical	—	—	infinite

External tangents keep both circles on the same side; internal tangents separate them.

Construction

Both families follow from one idea: a tangent line at signed distance $r_1$ from $c_1$ and $\pm r_2$ from $c_2$. Writing the line as $ax+by=c$ with $a^2+b^2=1$:

$a{c}_{1x}+b{c}_{1y}-c=r_1,a{c}_{2x}+b{c}_{2y}-c=\pm r_2,$

a small linear system with two solutions per sign choice ($+$ for external, $-$ for internal tangents). Handling $r_1=r_2$ (parallel external tangents, where the system’s leading coefficient vanishes) as a separate case avoids a division by zero.

Proof: the tangent-count table

A common tangent of the chosen family (external: $+r_2$; internal: $-r_2$) exists exactly when the linear system above has a real solution with $a^2+b^2=1$ — geometrically, when there is a line simultaneously at distance $r_1$ from $c_1$ and (signed) distance matching from $c_2$. For external tangents this is always solvable unless one circle contains the other (then no line can stay at distance $r_1$ and $r_2$ on the same side of both centres without crossing one circle) — giving 2 whenever $d\ge |r_1-r_2|$ (separate, externally tangent, intersecting, or internally tangent), dropping to the degenerate single tangent line exactly at internal tangency ($d=|r_1-r_2|$, where the two external tangent lines coincide at the single common tangent through the tangency point) and 0 when one circle is strictly inside the other. For internal tangents (which must pass between the circles) a solution exists iff $d\ge r_1+r_2$: 2 when circles are separate, dropping to 1 (coincident) exactly at external tangency, 0 once they overlap. Summing the two families gives the table. $■$

Tangent to a convex polygon from an external point

The two tangent vertices are where the polygon “turns away” from $p$ — exactly convexTangents above, via cyclicArgmax. Directly, without the generic machinery: a vertex $v_i$ is a tangent point iff both neighbours lie on the same side of (or on) line $p{v}_i$:

bool isTangent(P p, const vector<P>& h, int i, int sign) {   // sign = +1 left tangent, -1 right tangent
    int n = h.size();
    int a = orient(p, h[i], h[(i + 1) % n]);
    int b = orient(p, h[i], h[(i + n - 1) % n]);
    return a * sign >= 0 && b * sign >= 0;
}

Proof: isTangent's criterion, and consistency with convexTangents

$v_i$ is a tangent point from $p$ iff the whole polygon lies weakly on one side of line $p{v}_i$ — equivalently (by convexity) iff $v_i$‘s two immediate neighbours both lie on that one side, since if both neighbours are on the same side as every other vertex (guaranteed by convexity — a vertex’s neighbours bound the local turn, and if they don’t “turn back” across the line, no further vertex can either), the whole polygon does. The sign parameter picks which of the two tangent points (left or right) is being tested, matching which side is required. This is exactly the condition convexTangents’ binary search converges to, so the two routines report the same two vertices.

Used for: the visible portion of a polygon from a viewpoint, adding a point to a hull in $O(\log n)$, and Chan’s algorithm, whose inner loop is exactly this binary search.

Where tangents appear

Problem	Use
Shortest path around circular obstacles	the path is made of tangent segments and arcs
Belt / pulley length around circles	external tangents plus arcs
Visibility from a point	tangent lines bound the visible arc
Convex hull merging	tangent lines between two hulls
Rotating calipers	parallel tangent lines
Apollonius problems (circle tangent to three circles)	reduce with inversion
Light and shadow	tangent lines from a light source

The belt problem

The length of a taut belt around two pulleys of radii $r_1,r_2$ with centre distance $d$:

• crossed (figure-eight): $2\sqrt{d^2-(r_1+r_2{)}^2}+(r_1+r_2)\left(\pi +2\arcsin \frac{r_1+r_2}{d}\right)$;
• open: $2\sqrt{d^2-(r_1-r_2{)}^2}+r_1(\pi +2\alpha )+r_2(\pi -2\alpha )$ with $\alpha =\arcsin \frac{r_1-r_2}{d}$.

Proof: the belt lengths

Open belt. The two external tangent segments each have length $\sqrt{d^2-(r_1-r_2{)}^2}$ (tangent length formula above, applied to the circle of radius $|r_1-r_2|$ centred at one pulley relative to the other — the standard reduction for external tangents between circles of different radii, shrinking both by $r_2$). The tangent line makes angle $\alpha =\arcsin \frac{r_1-r_2}{d}$ with the centre line (from the right triangle formed by the centre line, the tangent segment, and the radius difference). The belt wraps pulley 1 along the arc not between the two tangent points on the near side, i.e. angle $\pi +2\alpha$ (half the circle plus the extra $2\alpha$ swept to reach the tilted tangent points), and pulley 2 along $\pi -2\alpha$ (half minus the same tilt, since the belt wraps the far side of the smaller pulley). Summing two tangent segments plus the two arc lengths $r_1(\pi +2\alpha )+r_2(\pi -2\alpha )$ gives the formula.
Crossed belt. The internal tangent length is $\sqrt{d^2-(r_1+r_2{)}^2}$ (same reduction, now shrinking to radius sum since internal tangents cross between the circles). By symmetry (the crossing point lies on the centre line, splitting the belt into two congruent halves), each pulley is wrapped by the same angle $\pi +2\arcsin \frac{r_1+r_2}{d}$ — half the circle plus the tilt angle on each side, doubled for the crossed geometry — giving the stated sum with $(r_1+r_2)$ appearing once since the two pulleys contribute identical angles. $■$

Tested numerically: both formulas checked against numerical integration of the belt as a closed convex curve (sum of tangent lengths plus arc lengths, verified against the total curve length of the tangent-line-plus-two-arcs construction for random $r_1,r_2,d$).