understand a pseudo angle implementation

Question

I'm trying to understand a go library for Delaunay triangulation and found out this function to calculate the pseudo angle

Here is the implementation of the psuedo angle

    func pseudoAngle(dx, dy float64) float64 {
        p := dx / (math.Abs(dx) + math.Abs(dy))
        if dy > 0 {
            p = (3 - p) / 4
        } else {
            p = (1 + p) / 4
        }
        return math.Max(0, math.Min(1-eps, p))
    }

Here is were it have been used :

func (t *triangulator) hashKey(point r3.Point) int {
d := point.Sub(t.center)
return int(pseudoAngle(d[0], d[1]) * float64(len(t.hash)))

}

Do you have any idea of where this implementation is coming from mathematically ?

score 2 · Accepted Answer · answered Dec 27 '20 at 18:17

The "pseudo-angle" this function defines runs from 0 to 1 counterclockwise around the circle, with 0 at the negative x-axis, and each 25% of the range mapping to one quadrant (so 0.25 at the negative y-axis, 0.5 at the positive x-axis, etc).

First, the expression dx / (math.Abs(dx) + math.Abs(dy)), can be seen as normalizing the vector in the 1-norm or taxicab norm as opposed to the usual Euclidean norm. In other words, it's projecting the vector onto the unit diamond:

After that, it looks at the sign of y and remaps x accordingly. For the lower half of the diamond (negative y), it maps x linearly from [−1, 1] to [0, 0.5]. For the top half it maps x from [1, –1] to [0.5, 1] (reversing the direction of the mapping this time). So, as you start from the point (−1, 0) and go counterclockwise around the diamond, the pseudo-angle result will increase from 0 to 1.

It is probably used because the system wants to sort vectors by their angle (or in this case, incorporate the angle in a hash apparently), but it doesn't need the actual Euclidean angle which would require an expensive atan2 function to calculate. It just needs something monotonically related to the angle but cheap to calculate, and this pseudo-angle fits the bill.

any idea on how i could generalize it to 3d and keep the same logic ? — Tawfik, Dec 29 '20 at 10:13
@Tawfik Like for angles within an arbitrary plane in 3D? Or you want something like spherical coordinates, with two pseudo-angles? — Nathan Reed, Dec 30 '20 at 18:23
yes , exactly . how would i run the tests over y and z after applying the taxicab norm ? — Tawfik, Dec 30 '20 at 23:35

understand a pseudo angle implementation

1 Answers1