### Rational Computational Geometry in Python

In the previous article, we looked at how a standard technique for determining the collinearity of points, based on computing the sign of the area of the triangle formed by two points on the line and a third query point. We discovered, that when used with Python's float type [1] the routine was unreliable in a region close to the line. This shortcoming has nothing to do with Python specifically and everything to do with the finite precision of the float number type. This time, we'll examine the behaviour of the algorithm more systematically using the following program:

def sign(x):
"""Determine the sign of x.

Returns:
-1 if x is negative, +1 if x is positive or 0 if x is zero.
"""
return (x > 0) - (x < 0)

def orientation(p, q, r):
"""Determine the orientation of three points in the plane.

Args:
p, q, r: Two-tuples representing coordinate pairs of three points.

Returns:
-1 if p, q, r is a turn to the right, +1 if p, q, r is a turn to the
left, otherwise 0 if p, q, and r are collinear.
"""
d = (q&#91;0&#93; - p&#91;0&#93;) * (r&#91;1&#93; - p&#91;1&#93;) - (q&#91;1&#93; - p&#91;1&#93;) * (r&#91;0&#93; - p&#91;0&#93;)
return sign(d)

def main():
"""
Test whether points immediately above and below the point (0.5, 0.5)
lie above, on, or below the line through (12.0, 12.0) and (24.0, 24.0).
"""
px = 0.5

pys = 0.49999999999999,
0.49999999999999006,
0.4999999999999901,
0.4999999999999902,
0.49999999999999023,
0.4999999999999903,
0.49999999999999034,
0.4999999999999904,
0.49999999999999045,
0.4999999999999905,
0.49999999999999056,
0.4999999999999906,
0.4999999999999907,
0.49999999999999073,
0.4999999999999908,
0.49999999999999084,
0.4999999999999909,
0.49999999999999095,
0.499999999999991,
0.49999999999999106,
0.4999999999999911,
0.4999999999999912,
0.49999999999999123,
0.4999999999999913,
0.49999999999999134,
0.4999999999999914,
0.49999999999999145,
0.4999999999999915,
0.49999999999999156,
0.4999999999999916,
0.4999999999999917,
0.49999999999999173,
0.4999999999999918,
0.49999999999999184,
0.4999999999999919,
0.49999999999999195,
0.499999999999992,
0.49999999999999206,
0.4999999999999921,
0.4999999999999922,
0.49999999999999223,
0.4999999999999923,
0.49999999999999234,
0.4999999999999924,
0.49999999999999245,
0.4999999999999925,
0.49999999999999256,
0.4999999999999926,
0.4999999999999927,
0.49999999999999273,
0.4999999999999928,
0.49999999999999284,
0.4999999999999929,
0.49999999999999295,
0.499999999999993,
0.49999999999999306,
0.4999999999999931,
0.49999999999999317,
0.4999999999999932,
0.4999999999999933,
0.49999999999999334,
0.4999999999999934,
0.49999999999999345,
0.4999999999999935,
0.49999999999999356,
0.4999999999999936,
0.49999999999999367,
0.4999999999999937,
0.4999999999999938,
0.49999999999999384,
0.4999999999999939,
0.49999999999999395,
0.499999999999994,
0.49999999999999406,
0.4999999999999941,
0.49999999999999417,
0.4999999999999942,
0.4999999999999943,
0.49999999999999434,
0.4999999999999944,
0.49999999999999445,
0.4999999999999945,
0.49999999999999456,
0.4999999999999946,
0.49999999999999467,
0.4999999999999947,
0.4999999999999948,
0.49999999999999484,
0.4999999999999949,
0.49999999999999495,
0.499999999999995,
0.49999999999999506,
0.4999999999999951,
0.49999999999999517,
0.4999999999999952,
0.4999999999999953,
0.49999999999999534,
0.4999999999999954,
0.49999999999999545,
0.4999999999999955,
0.49999999999999556,
0.4999999999999956,
0.49999999999999567,
0.4999999999999957,
0.4999999999999958,
0.49999999999999584,
0.4999999999999959,
0.49999999999999595,
0.499999999999996,
0.49999999999999606,
0.4999999999999961,
0.49999999999999617,
0.4999999999999962,
0.4999999999999963,
0.49999999999999634,
0.4999999999999964,
0.49999999999999645,
0.4999999999999965,
0.49999999999999656,
0.4999999999999966,
0.49999999999999667,
0.4999999999999967,
0.4999999999999968,
0.49999999999999684,
0.4999999999999969,
0.49999999999999695,
0.499999999999997,
0.49999999999999706,
0.4999999999999971,
0.49999999999999717,
0.4999999999999972,
0.4999999999999973,
0.49999999999999734,
0.4999999999999974,
0.49999999999999745,
0.4999999999999975,
0.49999999999999756,
0.4999999999999976,
0.49999999999999767,
0.4999999999999977,
0.4999999999999978,
0.49999999999999784,
0.4999999999999979,
0.49999999999999795,
0.499999999999998,
0.49999999999999806,
0.4999999999999981,
0.49999999999999817,
0.4999999999999982,
0.4999999999999983,
0.49999999999999833,
0.4999999999999984,
0.49999999999999845,
0.4999999999999985,
0.49999999999999856,
0.4999999999999986,
0.49999999999999867,
0.4999999999999987,
0.4999999999999988,
0.49999999999999883,
0.4999999999999989,
0.49999999999999895,
0.499999999999999,
0.49999999999999906,
0.4999999999999991,
0.49999999999999917,
0.4999999999999992,
0.4999999999999993,
0.49999999999999933,
0.4999999999999994,
0.49999999999999944,
0.4999999999999995,
0.49999999999999956,
0.4999999999999996,
0.49999999999999967,
0.4999999999999997,
0.4999999999999998,
0.49999999999999983,
0.4999999999999999,
0.49999999999999994,  # The previous representable float < 0.5
0.5,
0.5000000000000001,   # The next representable float > 0.5
0.5000000000000002,
0.5000000000000003,
0.5000000000000004,
0.5000000000000006,
0.5000000000000007,
0.5000000000000008,
0.5000000000000009,
0.500000000000001,
0.5000000000000011,
0.5000000000000012,
0.5000000000000013,
0.5000000000000014,
0.5000000000000016,
0.5000000000000017,
0.5000000000000018,
0.5000000000000019,
0.500000000000002,
0.5000000000000021,
0.5000000000000022,
0.5000000000000023,
0.5000000000000024,
0.5000000000000026,
0.5000000000000027,
0.5000000000000028,
0.5000000000000029,
0.500000000000003,
0.5000000000000031,
0.5000000000000032,
0.5000000000000033,
0.5000000000000034,
0.5000000000000036,
0.5000000000000037,
0.5000000000000038,
0.5000000000000039,
0.500000000000004,
0.5000000000000041,
0.5000000000000042,
0.5000000000000043,
0.5000000000000044,
0.5000000000000046,
0.5000000000000047,
0.5000000000000048,
0.5000000000000049,
0.500000000000005,
0.5000000000000051,
0.5000000000000052,
0.5000000000000053,
0.5000000000000054,
0.5000000000000056,
0.5000000000000057,
0.5000000000000058,
0.5000000000000059,
0.500000000000006,
0.5000000000000061,
0.5000000000000062,
0.5000000000000063,
0.5000000000000064,
0.5000000000000066,
0.5000000000000067,
0.5000000000000068,
0.5000000000000069,
0.500000000000007,
0.5000000000000071,
0.5000000000000072,
0.5000000000000073,
0.5000000000000074,
0.5000000000000075,
0.5000000000000077,
0.5000000000000078,
0.5000000000000079,
0.500000000000008,
0.5000000000000081,
0.5000000000000082,
0.5000000000000083,
0.5000000000000084,
0.5000000000000085,
0.5000000000000087,
0.5000000000000088,
0.5000000000000089,
0.500000000000009,
0.5000000000000091,
0.5000000000000092,
0.5000000000000093,
0.5000000000000094,
0.5000000000000095,
0.5000000000000097,
0.5000000000000098,
0.5000000000000099,
0.50000000000001]

