### Writing the Simplest Emacs company-mode Backend

In Emacs, company-mode (short for "complete anything") is a framework for performing completion in buffers. [1] It's an alternative to the popular auto-complete-mode. company-mode supports extension via backends which provide the framework with lists of possible completions in various contexts. So, for example, there's a backend th(at provides completion support for Emacs lisp and one that does the same for Python. Backends can use very different technologies as long as they conform to the backend interface specified by the mode.

I recently decided to write a company-mode backend for ycmd, a completion server for languages including C/C++/Objective-C and Python. [2] All in all it was a relatively pain-free experience, but the process isn't as well documented as I would have liked. So I want to use this series to describe how it's done with the hope of making it easier for others and of helping me remember how to do it in the future.

I won't be covering all of the details of company-mode backends (partially because I don't know them all), but this series should tell you what you need to know to create your own fully-armed and operational backend. [3] In this article we'll define the simplest possible backend in order to familiarize you with the concepts and infrastructure involved. In the next article we'll add some sophistication to that backend to improve the user experience.

## The simplest possible backend

For our example we need to define a source of completion candidates. Ultimately, any completion source is just a sequence of strings that meet some criteria. Examples might include:

• A list of English words starting with some prefix
• Methods for a particular object in Java
• Modules available for import in Python program

company-mode doesn't care about the nature of these strings. It just takes them and makes it easy for the user to select from the available options.

In this case, we'll just define a fixed list of strings:

(defconst sample-completions


That's it. [4] Completion sources don't need to (though they generally will) be more complex than that.

## Defining the backend

Backends take the form of a function which takes a command as its first argument. This command can take any of a number of values, and backends are required to respond to a handful of them. Before we get into those details, let's look at our very basic backend implementation:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  (require 'cl-lib) (require 'company) (defun company-sample-backend (command &optional arg &rest ignored) (interactive (list 'interactive)) (cl-case command (interactive (company-begin-backend 'company-sample-backend)) (prefix (and (eq major-mode 'fundamental-mode) (company-grab-symbol))) (candidates (cl-remove-if-not (lambda (c) (string-prefix-p arg c)) sample-completions)))) 

The signature of this function is mandated by company-mode. Line 5 makes the function interactive so that you can easily drive your backend without invoking company-mode, something we'll do in a bit. The cl-case statement on line 7 is where we decide what to do based on command. In this case, we respond to interactive, prefix, and candidates.

The interactive command is passed once, before the other commands are used, and it is used to initialize the company-mode infrastructure. All you need to do as a backend developer is pass your backend to company-begin-backend as in this example.

### The prefix command

The prefix command is probably the most complex command to handle. This command should return the text that is to be completed. Determining this text can be complex depending on what you're trying to complete, but company-grab-symbol often does "the right thing" if your completion context is space-delimited.

If the prefix command returns nil, this tells company-mode that the backend is not suitable for doing completion on this context. On line 9 of our example we check to see if we're in fundamental-mode and, if not, return nil. In other words, we're saying here that our backend only applies to fundamental-mode. Programming language-oriented backends can make a similar check for their specific modes. When a backend responds to prefix with nil, other backends are given a chance to do the completion.

On the other hand, if a backend is appropriate for the current completion but it can't provide any completions for some reason, the backend should return 'stop. This tells company-mode that no other backends should be used for this completion.

So our backend is effectively saying that it can do completion for anything in fundamental mode. There are more details to prefix, but that's covers the important parts.

### The candidates commands

The response to the candidates command is where you actually generate a list of possible completions at a point in a buffer. When this command is passed in, the arg argument holds the value returned by prefix. In other words, you construct your candidates based on the text that you previously indicated was to be completed.

In our case, the prefix we indicated was whatever came before point in the buffer. To calculate our possible completions, we filter the sample-completions values with that prefix using remove-if-not, returning only those candidates which begin with the prefix.

As with prefix calculations, real candidate calculations can be much more complex. But if you understand how the data is piped around, then constructing these complex candidate lists should be fairly straightforward.

### Test-driving the backend

To test out our backend, first enter all of the code into a buffer and evaluate it (e.g. with M-x eval-buffer.) Then create a new buffer and run M-x fundamental-mode and M-x company-mode. [5]

In this new buffer enter the single character "a" and then, with the cursor immediately after the "a", run M-x company-sample-backend. This should give you completion options something like this:

