3
$\begingroup$

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 ?


$\endgroup$

1 Answer 1

2
$\begingroup$

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:

unit ball in the 1-norm

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.