Compare a list of vecs against a angle

clankill3r

I have a line from the center to the mouse. That line has a certain angle. For the rest I have random points on the screen. I want to order those points in such a way that they are compared to the angle from the center to the mouse.

So 0 stays 0. 11 becomes 1, 6 becomes 2, 10 becomes 3 etc. In other words, if the line would move clockwise then they get numbered in that order.

I have no idea how to make a Comparator for that. I hope someone can help.

O yeah, if you want to run you need eclipse or IntelliJ cause Processing will give a scope problem.

import processing.core.PApplet;
import processing.core.PVector;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class CompareToAngle extends PApplet {

     public static void main(String[] args) {
         PApplet.main("CompareToAngle", args);
     }


    public void settings() {
        size(1024, 1024);

    }

    public void setup() {

    }


    public void draw() {
        background(255);

        PVector a = new PVector(width/2, height/2);
        PVector b = new PVector(mouseX, mouseY);

        line(a.x, a.y, b.x, b.y);

        // compare against this angle!!
        // compare against this angle!!
        // compare against this angle!!
        // compare against this angle!!
        // compare against this angle!!
        float angle = atan2(b.y-a.y, b.x-a.x);

        fill(0);
        text(angle, b.x, b.y);

        ArrayList<PVector> vecs = new ArrayList<PVector>();

        randomSeed(1);
        for (int i = 0; i < 15; i++ ) {
            PVector v = new PVector(random(50, width-50), random(50, height-50));
            vecs.add(v);
        }

        Collections.sort(vecs, new Comparator<PVector>() {

            @Override
            public int compare(PVector o1, PVector o2) {

                float angleO1 = atan2(b.y-o1.y, b.x-o1.x);
                float angleO2 = atan2(b.y-o2.y, b.x-o2.x);

                if (angleO1 > angleO2) {
                    if (angleO1 > angle) {
                        return 1;
                    }
                    if (angleO1 < angle) {
                        return -1;
                    }
                }
                else if (angleO1 < angleO2) {
                    if (angleO2 > angle) {
                        return 1;
                    }
                    if (angleO2 < angle) {
                        return -1;
                    }

                }

                return 0;
            }
        });

        int c = 0;
        for (PVector v : vecs) {
            ellipse(v.x, v.y, 5, 5);
            text(c++, v.x+20, v.y);
        }





    }

}

clankill3r

I found a great post here in c++ which could help but I don't really understand it.

http://stackoverflow.com/questions/7774241/sort-points-by-angle-from-given-axis

clankill3r

Ok, after some trial and error I got it working. I only return either -1 or 1 and never 0 cause I don't know where that should happen. Maybe I dig into it more later but for now who's interested in using it. Here is the code.

If you change the ? -1 : 1; to ? 1 : -1; then it's get sorted the other way around.

If someone could explain a bit more about what's happening then that is always welcome. I'm just glad it seems to work for now.

class  AngleSort2 implements Comparator<PVector> {

        PVector m_origin;
        PVector m_dreference;

        AngleSort2(PVector origin, PVector reference) {
            this.m_origin = origin;
            this.m_dreference = PVector.sub(reference, origin);
        }

        @Override
        public int compare(PVector a, PVector b) {

            PVector da = PVector.sub(a, m_origin);
            PVector db = PVector.sub(b, m_origin);
            double detb = xp(m_dreference, db);

            // nothing is less than zero degrees
            if (detb == 0 && db.x * m_dreference.x + db.y * m_dreference.y >= 0) return -1; // return false

            double deta = xp(m_dreference, da);

            // zero degrees is less than anything else
            if (deta == 0 && da.x * m_dreference.x + da.y * m_dreference.y >= 0) return 1;  // return true

            if (deta * detb >= 0) {
                // both on same side of reference, compare to each other
                return xp(da, db) > 0 ? -1 : 1;
            }

            // vectors "less than" zero degrees are actually large, near 2 pi
            return deta > 0 ? -1 : 1;
        }


        // z-coordinate of cross-product, aka determinant
        double xp(PVector a, PVector b) {
            return a.x * b.y - a.y * b.x;
        }


    }

colouredmirrorball

The xp() method calculates the cross product a x b, which has this property:

|a x b| = |a| |b| sin θ

where θ is the angle between a and b. That is, the magnitude of the cross product is equal to the product of the magnitude of the two vectors separately, and the sine of the angle between them. The cross product is defined in 3D only, this is a "simplified" 2D version. The result of the cross product of two vectors is another vector which is perpendicular to both original vectors. In this case, because we're in 2D, the resulting vector is in the z direction. Calculating the cross product is roughly analogous to calculating the determinant of a matrix, that's why the variables are called deta and detb:

| x̂   ŷ    ẑ   |
| ax  ay   az  |
| bx  by   bz  |

(where az and bz would be 0).

The magnitude actually doesn't matter here, only the sign. The sign is entirely determined by the sin θ factor. If θ is positive, sin θ is positive as well, meaning the angle between a and b is positive. If θ is negative, the angle between a and b is negative, which is exactly what you tried to determine.

clankill3r

@colouredmirrorball thanks for explaining!