q = (12.0, 12.0)
r = (24.0, 24.0)

for py in pys:
p = (px, py)
o = orientation(p, q, r)
print("orientation(({p[0]:>3}, {p[1]:<19}) q, r) -> {o:>2}".format(
p=p, o=o))

if __name__  == '__main__':
main()


The program includes definitions of our sign() and orientation() functions, together with a main() function which runs the test. The main function includes a list of the 271 nearest representable $$y$$-coordinate values to 0.5. We haven't included the code to generate these values successive float values because it's somewhat besides the point; we're referenced the necessary technique in the previous article.

The program iterates over these py values and performs the orientation test each time, printing the result. The complex format string is used to get readable output which lines up in columns. When we look at that output we see an intricate pattern of results emerge, which isn't even symmetrical around the central 0.5 value:

orientation((0.5, 0.50000000000001   ) q, r) ->  1
orientation((0.5, 0.5000000000000099 ) q, r) ->  1
orientation((0.5, 0.5000000000000098 ) q, r) ->  1
orientation((0.5, 0.5000000000000097 ) q, r) ->  1
orientation((0.5, 0.5000000000000095 ) q, r) ->  1
orientation((0.5, 0.5000000000000094 ) q, r) ->  1
orientation((0.5, 0.5000000000000093 ) q, r) ->  1
orientation((0.5, 0.5000000000000092 ) q, r) ->  1
orientation((0.5, 0.5000000000000091 ) q, r) ->  1
orientation((0.5, 0.500000000000009  ) q, r) ->  1
orientation((0.5, 0.5000000000000089 ) q, r) ->  1
orientation((0.5, 0.5000000000000088 ) q, r) ->  1
orientation((0.5, 0.5000000000000087 ) q, r) ->  1
orientation((0.5, 0.5000000000000085 ) q, r) ->  1
orientation((0.5, 0.5000000000000084 ) q, r) ->  1
orientation((0.5, 0.5000000000000083 ) q, r) ->  1
orientation((0.5, 0.5000000000000082 ) q, r) ->  1
orientation((0.5, 0.5000000000000081 ) q, r) ->  1
orientation((0.5, 0.500000000000008  ) q, r) ->  1
orientation((0.5, 0.5000000000000079 ) q, r) ->  1
orientation((0.5, 0.5000000000000078 ) q, r) ->  1
orientation((0.5, 0.5000000000000077 ) q, r) ->  1
orientation((0.5, 0.5000000000000075 ) q, r) ->  1
orientation((0.5, 0.5000000000000074 ) q, r) ->  1
orientation((0.5, 0.5000000000000073 ) q, r) ->  1
orientation((0.5, 0.5000000000000072 ) q, r) ->  1
orientation((0.5, 0.5000000000000071 ) q, r) ->  1
orientation((0.5, 0.500000000000007  ) q, r) ->  1
orientation((0.5, 0.5000000000000069 ) q, r) ->  1
orientation((0.5, 0.5000000000000068 ) q, r) ->  1
orientation((0.5, 0.5000000000000067 ) q, r) ->  1
orientation((0.5, 0.5000000000000066 ) q, r) ->  1
orientation((0.5, 0.5000000000000064 ) q, r) ->  1
orientation((0.5, 0.5000000000000063 ) q, r) ->  1
orientation((0.5, 0.5000000000000062 ) q, r) ->  1
orientation((0.5, 0.5000000000000061 ) q, r) ->  1
orientation((0.5, 0.500000000000006  ) q, r) ->  1
orientation((0.5, 0.5000000000000059 ) q, r) ->  1
orientation((0.5, 0.5000000000000058 ) q, r) ->  1
orientation((0.5, 0.5000000000000057 ) q, r) ->  1
orientation((0.5, 0.5000000000000056 ) q, r) ->  1
orientation((0.5, 0.5000000000000054 ) q, r) ->  1
orientation((0.5, 0.5000000000000053 ) q, r) ->  1
orientation((0.5, 0.5000000000000052 ) q, r) ->  1
orientation((0.5, 0.5000000000000051 ) q, r) ->  1
orientation((0.5, 0.500000000000005  ) q, r) ->  1
orientation((0.5, 0.5000000000000049 ) q, r) ->  1
orientation((0.5, 0.5000000000000048 ) q, r) ->  1
orientation((0.5, 0.5000000000000047 ) q, r) ->  1
orientation((0.5, 0.5000000000000046 ) q, r) ->  1
orientation((0.5, 0.5000000000000044 ) q, r) ->  0
orientation((0.5, 0.5000000000000043 ) q, r) ->  0
orientation((0.5, 0.5000000000000042 ) q, r) ->  0
orientation((0.5, 0.5000000000000041 ) q, r) ->  0
orientation((0.5, 0.500000000000004  ) q, r) ->  0
orientation((0.5, 0.5000000000000039 ) q, r) ->  0
orientation((0.5, 0.5000000000000038 ) q, r) ->  0
orientation((0.5, 0.5000000000000037 ) q, r) ->  0
orientation((0.5, 0.5000000000000036 ) q, r) ->  0
orientation((0.5, 0.5000000000000034 ) q, r) ->  0
orientation((0.5, 0.5000000000000033 ) q, r) ->  0
orientation((0.5, 0.5000000000000032 ) q, r) ->  0
orientation((0.5, 0.5000000000000031 ) q, r) ->  0
orientation((0.5, 0.500000000000003  ) q, r) ->  0
orientation((0.5, 0.5000000000000029 ) q, r) ->  0
orientation((0.5, 0.5000000000000028 ) q, r) ->  0
orientation((0.5, 0.5000000000000027 ) q, r) ->  0
orientation((0.5, 0.5000000000000026 ) q, r) ->  0
orientation((0.5, 0.5000000000000024 ) q, r) ->  0
orientation((0.5, 0.5000000000000023 ) q, r) ->  0
orientation((0.5, 0.5000000000000022 ) q, r) ->  0
orientation((0.5, 0.5000000000000021 ) q, r) ->  0
orientation((0.5, 0.500000000000002  ) q, r) ->  0
orientation((0.5, 0.5000000000000019 ) q, r) ->  0
orientation((0.5, 0.5000000000000018 ) q, r) ->  1
orientation((0.5, 0.5000000000000017 ) q, r) ->  1
orientation((0.5, 0.5000000000000016 ) q, r) ->  1
orientation((0.5, 0.5000000000000014 ) q, r) ->  1
orientation((0.5, 0.5000000000000013 ) q, r) ->  1
orientation((0.5, 0.5000000000000012 ) q, r) ->  1
orientation((0.5, 0.5000000000000011 ) q, r) ->  1
orientation((0.5, 0.500000000000001  ) q, r) ->  1
orientation((0.5, 0.5000000000000009 ) q, r) ->  0
orientation((0.5, 0.5000000000000008 ) q, r) ->  0
orientation((0.5, 0.5000000000000007 ) q, r) ->  0
orientation((0.5, 0.5000000000000006 ) q, r) ->  0
orientation((0.5, 0.5000000000000004 ) q, r) ->  0
orientation((0.5, 0.5000000000000003 ) q, r) ->  0
orientation((0.5, 0.5000000000000002 ) q, r) ->  0
orientation((0.5, 0.5000000000000001 ) q, r) ->  0
orientation((0.5, 0.5                ) q, r) ->  0
orientation((0.5, 0.49999999999999994) q, r) ->  0
orientation((0.5, 0.4999999999999999 ) q, r) ->  0
orientation((0.5, 0.49999999999999983) q, r) ->  0
orientation((0.5, 0.4999999999999998 ) q, r) ->  0
orientation((0.5, 0.4999999999999997 ) q, r) ->  0
orientation((0.5, 0.49999999999999967) q, r) ->  0
orientation((0.5, 0.4999999999999996 ) q, r) ->  0
orientation((0.5, 0.49999999999999956) q, r) ->  0
orientation((0.5, 0.4999999999999995 ) q, r) ->  0
orientation((0.5, 0.49999999999999944) q, r) ->  0
orientation((0.5, 0.4999999999999994 ) q, r) ->  0
orientation((0.5, 0.49999999999999933) q, r) ->  0
orientation((0.5, 0.4999999999999993 ) q, r) ->  0
orientation((0.5, 0.4999999999999992 ) q, r) ->  0
orientation((0.5, 0.49999999999999917) q, r) ->  0
orientation((0.5, 0.4999999999999991 ) q, r) ->  0
orientation((0.5, 0.49999999999999906) q, r) -> -1
orientation((0.5, 0.499999999999999  ) q, r) -> -1
orientation((0.5, 0.49999999999999895) q, r) -> -1
orientation((0.5, 0.4999999999999989 ) q, r) -> -1
orientation((0.5, 0.49999999999999883) q, r) -> -1
orientation((0.5, 0.4999999999999988 ) q, r) -> -1
orientation((0.5, 0.4999999999999987 ) q, r) -> -1
orientation((0.5, 0.49999999999999867) q, r) -> -1
orientation((0.5, 0.4999999999999986 ) q, r) -> -1
orientation((0.5, 0.49999999999999856) q, r) -> -1
orientation((0.5, 0.4999999999999985 ) q, r) -> -1
orientation((0.5, 0.49999999999999845) q, r) -> -1
orientation((0.5, 0.4999999999999984 ) q, r) -> -1
orientation((0.5, 0.49999999999999833) q, r) -> -1
orientation((0.5, 0.4999999999999983 ) q, r) -> -1
orientation((0.5, 0.4999999999999982 ) q, r) -> -1
orientation((0.5, 0.49999999999999817) q, r) ->  0
orientation((0.5, 0.4999999999999981 ) q, r) ->  0
orientation((0.5, 0.49999999999999806) q, r) ->  0
orientation((0.5, 0.499999999999998  ) q, r) ->  0
orientation((0.5, 0.49999999999999795) q, r) ->  0
orientation((0.5, 0.4999999999999979 ) q, r) ->  0
orientation((0.5, 0.49999999999999784) q, r) ->  0
orientation((0.5, 0.4999999999999978 ) q, r) ->  0
orientation((0.5, 0.4999999999999977 ) q, r) ->  0
orientation((0.5, 0.49999999999999767) q, r) ->  0
orientation((0.5, 0.4999999999999976 ) q, r) ->  0
orientation((0.5, 0.49999999999999756) q, r) ->  0
orientation((0.5, 0.4999999999999975 ) q, r) ->  0
orientation((0.5, 0.49999999999999745) q, r) ->  0
orientation((0.5, 0.4999999999999974 ) q, r) ->  0
orientation((0.5, 0.49999999999999734) q, r) ->  0
orientation((0.5, 0.4999999999999973 ) q, r) ->  0
orientation((0.5, 0.4999999999999972 ) q, r) ->  0
orientation((0.5, 0.49999999999999717) q, r) ->  0
orientation((0.5, 0.4999999999999971 ) q, r) ->  0
orientation((0.5, 0.49999999999999706) q, r) ->  0
orientation((0.5, 0.499999999999997  ) q, r) ->  0
orientation((0.5, 0.49999999999999695) q, r) ->  0
orientation((0.5, 0.4999999999999969 ) q, r) ->  0
orientation((0.5, 0.49999999999999684) q, r) ->  0
orientation((0.5, 0.4999999999999968 ) q, r) ->  0
orientation((0.5, 0.4999999999999967 ) q, r) ->  0
orientation((0.5, 0.49999999999999667) q, r) ->  0
orientation((0.5, 0.4999999999999966 ) q, r) ->  0
orientation((0.5, 0.49999999999999656) q, r) ->  0
orientation((0.5, 0.4999999999999965 ) q, r) ->  0
orientation((0.5, 0.49999999999999645) q, r) ->  0
orientation((0.5, 0.4999999999999964 ) q, r) ->  0
orientation((0.5, 0.49999999999999634) q, r) ->  0
orientation((0.5, 0.4999999999999963 ) q, r) ->  0
orientation((0.5, 0.4999999999999962 ) q, r) ->  0
orientation((0.5, 0.49999999999999617) q, r) ->  0
orientation((0.5, 0.4999999999999961 ) q, r) ->  0
orientation((0.5, 0.49999999999999606) q, r) ->  0
orientation((0.5, 0.499999999999996  ) q, r) ->  0
orientation((0.5, 0.49999999999999595) q, r) ->  0
orientation((0.5, 0.4999999999999959 ) q, r) ->  0
orientation((0.5, 0.49999999999999584) q, r) ->  0
orientation((0.5, 0.4999999999999958 ) q, r) ->  0
orientation((0.5, 0.4999999999999957 ) q, r) ->  0
orientation((0.5, 0.49999999999999567) q, r) ->  0
orientation((0.5, 0.4999999999999956 ) q, r) ->  0
orientation((0.5, 0.49999999999999556) q, r) ->  0
orientation((0.5, 0.4999999999999955 ) q, r) -> -1
orientation((0.5, 0.49999999999999545) q, r) -> -1
orientation((0.5, 0.4999999999999954 ) q, r) -> -1
orientation((0.5, 0.49999999999999534) q, r) -> -1
orientation((0.5, 0.4999999999999953 ) q, r) -> -1
orientation((0.5, 0.4999999999999952 ) q, r) -> -1
orientation((0.5, 0.49999999999999517) q, r) -> -1
orientation((0.5, 0.4999999999999951 ) q, r) -> -1
orientation((0.5, 0.49999999999999506) q, r) -> -1
orientation((0.5, 0.499999999999995  ) q, r) -> -1
orientation((0.5, 0.49999999999999495) q, r) -> -1
orientation((0.5, 0.4999999999999949 ) q, r) -> -1
orientation((0.5, 0.49999999999999484) q, r) -> -1
orientation((0.5, 0.4999999999999948 ) q, r) -> -1
orientation((0.5, 0.4999999999999947 ) q, r) -> -1
orientation((0.5, 0.49999999999999467) q, r) -> -1
orientation((0.5, 0.4999999999999946 ) q, r) -> -1
orientation((0.5, 0.49999999999999456) q, r) -> -1
orientation((0.5, 0.4999999999999945 ) q, r) -> -1
orientation((0.5, 0.49999999999999445) q, r) -> -1
orientation((0.5, 0.4999999999999944 ) q, r) -> -1
orientation((0.5, 0.49999999999999434) q, r) -> -1
orientation((0.5, 0.4999999999999943 ) q, r) -> -1
orientation((0.5, 0.4999999999999942 ) q, r) -> -1
orientation((0.5, 0.49999999999999417) q, r) -> -1
orientation((0.5, 0.4999999999999941 ) q, r) -> -1
orientation((0.5, 0.49999999999999406) q, r) -> -1
orientation((0.5, 0.499999999999994  ) q, r) -> -1
orientation((0.5, 0.49999999999999395) q, r) -> -1
orientation((0.5, 0.4999999999999939 ) q, r) -> -1
orientation((0.5, 0.49999999999999384) q, r) -> -1
orientation((0.5, 0.4999999999999938 ) q, r) -> -1
orientation((0.5, 0.4999999999999937 ) q, r) -> -1
orientation((0.5, 0.49999999999999367) q, r) -> -1
orientation((0.5, 0.4999999999999936 ) q, r) -> -1
orientation((0.5, 0.49999999999999356) q, r) -> -1
orientation((0.5, 0.4999999999999935 ) q, r) -> -1
orientation((0.5, 0.49999999999999345) q, r) -> -1
orientation((0.5, 0.4999999999999934 ) q, r) -> -1
orientation((0.5, 0.49999999999999334) q, r) -> -1
orientation((0.5, 0.4999999999999933 ) q, r) -> -1
orientation((0.5, 0.4999999999999932 ) q, r) -> -1
orientation((0.5, 0.49999999999999317) q, r) -> -1
orientation((0.5, 0.4999999999999931 ) q, r) -> -1
orientation((0.5, 0.49999999999999306) q, r) -> -1
orientation((0.5, 0.499999999999993  ) q, r) -> -1
orientation((0.5, 0.49999999999999295) q, r) -> -1
orientation((0.5, 0.4999999999999929 ) q, r) -> -1
orientation((0.5, 0.49999999999999284) q, r) -> -1
orientation((0.5, 0.4999999999999928 ) q, r) -> -1
orientation((0.5, 0.49999999999999273) q, r) -> -1
orientation((0.5, 0.4999999999999927 ) q, r) -> -1
orientation((0.5, 0.4999999999999926 ) q, r) -> -1
orientation((0.5, 0.49999999999999256) q, r) -> -1
orientation((0.5, 0.4999999999999925 ) q, r) -> -1
orientation((0.5, 0.49999999999999245) q, r) -> -1
orientation((0.5, 0.4999999999999924 ) q, r) -> -1
orientation((0.5, 0.49999999999999234) q, r) -> -1
orientation((0.5, 0.4999999999999923 ) q, r) -> -1
orientation((0.5, 0.49999999999999223) q, r) -> -1
orientation((0.5, 0.4999999999999922 ) q, r) -> -1
orientation((0.5, 0.4999999999999921 ) q, r) -> -1
orientation((0.5, 0.49999999999999206) q, r) -> -1
orientation((0.5, 0.499999999999992  ) q, r) -> -1
orientation((0.5, 0.49999999999999195) q, r) -> -1
orientation((0.5, 0.4999999999999919 ) q, r) -> -1
orientation((0.5, 0.49999999999999184) q, r) -> -1
orientation((0.5, 0.4999999999999918 ) q, r) -> -1
orientation((0.5, 0.49999999999999173) q, r) -> -1
orientation((0.5, 0.4999999999999917 ) q, r) -> -1
orientation((0.5, 0.4999999999999916 ) q, r) -> -1
orientation((0.5, 0.49999999999999156) q, r) -> -1
orientation((0.5, 0.4999999999999915 ) q, r) -> -1
orientation((0.5, 0.49999999999999145) q, r) -> -1
orientation((0.5, 0.4999999999999914 ) q, r) -> -1
orientation((0.5, 0.49999999999999134) q, r) -> -1
orientation((0.5, 0.4999999999999913 ) q, r) -> -1
orientation((0.5, 0.49999999999999123) q, r) -> -1
orientation((0.5, 0.4999999999999912 ) q, r) -> -1
orientation((0.5, 0.4999999999999911 ) q, r) -> -1
orientation((0.5, 0.49999999999999106) q, r) -> -1
orientation((0.5, 0.499999999999991  ) q, r) -> -1
orientation((0.5, 0.49999999999999095) q, r) -> -1
orientation((0.5, 0.4999999999999909 ) q, r) -> -1
orientation((0.5, 0.49999999999999084) q, r) -> -1
orientation((0.5, 0.4999999999999908 ) q, r) -> -1
orientation((0.5, 0.49999999999999073) q, r) -> -1
orientation((0.5, 0.4999999999999907 ) q, r) -> -1
orientation((0.5, 0.4999999999999906 ) q, r) -> -1
orientation((0.5, 0.49999999999999056) q, r) -> -1
orientation((0.5, 0.4999999999999905 ) q, r) -> -1
orientation((0.5, 0.49999999999999045) q, r) -> -1
orientation((0.5, 0.4999999999999904 ) q, r) -> -1
orientation((0.5, 0.49999999999999034) q, r) -> -1
orientation((0.5, 0.4999999999999903 ) q, r) -> -1
orientation((0.5, 0.49999999999999023) q, r) -> -1
orientation((0.5, 0.4999999999999902 ) q, r) -> -1
orientation((0.5, 0.4999999999999901 ) q, r) -> -1
orientation((0.5, 0.49999999999999006) q, r) -> -1
orientation((0.5, 0.49999999999999   ) q, r) -> -1



