[Numpy-discussion] Robust Sorting of Points

[Nathaniel Smith]

On Sun, Oct 27, 2013 at 10:41 PM, Freddie Witherden
<freddie at witherden.org> wrote:
> On 27/10/13 21:05, Jonathan March wrote:
>> If an "almost always works" solution is good enough, then sort on the
>> distance to some fixed random point that is in the vicinity of your N
>> points.
>
> I had considered this.  Unfortunately I need a solution which really
> does always work.
>
> The only pure-Python solution I can envision -- at the moment anyway --
> is to do some cleverness with the output of np.unique to identify
> similar values and replace them with an arbitrarily chosen one.  This
> should permit the output to be passed to np.lexsort without issue.

# Warning 1: Untested code.
# Warning 2: I can't tell if this is clever or horrible.
r = np.random.RandomState(0)
while True:
    # This perturbation leaves lexical order unchanged, but will
eventually shift
    # all points away from rounding bin boundarys.
    shift = r.rand()
    if np.any(np.around(perturbed + (shift - 1e-11), decimals=10) !=
np.around(perturbed + (shift + 1e-11))):
        continue
    return np.lexsort(np.around(perturbed, decimals=10))

-n