#!/usr/bin/env python3
"""Jesko's Method vs. the ideal rasterized circle.

For every radius 1..R, run Jesko's Method in the first octant and compare each
row y with the ideal circle: the integer x closest to sqrt(r^2 - y^2)
(this is also what the midpoint circle algorithm draws).

Usage:  python3 jesko_experiment.py [R]      (default R = 1000)
Source: https://schwarzers.com/?page_id=209
"""
import math
import sys


def jesko(r, t1=None):
    """Pixels (x, y) of one octant, exactly as in the pseudocode."""
    t1 = r // 16 if t1 is None else t1
    x, y = r, 0
    pts = []
    while x >= y:
        pts.append((x, y))
        y += 1
        t1 += y
        t2 = t1 - x
        if t2 >= 0:
            t1 = t2
            x -= 1
    return pts


def ideal_x(r, y):
    """Integer x closest to sqrt(r^2 - y^2), computed exactly (no ties possible)."""
    s = r * r - y * y
    x = math.isqrt(s)
    if 4 * x * x + 4 * x + 1 < 4 * s:   # (x + 1/2)^2 < s  ->  round up
        x += 1
    return x


def compare(R, start):
    rows = outward = inward = 0
    max_step = 0
    exact = []
    buckets = [[0, 0, 0.0, 0.0] for _ in range(5)]   # rows, deviating, sum err, max |err|
    max_err = max_err_ideal = 0.0
    for r in range(1, R + 1):
        ok = True
        for x, y in jesko(r, start(r)):
            ix = ideal_x(r, y)
            d = x - ix
            rows += 1
            outward += d > 0
            inward += d < 0
            max_step = max(max_step, abs(d))
            ok &= d == 0
            err = math.hypot(x, y) - r                  # signed radial error
            b = buckets[min(4, int(math.degrees(math.atan2(y, x)) / 9))]
            b[0] += 1
            b[1] += d != 0
            b[2] += err
            b[3] = max(b[3], abs(err))
            max_err = max(max_err, abs(err))
            max_err_ideal = max(max_err_ideal, abs(math.hypot(ix, y) - r))
        if ok:
            exact.append(r)
    return dict(rows=rows, outward=outward, inward=inward, max_step=max_step,
                exact=exact, buckets=buckets, max_err=max_err, max_err_ideal=max_err_ideal)


R = int(sys.argv[1]) if len(sys.argv) > 1 else 1000

res = compare(R, lambda r: r // 16)
print(f"Jesko's Method, t1 = r/16, radii 1..{R}")
print(f"  rows: {res['rows']}, one pixel further out: {res['outward']} "
      f"({100 * res['outward'] / res['rows']:.1f} %), further in: {res['inward']}, "
      f"largest deviation: {res['max_step']} px")
print(f"  max radial error: {res['max_err']:.3f} px (ideal circle: {res['max_err_ideal']:.3f} px)")
print(f"  identical to the ideal circle for r = {res['exact']}")
print("  angle     rows deviating   mean radial error   max radial error")
for i, (n, dev, s, m) in enumerate(res['buckets']):
    print(f"  {9 * i:2d}-{9 * i + 9:2d} deg   {100 * dev / n:6.1f} %        {s / n:+.3f} px          {m:.3f} px")

print("\nOther start values for t1:")
for name, f in [("0", lambda r: 0), ("r>>4", lambda r: r >> 4), ("r>>3", lambda r: r >> 3),
                ("r>>2", lambda r: r >> 2), ("(r>>2)+(r>>4)", lambda r: (r >> 2) + (r >> 4))]:
    q = compare(R, f)
    print(f"  t1 = {name:13s} further out: {100 * q['outward'] / q['rows']:5.1f} %   "
          f"further in: {100 * q['inward'] / q['rows']:4.1f} %   max radial error: {q['max_err']:.3f} px")