The colour coding (added later) represents whether the algorithm reckons the points are above the line (in blue), on the line (in yellow) or below the line (in red). The only point which is actually on the line is in green.

By this point you should at least be wary of using floating point arithmetic for geometric computation. Lest you think this can easily be solved by introducing a tolerance value, or some other clunky solution, we'll save you the bother by pointing out that doing do merely moves these fringing effects to the edge of the tolerance zone.

What to do? Fortunately, as we alluded to at the beginning of this tale, Python gives us a solution into the form of the rational numbers, implemented as the Fraction type.

Let's make a small change to our program, converting all numbers to Fractions before proceeding with the computation. We'll do this by modifying the orientation() to convert each of its three arguments from a tuple containing a pair of numeric objects into a pair of Fractions. The Fraction constructor accepts a selection of numeric types, including float:

def orientation(p, q, r):
"""Determine the orientation of three points in the plane.

Args:
p, q, r: Two-tuples representing coordinate pairs of three points.

Returns:
-1 if p, q, r is a turn to the right, +1 if p, q, r is a turn to the
left, otherwise 0 if p, q, and r are collinear.
"""
p = (Fraction(p[0]), Fraction(p[1]))
q = (Fraction(q[0]), Fraction(q[1]))
r = (Fraction(r[0]), Fraction(r[1]))