If that works correctly, then you've done almost everything you need to for a fully working backend.

### Plugging the backend into company-mode

The final thing you need to do to make your backend available to company-mode is to add it the list company-backends. One simple way to do that is with add-to-list list this:

(add-to-list 'company-backends 'company-sample-backend)


Once you've done this, you can use the command company-complete to do completions, and your new backend will be used in concert with all of the other backends in that list. Generally speaking, company-complete is the command you'll use for completion with company-mode, and it'll often be bound to a simple keystroke.

### A complete company-mode backend

That's all there is to writing a basic company-mode backend. In the next article in this series we'll look at adding a few more details to what we have already.

(require 'company)

(defconst sample-completions

(defun company-sample-backend (command &optional arg &rest ignored)
(interactive (list 'interactive))

(case command
(interactive (company-begin-backend 'company-sample-backend))
(prefix (and (eq major-mode 'fundamental-mode)
(company-grab-symbol)))
(candidates
(remove-if-not
(lambda (c) (string-prefix-p arg c))
sample-completions))))


 [2] The *ycmd* github repository and my Emacs client.
 [3] Sorry, I couldn't resist the Star Wars reference.
 [4] We'll filter the strings later based on context.
 [5] This puts your buffer in major mode "fundamental" and minor mode "company".

### Setting up a mac

Plugin, turn on, update, allow an hour!

Ensure you do not accept the default user details or your admin user will be timpizey not timp.

Install homebrew from http://brew.sh/. Ruby is installed already. This process will install devtools.

Install chrome, font size is under Web Content.

The System Font cannot be altered! The System Font is used by all native Apple applications such as iPhoto and iStore. This is a little annoying (EN_US tr: infuriating and probably illegal). For more general, well written, unix applications the fonts can be altered one by one.

### Really useful Xcode plugins

I'm a happy Xcode user, mainly using it for C++ programming. It's a relatively nice IDE (except for when I need to break out the big guns and fire up Vim for heavy lifting).

There are a few plugins that make it an even nicer IDE.

This is as much a note to myself as anyone else.

Backlight
One of the plugins that highlights the current cursor line. I have no idea why Xcode still doesn't do this by default.
https://github.com/limejelly/Backlight-for-XCode

Fuzzy Autocomplete
Makes autocomplete work on steroids, like the Open Quickly fuzzy matching. Nice.
https://github.com/FuzzyAutocomplete/FuzzyAutocompletePlugin

SCXcodeMiniMap
Puts a wee "mini map" beside your scrollbar. Can be useful if you write insane unnavigable source files. (Hint: aim for code that doesn't need it)
https://github.com/stefanceriu/SCXcodeMiniMap

BBUDebuggerTuckAway
Hides the debugger view as soon as you start typing into the editor. Handy. Saves a common keystroke.
https://github.com/neonichu/BBUDebuggerTuckAway

Quite keyboard shortcut for adjust font sizes. Useful as I switch between a retina display and various monitor sizes depending on where I'm working.

BlockJump
CTRL-] and [ navigate up and down by block.
https://github.com/tyeen/BlockJump

Xcode4_beginning_of_line
Command + left arrow goes to the first non whitespace character, like any sane editor should.
https://github.com/insanehunter/XCode4_beginning_of_line

XAlign
One i'm just trying out. I find this kind of alignment can help reveal code intent, although it adds extra work to maintain. So let's make the computer do the work. Command-shift-X
https://github.com/qfish/XAlign

### The super() Mystery Resolved

In the previous articles in this series [1] we uncovered a small mystery regarding how Python's super() works, and we looked at some of the underlying mechanics of how super() really works. In this article we'll see how those details work together to resolve the mystery.

## The mystery revisited

As you'll recall, the mystery we uncovered has to do with how a single use of super() seemed to invoke two separate implementations of a method in our SortedIntList example. As a reminder, our class diagram looks like this:

SimpleList defines a simplified list API, and IntList and SortedList each enforce specific constraints on the contents of the list. The class SortedIntList inherits from both IntList and SortedList and enforces the constraints of both base classes. Interestingly, though, SortedIntList has a trivial implementation:

class SortedIntList(IntList, SortedList):
pass


How does SortedIntList do what it does? From the code it seems that SortedIntList does no coordination between its base classes, and certainly the base classes don't know anything about each other. Yet somehow SortedIntList manages to invoke both implementations of add(), thereby enforcing all of the necessary constraints.

## super() with no arguments

We've already looked at method resolution order, C3 linearization, and the general behavior of super instances. The final bit of information we need in order to resolve the mystery is how super() behaves when called with no arguments. [2] Both IntList and SortedList use super() this way, in both their initializers and in add().

For instance methods such as these, calling super() with no arguments is the same as calling super() with the method's class as the first argument and self as the second. In other words, it constructs a super proxy that uses the MRO from self starting at the class implementing the method. Knowing this, it's easy to see how, in simple cases, using super() is equivalent to "calling the base class implementation". In these cases, type(self) is the same as the class implementing the method, so the method is resolved using everything in that class's MRO except the class itself. The next entry in the MRO will, of course, be the class's first base class, so simple uses of super() are equivalent to invoking a method on the first base class.

A key point to notice here is that type(self) will not always be the same as the class implementing a specific method. If you invoke super() in a method on a class with a subclass, then type(self) may well be that subclass. You can see this in a trivial example:

>>> class Base:
...     def f(self):
...         print('Type of self in Base.f() =', type(self))
...
>>> class Sub(Base):
...     pass
...
>>> Sub().f()
Type of self in Base.f() = <class '__main__.Sub'>


Understanding this point is the final key to seeing how SortedIntList works. If type(self) in a base class is not necessarily the type of the class implementing the method, then the MRO that gets used by super() is not necessarily the MRO of the class implementing the method...it may be that of the subclass. Since the entries in type(self).mro() may include entries that are not in the MRO for the implementing class, calls to super() in a base class may resolve to implementations that are not in the base class's own MRO. In other words, Python's method resolution is - as you might have guessed - extremely dynamic and depends not just on a class's base classes but its subclasses as well.

## Method resolution order to the rescue

With that in mind, let's finally see how all of the elements - MRO, no-argument super(), and multiple inheritance - coordinate to make SortedIntList work. As we've just seen, when super() is used with no arguments in an instance method, the proxy uses the MRO of self which, of course, will be that of SortedIntList in our example. So the first thing to look at is the MRO of SortedIntList itself:

>>> SortedIntList.mro()
[<class 'SortedIntList'>,
<class 'IntList'>,
<class 'SortedList'>,
<class 'SimpleList'>,
<class 'object'>]


A critical point here is that the MRO contains IntList and SortedList, meaning that both of them can contribute implementations when super() is used.

Next, let's examine the behavior of SortedIntList when we call its add() method. [3] Because IntList is the first class in the MRO which implements add(), a call to add() on a SortedIntList resolves to IntList.add():

class IntList(SimpleList):
# ...

self._validate(item)


And this is where things get interesting!

In IntList.add() there is a call to super().add(item), and because of how no-argument super() calls work, this is equivalent to super(IntList, self).add(item). Since type(self) == SortedIntList, this call to super() uses the MRO for SortedIntList and not just IntList. As a result, even though IntList doesn't really "know" anything about SortedList, it can access SortedList methods via a subclass's MRO.

In the end, the call to super().add(item) in IntList.add() takes the MRO of SortedIntList, find's IntList in that MRO, and uses everything after IntList in the MRO to resolve the method invocation. Since that MRO-tail looks like this:

[<class 'SortedList'>, <class 'SimpleList'>, <class 'object'>]


and since method resolution uses the first class in an MRO that implements a method, the call resolves to SortedList.add() which, of course, enforces the sorting constraint.

So by including both of its base classes in its MRO [4] - and because IntList and SortedList use super() in a cooperative way - SortedIntList ensures that both the sorting and type constraint are enforced.

## No more mystery

We've seen that a subclass can leverage MRO and super() to do some pretty interesting things. It can create entirely new method resolutions for its base classes, resolutions that aren't apparent in the base class definitions and are entirely dependent on runtime context.

Used properly, this can lead to some really powerful designs. Our SortedIntList example is just one instance of what can be done. At the same time, if used naively, super() can have some surprising and unexpected effects, so it pays to think deeply about the consequences of super() when you use it. For example, if you really do want to just call a specific base class implementation, you might be better off calling it directly rather than leaving the resolution open to the whims of subclass developers. It may be cliche, but it's true: with great power comes great responsibility.

For more information on this topic, you can always see the Inheritance and Subtype Polymorphism module of our Python: Beyond the Basics course on PluralSight. [5]

 [1] Part 1 and Part 2
 [2] Note that calling super() with no arguments is only supported in Python 3. Python 2 users will need to use the longer explicit form.
 [3] The same logic applies to it's __init__() which also involves calls to super().
 [4] Thanks, of course, to how C3 works.

### Method Resolution Order, C3, and Super Proxies

In the previous article in this series we looked at a seemingly simple class graph with some surprising behavior. The central mystery was how a class with two bases can seem to invoke two different method implementations with just a single invocation of super(). In order to understand how that works, we need to delve into the details of how super() works, and this involves understanding some design details of the Python language itself.

## Method Resolution Order

The first detail we need to understand is the notion of method resolution order or simply MRO. Put simply a method resolution order is the ordering of an inheritance graph for the purposes of deciding which implementation to use when a method is invoked on an object. Let's look at that definition a bit more closely.

First, we said that an MRO is an "ordering of an inheritance graph". Consider a simple diamond class structure like this:

>>> class A: pass
...
>>> class B(A): pass
...
>>> class C(A): pass
...
>>> class D(B, C): pass
...


The MRO for these classes could be, in principle, any ordering of the classes A, B, C, and D (and object, the ultimate base class of all classes in Python.) Python, of course, doesn't just pick the order randomly, and we'll cover how it picks the order in a later section. For now, let's examine the MROs for our classes using the mro() class method:

>>> A.mro()
[<class '__main__.A'>,
<class 'object'>]
>>> B.mro()
[<class '__main__.B'>,
<class '__main__.A'>,
<class 'object'>]
>>> C.mro()
[<class '__main__.C'>,
<class '__main__.A'>,
<class 'object'>]
>>> D.mro()
[<class '__main__.D'>,
<class '__main__.B'>,
<class '__main__.C'>,
<class '__main__.A'>,
<class 'object'>]


We can see that all of our classes have an MRO. But what is it used for? The second half of our definition said "for the purposes of deciding which implementation to use when a method is invoked on an object". What this means is that Python looks at a class's MRO when a method is invoked on an instance of that class. Starting at the head of the MRO, Python examines each class in order looking for the first one which implements the invoked method. That implementation is the one that gets used.

For example, let's augment our simple example with a method implemented in multiple locations:

>>> class A:
...     def foo(self):
...         print('A.foo')
...
>>> class B(A):
...     def foo(self):
...         print('B.foo')
...
>>> class C(A):
...     def foo(self):
...         print('C.foo')
...
>>> class D(B, C):
...     pass
...


What will happen if we invoke foo() on an instance of D? Remember that the MRO of D was [D, B, C, A, object]. Since the first class in that sequence to support foo() is B, we would expect to see "B.foo" printed, and indeed that is exactly what happens:

>>> D().foo()
B.foo


What if remove the implementation in B? We would expect to see "C.foo", which again is what happens:

>>> class A:
...     def foo(self):
...         print('A.foo')
...
>>> class B(A):
...     pass
...
>>> class C(A):
...     def foo(self):
...         print('C.foo')
...
>>> class D(B, C):
...     pass
...
>>> D().foo()
C.foo


To reiterate, method resolution order is nothing more than some ordering of the inheritance graph that Python uses to find method implementations. It's a relatively simple concept, but it's one that many developers understand only intuitively and partially. But how does Python calculate an MRO? We hinted earlier – and you probably suspected – that it's not just any random ordering, and in the next section we'll look at precisely how Python does this.

## C3 superclass linearization

The short answer to the question of how Python determines MRO is "C3 superclass linearization", or simply C3. C3 is an algorithm initially developed for the Dylan programming language [1], and it has since been adopted by several prominent programming languages including Perl, Parrot, and of course Python. [2] We won't go into great detail on how C3 works, though there is plenty of information on the web that can tell you everything you need to know. [3]

What's important to know about C3 is that it guarantees three important features:

1. Subclasses appear before base classes
2. Base class declaration order is preserved
3. For all classes in an inheritance graph, the relative orderings guaranteed by 1 and 2 are preserved at all points in the graph.

In other words, by rule 1, you will never see an MRO where a class is preceded by one of its base classes. If you have this:

>>> class Foo(Fred, Jim, Shiela):
...     pass
...


you will never see an MRO where Foo comes after Fred, Jim, or Shiela. This, again, is because Fred, Jim, and Shiela are all base classes of Foo, and C3 puts base classes after subclasses.

Likewise, by rule 2, you will never see an MRO where the base classes specified to the class keyword are in a different relative order than that definition. Given the same code above, this means that you will never see and MRO with Fred after either Jim or Shiela. Nor will you see an MRO with Jim after Shiela. This is because the base class declaration order is preserved by C3.

The third constraint guaranteed by C3 simply means that the relative orderings determined by one class in an inheritance graph – i.e. the ordering constraints based on one class's base class declarations – will not be violated in any MRO for any class in that graph.

### C3 limits your inheritance options

One interesting side-effect of the use of C3 is that not all inheritance graphs are legal. It's possible to construct inheritance graphs which make it impossible to meet all of the constraints of C3. When this happens, Python raises an exception and prevents the creation of the invalid class:

>>> class A:
...     pass
...
>>> class B(A):
...     pass
...
>>> class C(A):
...     pass
...
>>> class D(B, A, C):
...     pass
...
Traceback (most recent call last):
File "<input>", line 1, in <module>
TypeError: Cannot create a consistent method resolution
order (MRO) for bases A, C


In this case, we've asked for D to inherit from B, A, and C, in that order. Unfortunately, C3 wants to enforce two incompatible constraints in this case:

1. It wants to put C before A because A is a base class of C
2. It wants to put A before C because of D's base class ordering

Since these are obviously mutually exclusive states, C3 rejects the inheritance graph and Python raises a TypeError.

That's about it, really. These rules provide a consistent, predictable basis for calculating MROs. Understanding C3, or even just knowing that it exists, is perhaps not important for day-to-day Python development, but it's an interesting tidbit for those interested in the details of language design.

## Super proxies

The third detail we need to understand in order to resolve our mystery is the notion of a "super proxy". When you invoke super() in Python [4], what actually happens is that you construct an object of type super. In other words, super is a class, not a keyword or some other construct. You can see this in a REPL:

>>> s = super(C)
>>> type(s)
<class 'super'>
>>> dir(s)
['__class__', '__delattr__', '__dir__',
'__doc__', '__eq__', '__format__', '__ge__',
'__get__', '__getattribute__', '__gt__',
'__hash__', '__init__', '__le__', '__lt__',
'__ne__', '__new__', '__reduce__',
'__reduce_ex__', '__repr__', '__self__',
'__self_class__', '__setattr__', '__sizeof__',
'__str__', '__subclasshook__', '__thisclass__']


In most cases, super objects have two important pieces of information: an MRO and a class in that MRO. [5] When you use an invocation like this:

super(a_type, obj)


then the MRO is that of the type of obj, and the class within that MRO is a_type. [6]

Likewise, when you use an invocation like this:

super(type1, type2)


the MRO is that of type2 and the class within that MRO is type1. [7]

Given that, what exactly does super() do? It's hard to put it in a succinct, pithy, or memorable form, but here's my best attempt so far. Given a method resolution order and a class C in that MRO, super() gives you an object which resolves methods using only the part of the MRO which comes after C.

In other words, rather than resolving method invocation using the full MRO like normal, super uses only the tail of an MRO. In all other ways, though, method resolution is occurring exactly as it normally would.

For example, suppose I have an MRO like this:

[A, B, C, D, E, object]


and further suppose that I have a super object using this MRO and the class C in this MRO. In that case, the super instance would only resolve to methods implemented in D, E, or object (in that order.) In other words, a call like this:

super(C, A).foo()


would only resolve to an implementation of foo() in D or E. [8]

### Why the name super-proxy

You might wonder why we've been using the name super-proxy when discussing super instances. The reason is that instances of super are designed to respond to any method name, resolving the actual method implementation based on their MRO and class configuration. In this way, super instances act as proxies for all objects. They simply pass arguments through to an underlying implementation.

## The mystery is almost resolved!

We now know everything we need to know to resolve the mystery described in the first article in this series. You can (and probably should) see if you can figure it out for yourself at this point. By applying the concepts we discussed in this article - method resolution order, C3, and super proxies - you should be able to see how SortedIntList is able to enforce the constraints of IntList and SortedList even though it only makes a single call to super().

If you'd rather wait, though, the third article in this series will lay it all out for you. Stay tuned!

 [2] Presumably starting with the letter "P" is not actually a requirement for using C3 in a language.
 [3] Python's introduction of C3 in version 2.3 includes a great description. You can also track down the original research describing C3.
 [4] With zero or more arguments. I'm using zero here to keep things simple.
 [5] In the case of an unbound super object you don't have the MRO, but that's a detail we can ignore for this article.
 [6] Remember that this form of super() requires that isinstance(obj, a_type) be true.
 [7] Remember that this form of super() requires that issubclass(type2, type1) be true.
 [8] Since object does not (yet...though I'm working on a PEP) implement foo().

### How to mount the Nexus 4 storage SD card on Linux systems

Taken from How to mount the Nexus 4 storage SD card on Linux systems and comments there.

Reproduced here so that I can find it again!

### Enable Developer Mode

Settings >>‘about phone’ menu and after that you should tap seven times on ‘Build Number’.

Now, from the Developer Options menu enable USB Debugging.

sudo apt-get install mtp-tools mtpfssudo gedit /etc/udev/rules.d/51-android.rules

Note not smart quotes as in the article

#LG – Nexus 4SUBSYSTEM=="usb", ATTR{idVendor}=="1004?, MODE="0666?
sudo chmod +x /etc/udev/rules.d/51-android.rules sudo service udev restartsudo mkdir /media/nexus4sudo chmod 755 /media/nexus4

Next, connect your Google Nexus 4 to your Ubuntu computer using the USB cable. The MTP option has to be enabled.

sudo mtpfs -o allow_other /media/nexus4

To unmount:

sudo umount /media/nexus4

### Writing: Nothing is Set in Stone

My latest Becoming a Better Programmer column is published in the July issue of CVu magazine (26.3). It called Nothing is Set in Stone. It talks about the soft nature of software, and how to make fearless changes.

### Writing: Becoming a Better Programmer

I am delighted to announce that I have signed a contract to publish my latest book, Becoming a Better Programmer with the excellent folks at O'Reilly.

You can find out more about the book from it's catalogue page at http://shop.oreilly.com/product/0636920033929.do.

We have now made an early access version available with a number of the chapters. It's already looking excellent, and I can't wait to get the final version out.

### Remote debugging python in Visual Studio

Suppose you have a script you want to run on linux and you only know how to drive the Visual Studio debugger. By installing an add-in for Visual Studio locally, installing the python tools for Visual Studio debugging on the remote machine, e.g. with pip install ptvsd==2.0.0pr1 and adding a (minimum of) a couple of lines to your script you can debug in Visual Studio even if the remote machine is running linux.
The additional lines are highlighted in the following script:

#!/usr/bin/python

"""
You will need to insert both these in your script
The remote box requires the ptvsd package (otherwise the import fails)
"""
import ptvsd
ptvsd.enable_attach(secret = 'joshua')
#use None instead of joshua but that is not secure
#The secret can be any string - but this is not properly secure

def say_it(it):
"""
This inserts a breakpoint
but you can add new breakpoints in Visual Studio
"""
ptvsd.break_into_debugger()
print(it)

if __name__ == "__main__":
#pause this script til we attach to it
ptvsd.wait_for_attach()
say_it("Hello world")

See https://pytools.codeplex.com/wikipage?title=Remote%20Debugging%20for%20Windows%2C%20Linux%20and%20OS%20X for more details and be wary of line ending in VS which may be inappropriate for linux.

Install the ptvs from the relevant msi for your version of Visual Studio.

Start the script on the linux box:
\$python VSPyNoodle.py

It will hang, since it has a wait_for_attach call in main.
ctrl-Z will stop it on the remote box if something goes wrong.

Select "Attach to process" in the Debug menu on Visual Studio
Change the "Transport" to "Python remote debugging (unsecured)"

Add the secret (joshua in this script) @ hostname to Qualifier
e.g. joshua@hostname

Hit "Refresh"

It should find the process running on the linux box and add the port it uses to the Qualifier
Select your process in the list box and hit "Attach"
then debug as you are used to in VS.

If it complains about stack frames and not being able to see the code you may need to make a VS project from a local version of the code. having made sure it exactly matches the remote code.

### 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.