Convex hull of 8 points by monotone chain: sort by x, walk left to right keeping only left turns to get the lower hull, then walk right to left for the upper hull. A point that makes a right turn would be inside the rubber band, so it is popped.
The code
Plane Geometry, in Python
P = namedtuple("P", "x y")
def sub(a, b): return P(a.x - b.x, a.y - b.y) # the vector from b to a
def dot(u, v): return u.x * v.x + u.y * v.y # |u||v| cos(angle)
def cross(u, v): return u.x * v.y - u.y * v.x # |u||v| sin(angle), signed
def dist2(a, b): return dot(sub(a, b), sub(a, b)) # squared distance, no square root
def orient(a, b, c):
z = cross(sub(b, a), sub(c, a))
return (z > 0) - (z < 0) # +1 left turn, -1 right, 0 collinear
def intersect(a, b, c, d):
o1 = orient(a, b, c); o2 = orient(a, b, d)
o3 = orient(c, d, a); o4 = orient(c, d, b)
return o1 != o2 and o3 != o4 # each straddles the other's line
def area2(poly): return sum(cross(poly[i], poly[(i + 1) % len(poly)]) for i in range(len(poly)))
def hull(points):
ordered = sorted(points, key=lambda p: (p.x, p.y))
lower = []
for p in ordered:
while len(lower) >= 2 and orient(lower[-2], lower[-1], p) <= 0: lower.pop()
lower.append(p)
upper = []
for p in reversed(ordered):
while len(upper) >= 2 and orient(upper[-2], upper[-1], p) <= 0: upper.pop()
upper.append(p)
return lower[:-1] + upper[:-1]
def graham_scan(points):
pivot = min(points, key=lambda p: (p.y, p.x)) # lowest point, leftmost on a tie
rest = sorted([p for p in points if p != pivot], key=cmp_to_key( # by angle around the pivot
lambda a, b: -o if (o := orient(pivot, a, b)) != 0 else dist2(pivot, a) - dist2(pivot, b)))
stack = [pivot]
for p in rest:
while len(stack) >= 2 and orient(stack[-2], stack[-1], p) <= 0: stack.pop()
stack.append(p) # only left turns survive
return stack
def closest(ps): # ps sorted by x; returns dist2
if len(ps) <= 3: return min(dist2(ps[i], ps[j]) for i in range(len(ps)) for j in range(i + 1, len(ps)))
mid = len(ps) // 2; x = ps[mid].x
d = min(closest(ps[:mid]), closest(ps[mid:])) # best on either side
strip = sorted([p for p in ps if (p.x - x) * (p.x - x) < d], key=lambda p: p.y) # near the divider
for i in range(len(strip)):
for j in range(i + 1, len(strip)):
if (strip[j].y - strip[i].y) ** 2 >= d: break # too far up: stop
d = min(d, dist2(strip[i], strip[j]))
return d
def any_intersect(segs): # Shamos-Hoey sweep
events = sorted([e for s in segs for e in (Event(s.left.x, s, True), Event(s.right.x, s, False))], key=lambda e: e.x)
active = SortedSet(key=lambda s: s.y_at(sweep_x)) # ordered by height at the sweep
for e in events:
sweep_x = e.x
if e.insert:
active.add(e.seg) # check only the new neighbours
if any(intersect(n, e.seg) for n in (active.lower(e.seg), active.higher(e.seg)) if n is not None): return True
else:
above = active.higher(e.seg); below = active.lower(e.seg)
active.remove(e.seg) # its neighbours meet: check them
if above is not None and below is not None and intersect(above, below): return True
return False
Plane Geometry, in JavaScript
const P = (x, y) => ({ x, y });
const sub = (a, b) => P(a.x - b.x, a.y - b.y); // the vector from b to a
const dot = (u, v) => u.x * v.x + u.y * v.y; // |u||v| cos(angle)
const cross = (u, v) => u.x * v.y - u.y * v.x; // |u||v| sin(angle), signed
const dist2 = (a, b) => dot(sub(a, b), sub(a, b)); // squared distance, no square root
const orient = (a, b, c) => Math.sign(cross(sub(b, a), sub(c, a))); // +1 left turn, -1 right, 0 collinear
function intersect(a, b, c, d) {
const o1 = orient(a, b, c); const o2 = orient(a, b, d);
const o3 = orient(c, d, a); const o4 = orient(c, d, b);
return o1 !== o2 && o3 !== o4; // each straddles the other's line
}
const area2 = (poly) => poly.reduce((sum, _, i) => sum + cross(poly[i], poly[(i + 1) % poly.length]), 0);
function hull(points) {
const ordered = [...points].sort((a, b) => a.x - b.x || a.y - b.y);
const lower = [];
for (const p of ordered) {
while (lower.length >= 2 && orient(lower[lower.length - 2], lower[lower.length - 1], p) <= 0) lower.pop();
lower.push(p);
}
const upper = [];
for (const p of [...ordered].reverse()) {
while (upper.length >= 2 && orient(upper[upper.length - 2], upper[upper.length - 1], p) <= 0) upper.pop();
upper.push(p);
}
return [...lower.slice(0, -1), ...upper.slice(0, -1)];
}
function grahamScan(points) {
const pivot = points.reduce((best, p) => ((p.y - best.y || p.x - best.x) < 0 ? p : best)); // lowest point, leftmost on a tie
const rest = points.filter((p) => p !== pivot).sort((a, b) => { // by angle around the pivot
const o = orient(pivot, a, b); return o !== 0 ? -o : dist2(pivot, a) - dist2(pivot, b);
});
const stack = [pivot];
for (const p of rest) {
while (stack.length >= 2 && orient(stack[stack.length - 2], stack[stack.length - 1], p) <= 0) stack.pop();
stack.push(p); // only left turns survive
}
return stack;
}
function closest(ps) { // ps sorted by x; returns dist2
if (ps.length <= 3) return Math.min(...ps.flatMap((_, i) => ps.slice(i + 1).map((q) => dist2(ps[i], q))));
const mid = Math.floor(ps.length / 2); const x = ps[mid].x;
let d = Math.min(closest(ps.slice(0, mid)), closest(ps.slice(mid))); // best on either side
const strip = ps.filter((p) => (p.x - x) * (p.x - x) < d).sort((a, b) => a.y - b.y); // near the divider
for (let i = 0; i < strip.length; i++) {
for (let j = i + 1; j < strip.length; j++) {
if ((strip[j].y - strip[i].y) ** 2 >= d) break; // too far up: stop
d = Math.min(d, dist2(strip[i], strip[j]));
}
}
return d;
}
function anyIntersect(segs) { // Shamos-Hoey sweep
const events = segs.flatMap((s) => [new Event(s.left.x, s, true), new Event(s.right.x, s, false)]).sort((a, b) => a.x - b.x);
const active = new SortedSet((s) => s.yAt(sweepX)); // ordered by height at the sweep
for (const e of events) {
sweepX = e.x;
if (e.insert) {
active.add(e.seg); // check only the new neighbours
if ([active.lower(e.seg), active.higher(e.seg)].some((n) => n != null && intersect(n, e.seg))) return true;
} else {
const above = active.higher(e.seg); const below = active.lower(e.seg);
active.remove(e.seg); // its neighbours meet: check them
if (above != null && below != null && intersect(above, below)) return true;
}
}
return false;
}
Plane Geometry, in Kotlin
data class P(val x: Int, val y: Int)
fun sub(a: P, b: P) = P(a.x - b.x, a.y - b.y) // the vector from b to a
fun dot(u: P, v: P) = u.x * v.x + u.y * v.y // |u||v| cos(angle)
fun cross(u: P, v: P) = u.x * v.y - u.y * v.x // |u||v| sin(angle), signed
fun dist2(a: P, b: P) = dot(sub(a, b), sub(a, b)) // squared distance, no square root
fun orient(a: P, b: P, c: P) = cross(sub(b, a), sub(c, a)).sign // +1 left turn, -1 right, 0 collinear
fun intersect(a: P, b: P, c: P, d: P): Boolean {
val o1 = orient(a, b, c); val o2 = orient(a, b, d)
val o3 = orient(c, d, a); val o4 = orient(c, d, b)
return o1 != o2 && o3 != o4 // each straddles the other's line
}
fun area2(poly: List<P>) = poly.indices.sumOf { i -> cross(poly[i], poly[(i + 1) % poly.size]) }
fun hull(points: List<P>): List<P> {
val sorted = points.sortedWith(compareBy({ it.x }, { it.y }))
val lower = mutableListOf<P>()
for (p in sorted) {
while (lower.size >= 2 && orient(lower[lower.size - 2], lower.last(), p) <= 0) lower.removeLast()
lower += p
}
val upper = mutableListOf<P>()
for (p in sorted.asReversed()) {
while (upper.size >= 2 && orient(upper[upper.size - 2], upper.last(), p) <= 0) upper.removeLast()
upper += p
}
return lower.dropLast(1) + upper.dropLast(1)
}
fun grahamScan(points: List<P>): List<P> {
val pivot = points.minWith(compareBy({ it.y }, { it.x })) // lowest point, leftmost on a tie
val rest = (points - pivot).sortedWith { a, b -> // by angle around the pivot
val o = orient(pivot, a, b); if (o != 0) -o else dist2(pivot, a) - dist2(pivot, b) }
val stack = mutableListOf(pivot)
for (p in rest) {
while (stack.size >= 2 && orient(stack[stack.size - 2], stack.last(), p) <= 0) stack.removeLast()
stack += p // only left turns survive
}
return stack
}
fun closest(ps: List<P>): Int { // ps sorted by x; returns dist2
if (ps.size <= 3) return ps.indices.flatMap { i -> ps.indices.drop(i + 1).map { dist2(ps[i], ps[it]) } }.min()
val mid = ps.size / 2; val x = ps[mid].x
var d = min(closest(ps.subList(0, mid)), closest(ps.subList(mid, ps.size))) // best on either side
val strip = ps.filter { (it.x - x) * (it.x - x) < d }.sortedBy { it.y } // near the divider
for (i in strip.indices) for (j in i + 1 until strip.size) {
if ((strip[j].y - strip[i].y).let { it * it } >= d) break // too far up: stop
d = min(d, dist2(strip[i], strip[j]))
}
return d
}
fun anyIntersect(segs: List<Seg>): Boolean { // Shamos-Hoey sweep
val events = segs.flatMap { listOf(Event(it.left.x, it, true), Event(it.right.x, it, false)) }.sortedBy { it.x }
val active = sortedSetOf(compareBy<Seg> { it.yAt(sweepX) }) // ordered by height at the sweep
for (e in events) {
sweepX = e.x
if (e.insert) {
active += e.seg // check only the new neighbours
if (listOfNotNull(active.lower(e.seg), active.higher(e.seg)).any { intersect(it, e.seg) }) return true
} else {
val above = active.higher(e.seg); val below = active.lower(e.seg)
active -= e.seg // its neighbours meet: check them
if (above != null && below != null && intersect(above, below)) return true
}
}
return false
}