Advanced Computational Geometry

Each linear inequality a·x + b·y ≤ c (or the left side of a directed line) defines a half-plane. The intersection of several half-planes is a convex region (possibly empty, unbounded, or a single point) bounded by a convex polygon. It is the dual notion to a convex hull of points.

Represent each half-plane by a directed line keeping the left side. Sort all lines by polar angle of their direction. Sweep with a double-ended queue: before pushing a new line, pop from the back any line whose intersection with the new front becomes invalid, and pop from the front symmetrically. Finally clean the back against the front. The deque holds the boundary lines in angular order.

Lines with the same direction are parallel; keep only the one whose half-plane is more restrictive (the inner one, farther toward the interior). During the angular sort, place same-angle lines adjacently and discard the looser duplicate so the deque never holds two parallel boundaries.

Compute the point p where the two existing lines meet, then check the sign of the cross product of the new line's direction with (p − point-on-new-line). If p lies on the wrong (outside) side of the new half-plane, the configuration is invalid and you pop a line from the deque. This is the core 'bad' test driving the deque pops.

Fix vertex p0. The polygon (CCW) fans into triangles p0,pi,pi+1. Binary search for the wedge: find i such that the query q lies between rays p0→pi and p0→pi+1 using cross-product signs. Then q is inside iff it is on the correct side of edge pi→pi+1. Total O(log n) per query after O(n) preprocessing.

A vertex v is a tangent point iff both polygon edges incident to v lie on the same side of line (point, v). Equivalently the polygon is locally on one side. Because the cross-product sign of (v − query) relative to neighbors is unimodal around the hull, you can binary-search each tangent (left/upper and right/lower) in O(log n).