"""Visualize that testing if a point p is to the left or right of a line
defined by two points q and r is nummerical unstable when using floats.

  q = (12, 12), r = (24, 24), p in [1/2, 1/2 + eps]^2 where eps = 2^-46

Attempt to reproduce slide 9 from
https://people.mpi-inf.mpg.de/~mehlhorn/ftp/SoCG09.pdf
"""

import matplotlib.pyplot as plt

N = 256

delta = 1 / 2**54
q = (12, 12)
r = (24, 24)

P = []  # points (i, j, det)

for i in range(N):
    for j in range(N):
        p = (0.5 + i * delta, 0.5 + j * delta)
        det = q[0]*r[1] + r[0]*p[1] + p[0]*q[1] - r[0]*q[1] - p[0]*r[1] - q[0]*p[1]
        P.append((i, j, det))

positive = [(i, j) for i, j, det in P if det > 0]
negative = [(i, j) for i, j, det in P if det < 0]
zero = [(i, j) for i, j, det in P if det == 0]

plt.subplot(facecolor='lightgrey', aspect='equal')
plt.xlabel('i')
plt.ylabel('j', rotation=0)

for points, color in [(positive, "b"), (negative, "r"), (zero, "y")]:
    X = [x for x, y in points]
    Y = [y for x, y in points]
    plt.plot(X, Y, color + ".")

plt.plot([-1, N], [-1, N], "k-")
plt.show()