Sorting a PVector array by slopes with the Comparator interface

Programming Questions

dimiro

Sorting a PVector array by slopes with the Comparator interface

in Programming Questions • 1 year ago

hi,

i have a PVector array and i want to find collinear points by using the Comparator interface. In detail, i want to find their slopes and then sort the array by their slopes

i can sort the array by its x or y values but i cannot sort it by a relationship between point A and Point B. I have a class that uses a PVector internally

public class P {
private PVector point;
public final Comparator <P>BY_SLOPE_ORDER=new BySlope();
PApplet pa;
private float x,y;
public P(){
point=new PVector();
}
public P(PApplet pa,PVector p){
this.pa=pa;
this.x=p.get().x/60+this.pa.getWidth()/4;
this.y=p.get().y/60;
point=new PVector(this.x,this.y);
}
public float getX(){
return point.x;
}
public float getY(){
return point.y;
}
public double slopeTo(P that){
double a=1;
double pos=(a-a)/a;//horizontal lines
double neg=(a-a)/-a;//vertical lines
double y=this.getY()-that.getY();
double x=this.getX()-that.getX();
slope=y/x;
if (y==0)
slope=pos;
if (x==0)
slope=Double.POSITIVE_INFINITY;
if (y==0 && x==0)
slope=Double.NEGATIVE_INFINITY;
return slope;
}
//to double check afterwards
public boolean collinear( P b, P c){
return (this.getY()-b.getY())*(this.getX()-c.getX())==(this.getY()-c.getY())*(this.getX()-b.getX());
}
private class BySlope implements Comparator<P>{
@Override
public int compare(P o1, P o2) {
if ((P.this.slopeTo(o1)==P.this.slopeTo(o2)))
return 1;
return 0;
}
}// BySlope class
}

public class Xtest extends PApplet{
P [] points;
public void setup(){
size(800,600);
String [][] temp=myImports.loadCSV("/home/dr/Downloads/points/xx.csv", " ");
int [] data=new int [myImports.csv.length];
points=new P[data.length];
for (int i=0; i<data.length; i++){
points[i]=new P(this,new PVector(Float.parseFloat(temp[i][0]),Float.parseFloat(temp[i][1])));
}
for (int i=0; i<points.length-1; i++){
System.out.println(points[i].getX()+" "+points[i].getY());
}
Arrays.sort(points,points[0].BY_SLOPE_ORDER);
System.out.println("---------------------------AFTER SORT---------------------");
//print again

as i said the array gets correctly sorted if change the compare method to

private class BySlope implements Comparator<P>{
@Override
public int compare(P o1, P o2) {
if (o1.getX() > o2.getX())
return 1;
return 0;
}
}// BySlope

but i cannot find what i am doing wrong when i need to sort the array according to a relationship among these objects...

any ideas?

Replies(1)

PhiLho

Re: Sorting a PVector array by slopes with the Comparator interface

1 year ago

The root of the problem is that you use equality on double variables.
That's a practice tools like Findbugs warns against...
Why? Because, among other things, of floating point errors, that easily cumulate. So 3.000001 isn't equals to 3.000002, even if mathematically, you should have the same result from different inputs...
The most used workaround to this problem is to check on an epsilon (very small) value:

private class BySlope implements Comparator<P>{
@Override
public int compare(P o1, P o2) {
double s1 = P.this.slopeTo(o1);
double s2 = P.this.slopeTo(o2);
if (Math.abs(s1 - s2) < EPSILON)
return 1;
return 0;
}
}// BySlope class

where you can define EPSILON to some value OK for your purposes, like 0.00001 or lower, or higher.