d = (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
return sign(d)


The variable d will now also be a Fraction and the sign() function will work as expected with this type since it only uses comparison to zero.

Let's run our modified example:

orientation((0.5, 0.49999999999999   ) q, r) -> -1
orientation((0.5, 0.49999999999999006) q, r) -> -1
orientation((0.5, 0.4999999999999901 ) q, r) -> -1
orientation((0.5, 0.4999999999999902 ) q, r) -> -1
orientation((0.5, 0.49999999999999023) q, r) -> -1
orientation((0.5, 0.4999999999999903 ) q, r) -> -1
orientation((0.5, 0.49999999999999034) q, r) -> -1
orientation((0.5, 0.4999999999999904 ) q, r) -> -1
orientation((0.5, 0.49999999999999045) q, r) -> -1
orientation((0.5, 0.4999999999999905 ) q, r) -> -1
orientation((0.5, 0.49999999999999056) q, r) -> -1
orientation((0.5, 0.4999999999999906 ) q, r) -> -1
orientation((0.5, 0.4999999999999907 ) q, r) -> -1
orientation((0.5, 0.49999999999999073) q, r) -> -1
orientation((0.5, 0.4999999999999908 ) q, r) -> -1
orientation((0.5, 0.49999999999999084) q, r) -> -1
orientation((0.5, 0.4999999999999909 ) q, r) -> -1
orientation((0.5, 0.49999999999999095) q, r) -> -1
orientation((0.5, 0.499999999999991  ) q, r) -> -1
orientation((0.5, 0.49999999999999106) q, r) -> -1
orientation((0.5, 0.4999999999999911 ) q, r) -> -1
orientation((0.5, 0.4999999999999912 ) q, r) -> -1
orientation((0.5, 0.49999999999999123) q, r) -> -1
orientation((0.5, 0.4999999999999913 ) q, r) -> -1
orientation((0.5, 0.49999999999999134) q, r) -> -1
orientation((0.5, 0.4999999999999914 ) q, r) -> -1
orientation((0.5, 0.49999999999999145) q, r) -> -1
orientation((0.5, 0.4999999999999915 ) q, r) -> -1
orientation((0.5, 0.49999999999999156) q, r) -> -1
orientation((0.5, 0.4999999999999916 ) q, r) -> -1
orientation((0.5, 0.4999999999999917 ) q, r) -> -1
orientation((0.5, 0.49999999999999173) q, r) -> -1
orientation((0.5, 0.4999999999999918 ) q, r) -> -1
orientation((0.5, 0.49999999999999184) q, r) -> -1
orientation((0.5, 0.4999999999999919 ) q, r) -> -1
orientation((0.5, 0.49999999999999195) q, r) -> -1
orientation((0.5, 0.499999999999992  ) q, r) -> -1
orientation((0.5, 0.49999999999999206) q, r) -> -1
orientation((0.5, 0.4999999999999921 ) q, r) -> -1
orientation((0.5, 0.4999999999999922 ) q, r) -> -1
orientation((0.5, 0.49999999999999223) q, r) -> -1
orientation((0.5, 0.4999999999999923 ) q, r) -> -1
orientation((0.5, 0.49999999999999234) q, r) -> -1
orientation((0.5, 0.4999999999999924 ) q, r) -> -1
orientation((0.5, 0.49999999999999245) q, r) -> -1
orientation((0.5, 0.4999999999999925 ) q, r) -> -1
orientation((0.5, 0.49999999999999256) q, r) -> -1
orientation((0.5, 0.4999999999999926 ) q, r) -> -1
orientation((0.5, 0.4999999999999927 ) q, r) -> -1
orientation((0.5, 0.49999999999999273) q, r) -> -1
orientation((0.5, 0.4999999999999928 ) q, r) -> -1
orientation((0.5, 0.49999999999999284) q, r) -> -1
orientation((0.5, 0.4999999999999929 ) q, r) -> -1
orientation((0.5, 0.49999999999999295) q, r) -> -1
orientation((0.5, 0.499999999999993  ) q, r) -> -1
orientation((0.5, 0.49999999999999306) q, r) -> -1
orientation((0.5, 0.4999999999999931 ) q, r) -> -1
orientation((0.5, 0.49999999999999317) q, r) -> -1
orientation((0.5, 0.4999999999999932 ) q, r) -> -1
orientation((0.5, 0.4999999999999933 ) q, r) -> -1
orientation((0.5, 0.49999999999999334) q, r) -> -1
orientation((0.5, 0.4999999999999934 ) q, r) -> -1
orientation((0.5, 0.49999999999999345) q, r) -> -1
orientation((0.5, 0.4999999999999935 ) q, r) -> -1
orientation((0.5, 0.49999999999999356) q, r) -> -1
orientation((0.5, 0.4999999999999936 ) q, r) -> -1
orientation((0.5, 0.49999999999999367) q, r) -> -1
orientation((0.5, 0.4999999999999937 ) q, r) -> -1
orientation((0.5, 0.4999999999999938 ) q, r) -> -1
orientation((0.5, 0.49999999999999384) q, r) -> -1
orientation((0.5, 0.4999999999999939 ) q, r) -> -1
orientation((0.5, 0.49999999999999395) q, r) -> -1
orientation((0.5, 0.499999999999994  ) q, r) -> -1
orientation((0.5, 0.49999999999999406) q, r) -> -1
orientation((0.5, 0.4999999999999941 ) q, r) -> -1
orientation((0.5, 0.49999999999999417) q, r) -> -1
orientation((0.5, 0.4999999999999942 ) q, r) -> -1
orientation((0.5, 0.4999999999999943 ) q, r) -> -1
orientation((0.5, 0.49999999999999434) q, r) -> -1
orientation((0.5, 0.4999999999999944 ) q, r) -> -1
orientation((0.5, 0.49999999999999445) q, r) -> -1
orientation((0.5, 0.4999999999999945 ) q, r) -> -1
orientation((0.5, 0.49999999999999456) q, r) -> -1
orientation((0.5, 0.4999999999999946 ) q, r) -> -1
orientation((0.5, 0.49999999999999467) q, r) -> -1
orientation((0.5, 0.4999999999999947 ) q, r) -> -1
orientation((0.5, 0.4999999999999948 ) q, r) -> -1
orientation((0.5, 0.49999999999999484) q, r) -> -1
orientation((0.5, 0.4999999999999949 ) q, r) -> -1
orientation((0.5, 0.49999999999999495) q, r) -> -1
orientation((0.5, 0.499999999999995  ) q, r) -> -1
orientation((0.5, 0.49999999999999506) q, r) -> -1
orientation((0.5, 0.4999999999999951 ) q, r) -> -1
orientation((0.5, 0.49999999999999517) q, r) -> -1
orientation((0.5, 0.4999999999999952 ) q, r) -> -1
orientation((0.5, 0.4999999999999953 ) q, r) -> -1
orientation((0.5, 0.49999999999999534) q, r) -> -1
orientation((0.5, 0.4999999999999954 ) q, r) -> -1
orientation((0.5, 0.49999999999999545) q, r) -> -1
orientation((0.5, 0.4999999999999955 ) q, r) -> -1
orientation((0.5, 0.49999999999999556) q, r) -> -1
orientation((0.5, 0.4999999999999956 ) q, r) -> -1
orientation((0.5, 0.49999999999999567) q, r) -> -1
orientation((0.5, 0.4999999999999957 ) q, r) -> -1
orientation((0.5, 0.4999999999999958 ) q, r) -> -1
orientation((0.5, 0.49999999999999584) q, r) -> -1
orientation((0.5, 0.4999999999999959 ) q, r) -> -1
orientation((0.5, 0.49999999999999595) q, r) -> -1
orientation((0.5, 0.499999999999996  ) q, r) -> -1
orientation((0.5, 0.49999999999999606) q, r) -> -1
orientation((0.5, 0.4999999999999961 ) q, r) -> -1
orientation((0.5, 0.49999999999999617) q, r) -> -1
orientation((0.5, 0.4999999999999962 ) q, r) -> -1
orientation((0.5, 0.4999999999999963 ) q, r) -> -1
orientation((0.5, 0.49999999999999634) q, r) -> -1
orientation((0.5, 0.4999999999999964 ) q, r) -> -1
orientation((0.5, 0.49999999999999645) q, r) -> -1
orientation((0.5, 0.4999999999999965 ) q, r) -> -1
orientation((0.5, 0.49999999999999656) q, r) -> -1
orientation((0.5, 0.4999999999999966 ) q, r) -> -1
orientation((0.5, 0.49999999999999667) q, r) -> -1
orientation((0.5, 0.4999999999999967 ) q, r) -> -1
orientation((0.5, 0.4999999999999968 ) q, r) -> -1
orientation((0.5, 0.49999999999999684) q, r) -> -1
orientation((0.5, 0.4999999999999969 ) q, r) -> -1
orientation((0.5, 0.49999999999999695) q, r) -> -1
orientation((0.5, 0.499999999999997  ) q, r) -> -1
orientation((0.5, 0.49999999999999706) q, r) -> -1
orientation((0.5, 0.4999999999999971 ) q, r) -> -1
orientation((0.5, 0.49999999999999717) q, r) -> -1
orientation((0.5, 0.4999999999999972 ) q, r) -> -1
orientation((0.5, 0.4999999999999973 ) q, r) -> -1
orientation((0.5, 0.49999999999999734) q, r) -> -1
orientation((0.5, 0.4999999999999974 ) q, r) -> -1
orientation((0.5, 0.49999999999999745) q, r) -> -1
orientation((0.5, 0.4999999999999975 ) q, r) -> -1
orientation((0.5, 0.49999999999999756) q, r) -> -1
orientation((0.5, 0.4999999999999976 ) q, r) -> -1
orientation((0.5, 0.49999999999999767) q, r) -> -1
orientation((0.5, 0.4999999999999977 ) q, r) -> -1
orientation((0.5, 0.4999999999999978 ) q, r) -> -1
orientation((0.5, 0.49999999999999784) q, r) -> -1
orientation((0.5, 0.4999999999999979 ) q, r) -> -1
orientation((0.5, 0.49999999999999795) q, r) -> -1
orientation((0.5, 0.499999999999998  ) q, r) -> -1
orientation((0.5, 0.49999999999999806) q, r) -> -1
orientation((0.5, 0.4999999999999981 ) q, r) -> -1
orientation((0.5, 0.49999999999999817) q, r) -> -1
orientation((0.5, 0.4999999999999982 ) q, r) -> -1
orientation((0.5, 0.4999999999999983 ) q, r) -> -1
orientation((0.5, 0.49999999999999833) q, r) -> -1
orientation((0.5, 0.4999999999999984 ) q, r) -> -1
orientation((0.5, 0.49999999999999845) q, r) -> -1
orientation((0.5, 0.4999999999999985 ) q, r) -> -1
orientation((0.5, 0.49999999999999856) q, r) -> -1
orientation((0.5, 0.4999999999999986 ) q, r) -> -1
orientation((0.5, 0.49999999999999867) q, r) -> -1
orientation((0.5, 0.4999999999999987 ) q, r) -> -1
orientation((0.5, 0.4999999999999988 ) q, r) -> -1
orientation((0.5, 0.49999999999999883) q, r) -> -1
orientation((0.5, 0.4999999999999989 ) q, r) -> -1
orientation((0.5, 0.49999999999999895) q, r) -> -1
orientation((0.5, 0.499999999999999  ) q, r) -> -1
orientation((0.5, 0.49999999999999906) q, r) -> -1
orientation((0.5, 0.4999999999999991 ) q, r) -> -1
orientation((0.5, 0.49999999999999917) q, r) -> -1
orientation((0.5, 0.4999999999999992 ) q, r) -> -1
orientation((0.5, 0.4999999999999993 ) q, r) -> -1
orientation((0.5, 0.49999999999999933) q, r) -> -1
orientation((0.5, 0.4999999999999994 ) q, r) -> -1
orientation((0.5, 0.49999999999999944) q, r) -> -1
orientation((0.5, 0.4999999999999995 ) q, r) -> -1
orientation((0.5, 0.49999999999999956) q, r) -> -1
orientation((0.5, 0.4999999999999996 ) q, r) -> -1
orientation((0.5, 0.49999999999999967) q, r) -> -1
orientation((0.5, 0.4999999999999997 ) q, r) -> -1
orientation((0.5, 0.4999999999999998 ) q, r) -> -1
orientation((0.5, 0.49999999999999983) q, r) -> -1
orientation((0.5, 0.4999999999999999 ) q, r) -> -1
orientation((0.5, 0.49999999999999994) q, r) -> -1
orientation((0.5, 0.5                ) q, r) ->  0
orientation((0.5, 0.5000000000000001 ) q, r) ->  1
orientation((0.5, 0.5000000000000002 ) q, r) ->  1
orientation((0.5, 0.5000000000000003 ) q, r) ->  1
orientation((0.5, 0.5000000000000004 ) q, r) ->  1
orientation((0.5, 0.5000000000000006 ) q, r) ->  1
orientation((0.5, 0.5000000000000007 ) q, r) ->  1
orientation((0.5, 0.5000000000000008 ) q, r) ->  1
orientation((0.5, 0.5000000000000009 ) q, r) ->  1
orientation((0.5, 0.500000000000001  ) q, r) ->  1
orientation((0.5, 0.5000000000000011 ) q, r) ->  1
orientation((0.5, 0.5000000000000012 ) q, r) ->  1
orientation((0.5, 0.5000000000000013 ) q, r) ->  1
orientation((0.5, 0.5000000000000014 ) q, r) ->  1
orientation((0.5, 0.5000000000000016 ) q, r) ->  1
orientation((0.5, 0.5000000000000017 ) q, r) ->  1
orientation((0.5, 0.5000000000000018 ) q, r) ->  1
orientation((0.5, 0.5000000000000019 ) q, r) ->  1
orientation((0.5, 0.500000000000002  ) q, r) ->  1
orientation((0.5, 0.5000000000000021 ) q, r) ->  1
orientation((0.5, 0.5000000000000022 ) q, r) ->  1
orientation((0.5, 0.5000000000000023 ) q, r) ->  1
orientation((0.5, 0.5000000000000024 ) q, r) ->  1
orientation((0.5, 0.5000000000000026 ) q, r) ->  1
orientation((0.5, 0.5000000000000027 ) q, r) ->  1
orientation((0.5, 0.5000000000000028 ) q, r) ->  1
orientation((0.5, 0.5000000000000029 ) q, r) ->  1
orientation((0.5, 0.500000000000003  ) q, r) ->  1
orientation((0.5, 0.5000000000000031 ) q, r) ->  1
orientation((0.5, 0.5000000000000032 ) q, r) ->  1
orientation((0.5, 0.5000000000000033 ) q, r) ->  1
orientation((0.5, 0.5000000000000034 ) q, r) ->  1
orientation((0.5, 0.5000000000000036 ) q, r) ->  1
orientation((0.5, 0.5000000000000037 ) q, r) ->  1
orientation((0.5, 0.5000000000000038 ) q, r) ->  1
orientation((0.5, 0.5000000000000039 ) q, r) ->  1
orientation((0.5, 0.500000000000004  ) q, r) ->  1
orientation((0.5, 0.5000000000000041 ) q, r) ->  1
orientation((0.5, 0.5000000000000042 ) q, r) ->  1
orientation((0.5, 0.5000000000000043 ) q, r) ->  1
orientation((0.5, 0.5000000000000044 ) q, r) ->  1
orientation((0.5, 0.5000000000000046 ) q, r) ->  1
orientation((0.5, 0.5000000000000047 ) q, r) ->  1
orientation((0.5, 0.5000000000000048 ) q, r) ->  1
orientation((0.5, 0.5000000000000049 ) q, r) ->  1
orientation((0.5, 0.500000000000005  ) q, r) ->  1
orientation((0.5, 0.5000000000000051 ) q, r) ->  1
orientation((0.5, 0.5000000000000052 ) q, r) ->  1
orientation((0.5, 0.5000000000000053 ) q, r) ->  1
orientation((0.5, 0.5000000000000054 ) q, r) ->  1
orientation((0.5, 0.5000000000000056 ) q, r) ->  1
orientation((0.5, 0.5000000000000057 ) q, r) ->  1
orientation((0.5, 0.5000000000000058 ) q, r) ->  1
orientation((0.5, 0.5000000000000059 ) q, r) ->  1
orientation((0.5, 0.500000000000006  ) q, r) ->  1
orientation((0.5, 0.5000000000000061 ) q, r) ->  1
orientation((0.5, 0.5000000000000062 ) q, r) ->  1
orientation((0.5, 0.5000000000000063 ) q, r) ->  1
orientation((0.5, 0.5000000000000064 ) q, r) ->  1
orientation((0.5, 0.5000000000000066 ) q, r) ->  1
orientation((0.5, 0.5000000000000067 ) q, r) ->  1
orientation((0.5, 0.5000000000000068 ) q, r) ->  1
orientation((0.5, 0.5000000000000069 ) q, r) ->  1
orientation((0.5, 0.500000000000007  ) q, r) ->  1
orientation((0.5, 0.5000000000000071 ) q, r) ->  1
orientation((0.5, 0.5000000000000072 ) q, r) ->  1
orientation((0.5, 0.5000000000000073 ) q, r) ->  1
orientation((0.5, 0.5000000000000074 ) q, r) ->  1
orientation((0.5, 0.5000000000000075 ) q, r) ->  1
orientation((0.5, 0.5000000000000077 ) q, r) ->  1
orientation((0.5, 0.5000000000000078 ) q, r) ->  1
orientation((0.5, 0.5000000000000079 ) q, r) ->  1
orientation((0.5, 0.500000000000008  ) q, r) ->  1
orientation((0.5, 0.5000000000000081 ) q, r) ->  1
orientation((0.5, 0.5000000000000082 ) q, r) ->  1
orientation((0.5, 0.5000000000000083 ) q, r) ->  1
orientation((0.5, 0.5000000000000084 ) q, r) ->  1
orientation((0.5, 0.5000000000000085 ) q, r) ->  1
orientation((0.5, 0.5000000000000087 ) q, r) ->  1
orientation((0.5, 0.5000000000000088 ) q, r) ->  1
orientation((0.5, 0.5000000000000089 ) q, r) ->  1
orientation((0.5, 0.500000000000009  ) q, r) ->  1
orientation((0.5, 0.5000000000000091 ) q, r) ->  1
orientation((0.5, 0.5000000000000092 ) q, r) ->  1
orientation((0.5, 0.5000000000000093 ) q, r) ->  1
orientation((0.5, 0.5000000000000094 ) q, r) ->  1
orientation((0.5, 0.5000000000000095 ) q, r) ->  1
orientation((0.5, 0.5000000000000097 ) q, r) ->  1
orientation((0.5, 0.5000000000000098 ) q, r) ->  1
orientation((0.5, 0.5000000000000099 ) q, r) ->  1
orientation((0.5, 0.50000000000001   ) q, r) ->  1



Using Fractions internally, our orientation() function gets the full benefit of exact arithmetic with effectively infinite precision and consequently produces an exact result with only one position of p being reported as collinear with q and r.

In the next article, we'll more fully explore the behaviour of the non-robust float-based version of this function based graphically, to get an impression of how lines are 'seen' by floating-point geometric functions.

 [1] Python's float is an IEEE-754 double precision 64-bit float.

### Business of Software Conference Europe

Our founder Anna attended the Business of Software Europe Conference in Cambridge last week, and it was quite something indeed.

Although the Business of Software Conference has been running for several years in the USA, this is the first year an event has been held in Europe (and what better a place than Cambridge?). The conference covered everything from live Python telephony to the psychology of the internet and the organisation and management of sales teams, so it was pretty diverse.

If you are interested in more than just coding, this is an event we can strongly recommend. Photos and videos from the conference should be online soon, so if you are interested please stay tuned.

### Business of Software Conference Europe

Our founder Anna attended the Business of Software Europe Conference in Cambridge last week, and it was quite something indeed.

Although the Business of Software Conference has been running for several years in the USA, this is the first year an event has been held in Europe (and what better a place than Cambridge?). The conference covered everything from live Python telephony to the psychology of the internet and the organisation and management of sales teams, so it was pretty diverse.

If you are interested in more than just coding, this is an event we can strongly recommend. Photos and videos from the conference should be online soon, so if you are interested please stay tuned.

### Business of Software Conference Europe

Our founder Anna attended the Business of Software Europe Conference in Cambridge last week, and it was quite something indeed. Although the Business of Software Conference has been running for several years in the USA, this is the first year an event has been held in Europe (and what better a place than Cambridge?). The conference covered everything from live Python telephony to the psychology of the internet and the organisation and management of sales teams, so it was pretty diverse. If you are interested in more than just coding, this is an event we can strongly recommend. Photos and videos from the conference should be online soon, so if you are interested please stay tuned.

### Resolving strong references between Swift and Objective-C classes – Using unowned and weak references from Swift to Objective-C classes

My Swift and SpriteKit exploration continues. At the moment I'm writing the collision handling code.

Rather than derive game objects from SKSpriteNode with each derived class containing the code for handling collisions with the other types of game objects I'm following something akin to a Component-Entity model.

I have per-game-object handler classes of which an instance of each is stored in the actual SKSpriteNode's userData dictionary. In turn each handler instance has a reference to the SKSpriteNode that references it. Given ARC is used this is a classical strong-reference chain which will prevent memory from being freed. The usual solution to this in Objective-C is to have one of the references be weak. In Swift there are two types of weak references: weak which is the same as in Objective-C and unowned (which I think is new). The difference is that an unowned reference can never be nil, i.e. it's optional whether a weak pointer reference an object but an unowned pointer must always reference something. As such the member variable is always defined using let and must be initialized, i.e. an init method is required.

The following code shows how I was intending to implement this. There is the strong reference from node.UserData to PhysicsActions and then the unowned reference back again from PhysicsActions.

class PhysicsActions
{
unowned let node : SKSpriteNode

init(associatedNode : SKSpriteNode)
{
// Store really weak (unowned) reference
self.node = associatedNode
}

func onContact(other : PhysicsActions)
{
// Do stuff with node

}
}

class func makeNode(imageNamed name: String) -> SKSpriteNode
{
let node = SKSpriteNode(imageNamed: name)
node.userData = NSMutableDictionary()
// Store strong reference
node.userData["action"] = makeActionFn(node)
return node

}

However, when I went to use this code it crashed within the onContact method when it attempted to use the node. Changing this the reference type from unowned to weak fixed this, e.g.

weak let node : SKSpriteNode?

This verified that the rest of the code was ok so this seemed to look like another Swift/Objective-C interoperability issue. Firstly, I made a pure Swift example which is a simplified version from the The Swift Programming Language book.

class Foo
{
var bar : Bar?

{
self.bar = bar
}
}

class Bar
{
unowned let foo : Foo
init(foo : Foo)
{
self.foo = foo
}

func f()
{
println("foo:\(foo)")
}
}

var foo : Foo? = Foo()
var bar = Bar(foo: foo!)
foo!.ç(bar)

bar.f()

Which works and results in:

foo:C14XXXUnownedTest3Foo (has 1 child)

Ok, not a fundamental problem but let's try having an unowned reference to an Objective-C class which is just like the real case as that's what SKSpriteNode is.

Foo2.h

@interface Foo2 : NSObject
@end

Foo2.m

@implementation Foo2

-(id)init
{
return [super init];
}

@end

main.swift

class Bar2
{
unowned let foo2 : Foo2
init(foo2 : Foo2)
{
self.foo2 = foo2
}

func f()
{
println("foo2:\(foo2)")
}
}

var foo2 = Foo2()
var bar2 = Bar2(foo2: foo2)
bar2.f()

Which when foo2.f() is invoked results in:

libswift_stdlib_core.dylib_swift_abortRetainUnowned:
0x100142420:  pushq  %rbp
0x100142421:  movq   %rsp, %rbp
0x100142424:  leaq   0x17597(%rip), %rax       ; "attempted to retain deallocated object"
0x10014242b:  movq   %rax, 0x348be(%rip)       ; gCRAnnotations + 8
0x100142432:  int3
0x100142433:  nopw   %cs:(%rax,%rax)

Again, changing unowned let foo2 : Foo2 to weak var foo2 : Foo2? works.

I can't explain what the actual problem is but it looks like the enhanced weak reference support (unowned) only works with pure Swift classes. If you have cyclic references to Objective-C classes from Swift then don't use unowned. In fact writing the previous sentence led me to try the following:

let orig = Foo2()
unowned let other = orig
println("other:\(other)")
println("orig:\(orig)")

No cyclic references, just an ordinary reference counted instance of Foo2 (the Objective-C class) which is then assigned to an unowned reference. The final call to println will keep the instance around until the end. This crashes as per the previous example when the other variable is accessed. Changing the type assigned to orig from Foo2 (Objective-C) to Foo (Swift) make it work.

Therefore it seems unowned should not be used to refer to Objective-C classes, just Swift classes.

### Beware: Despite the docs SKNode userData is optional

In the Swift documentation for SKNode the userData member (a dictionary) is defined as follows:

userData

A dictionary containing arbitrary data.

Declaration

SWIFT
var userData: NSMutableDictionary!

OBJECTIVE-C

@property(nonatomic, retain)*userData

However, in Objective-C the userData member is initially nil. Given that this is the same class then it should also be in Swift and using it, e.g.

let node = SKSpriteNode(imageNamed: name)
node.userData["action"] = Action() // custom class

causes a crash:

fatal error: Can't unwrap Optional.None

This is because the it is in fact nil despite the '!' following the Swift definition. This must be a documentation bug. The correct code is:

let node = SKSpriteNode(imageNamed: name)
node.userData = NSMutableDictionary()
node.userData["action"] = Action() // custom class

### Rename Selected Jenkins Jobs

Using jenkinsapi it is easy to rename some jobs:

from jenkinsapi.jenkins import JenkinsJ = Jenkins('http://localhost:8080')for j in J.keys():  if (j.startswith('bad-prefix')):    n = j.replace('bad-prefix', 'good-prefix')    J.rename_job(j, n)

### Python’s super(): Not as Simple as You Thought

Python's super() is one of those aspects of the language that many developers use without really understanding what it does or how it works. [1] To many people, super() is simply how you access your base-class's implementation of a method. And while this is true, it's far from the full story.

In this series I want to look at the mechanics and some of the theory behind super(). I want to show that, far from just letting you access your base-class, Python's super() is the key to some interesting and elegant design options that promote composability, separation of concerns, and long-term maintainability. In this first article I'll introduce a small set of classes, and in these classes we'll find a bit of a mystery. In subsequent articles we'll investigate this mystery by seeing how Python's super() really works, looking at topics like method resolution order, the C3 algorithm, and proxy objects.

In the end, you'll find that super() is both more complex than you probably expected, yet also surprisingly elegant and easy-to-understand. This improved understanding of super() will help you understand and appreciate Python on at a deeper level, and it will give you new tools for developing your own Python code.

## A note on Python versions

This series is written using Python 3, and some of the examples and concepts don't apply completely to Python 2. In particular, this series assumes that classes are "new-style" classes. ((For a discussion of the difference between "old-style" and "new-style" classes, see the Python wiki.)) In Python 3 all classes are new-style, while in Python 2 you have to explicitly inherit from object to be a new-style class.

For example, where we might use the following Python 3 code in this series:

class IntList:
. . .


the equivalent Python 2 code would be:

class IntList(object):
. . .


Also, throughout this series we'll call super() with no arguments. This is only supported in Python 3, but it has an equivalent form in Python 2. In general, when you see a method like this:

class IntList:


the equivalent Python 2 code has to pass the class name and self to super(), like this:

class IntList:


If any other Python2/3 differences occur in the series, I'll be sure to point them out. [2]

### The Mystery of the SortedIntList

To begin, we're going to define a small family of classes that implement some constrained list-like functionality. These classes form a diamond inheritance graph like this:

At the root of these classes is SimpleList:

class SimpleList:
def __init__(self, items):
self._items = list(items)

self._items.append(item)

def __getitem__(self, index):
return self._items[index]

def sort(self):
self._items.sort()

def __len__(self):
return len(self._items)

def __repr__(self):
return "{}({!r})".format(
self.__class__.__name__,
self._items)


SimpleList uses a standard list internally, and it provides a smaller, more limited API for interacting with the list data. This may not be a very realistic class from a practical point of view, but, as you'll see, it let's us explore some interesting aspects of inheritance relationships in Python.

Next let's create a subclass of SimpleList which keeps the list contents sorted. We'll call this class SortedList:

class SortedList(SimpleList):
def __init__(self, items=()):
super().__init__(items)
self.sort()

self.sort()


The initializer calls SimpleList's initializer and then immediately uses SimpleList.sort() to sort the contents. SortedList also overrides the add method on SimpleList to ensure that the list always remains sorted.

In SortedList we already see a call to super(), and the intention of this code is pretty clear. In SortedList.add(), for example, super() is used to call SimpleList.add() - that is, deferring to the base-class - before sorting the list contents. There's nothing mysterious going on...yet.

Next let's define IntList, a SimpleList subclass which only allows integer elements. This list subclass prevents the insertion of non-integer elements, and it does so by using the isinstance() function:

class IntList(SimpleList):
def __init__(self, items=()):
for item in items: self._validate(item)
super().__init__(items)

@classmethod
def _validate(cls, item):
if not isinstance(item, int):
raise TypeError(
'{} only supports integer values.'.format(
cls.__name__))

self._validate(item)


You'll immediately notice that IntList is structurally similar to SortedList. It provides its own initializer and, like SortedList, overrides the add() method to perform extra checks. In this case, IntList calls its _validate() method on every item that goes into the list. _validate() uses isinstance() to check the type of the candidates, and if a candidate is not an instance of int, _validate() raises a TypeError.

Chances are, neither SortedList nor IntList are particularly surprising. They both use super() for the job that most people find most natural: calling base-class implementations. With that in mind, then, let's introduce one more class, SortedIntList, which inherits from both SortedList and IntList, and which enforces both constraints at once:

class SortedIntList(IntList, SortedList):
pass


It doesn't look like much, does it? We've simply defined a new class and given it two base classes. In fact, we haven't added any new implementation code at all. But if we go to the REPL we can see that it works as we expect. The initializer sorts the input sequence:

>>> sil = SortedIntList([42, 23, 2])
>>> sil
SortedIntList([2, 23, 42])


but rejects non-integer values:

>>> SortedIntList([3, 2, '1'])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "sorted_int_list.py", line 43, in __init__
for x in items: self._validate(x)
File "sorted_int_list.py", line 49, in _validate
raise TypeError(
'{} only supports integer values.'.format(
cls.__name__))
TypeError: SortedIntList only supports integer values.


Likewise, add() maintains both the sorting and type constraints defined by the base classes:

>>> sil.add(-1234)
>>> sil
SortedIntList([-1234, 2, 23, 42])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "sorted_int_list.py", line 45, in add
self._validate(item)
File "sorted_int_list.py", line 42, in _validate
raise TypeError(
'{} only supports integer values.'.format(
cls.__name__))
TypeError: SortedIntList only supports integer values.
`

You should spend some time playing with SortedIntList to convince yourself that it works as expected. You can get the code here.

It may not be immediately apparent how all of this works, though. After all, both IntList and SortedList define add(). How does Python know which add() to call? More importantly, since both the sorting and type constraints are being enforced by SortedIntList, how does Python seem to know to call both of them? This is the mystery that this series will unravel, and the answers to these questions have to do with the method resolution order we mentioned earlier, along with the details of how super() really works. So stay tuned!

 [1] If you do know how it works, then congratulations! This series probably isn't for you. But believe me, lots of people don't.
 [2] For a detailed look at the differences between the language versions, see Guido's list of differences.

### Python’s super() explained

You probably already know how to use Python's super() to call base-class implementations of methods. But do you really know what it's doing? The details of super() are elegant, interesting, and powerful, and while super() is probably more complex than you expect, it's also surprisingly easy to understand. In this series we'll explore super() by first uncovering a bit of a mystery. To resolve the mystery, we'll look a bit under Python's hood to see how super() really works.

### Robust Geometric Computation in Python

In this series we look in detail at the behaviour of one of the simplest geometric functions, demonstrate its flawed behaviour when implemented with floating point numbers, and fix it using an exact number type provided in the Python Standard Library.