Using Line2D in java with hashmaps

Question

I have a set of N points and I want to find the maximum number of points that lie in a single line.

I created Line2D objects with each pair of points. Obviously some of the Line2D objects will have same slope and intercept to make the points collinear. Now I want to create a kind of Hashtable to store a counter for the lines with same slope and intercept.

        int x1 = 1;
        int y1 = 1;
        int x2 = 2;
        int y2 = 2;
        int x3 = 3;
        int y3 = 3;


        Line2D line1 = new Line2D.Double(x1, y1, x2, y2);
        Line2D line2 = new Line2D.Double(x2, y2, x3, y3);


        hashMap.put(line1, 1);

Obviously, if I put line2 in the hashMap, it will go to a different one. How can I do it such that since both the lines are same, the count is incremented by 1?

Don't use a "slope", this will not work properly with vertical lines. In any case, concerning the actual intention, this seems to be the same as http://stackoverflow.com/questions/25342885/finding-the-maximum-number-of-points-that-lie-on-the-same-straight-line-in-a-2d — Marco13, Sep 03 '14 at 08:55

Rod_Algonquin · Answer 1 · 2014-09-03T03:33:14.887

0

You can use a String key and append each of the coordinates/points to the String so by the time you put the same coordinate it wont put it to a separate location in the HashMap.

sample:

Line2D line1 = new Line2D.Double(x1, y1, x2, y2);
HashMap<String, Integer> hashMap = new HashMap<>();
String keyToGetOrPut = line1.getP1().getX() + "" + line1.getP1().getY() + "" + line1.getP2().getX() + "" + line1.getP2().getY();
if(hashMap.get(keyToGetOrPut) != null){
    hashMap.put(keyToGetOrPut, hashMap.get(keyToGet)+1); //increment by 1 if points is already in the HashMap
} else {
    hashMap.put(keyToGetOrPut, 1); //put a new record to the HashMap
}

edited Sep 03 '14 at 03:33

answered Sep 03 '14 at 03:16

Rod_Algonquin

26,074
6
52
63

Shouldn't the `keyToGet` String have separation between the values? For example, `line1.getP1().getX() + " " + line1.getP1().getY()` or `line1.getP1().getX() + "-" + line1.getP1().getY()` – But I'm Not A Wrapper Class Sep 03 '14 at 03:18
@CyberneticTwerkGuruOrc no need, it is only used as unique keys and adding space or dash doesnt change anything. – Rod_Algonquin Sep 03 '14 at 03:20
Say you have `line1(1.23, 4.5, 6.7, 8.9)` and `line2(1.2, 34.5, 6.7, 8.9)`, wouldn't those produce the same value (although they are two different lines)? – But I'm Not A Wrapper Class Sep 03 '14 at 03:23
@CyberneticTwerkGuruOrc they wont produce the same values. that `getX()` and `getY()` will return double not int. – Rod_Algonquin Sep 03 '14 at 03:24

score 0 · Answer 2 · answered Sep 03 '14 at 03:20

0

You could create a new class that holds slope and intercept values. It should have an equals method and hashcode method that allow for equivalence within a defined parameter epsilon value to allow for functional floating point equality. Then you could use this as the key to the HashMap. The Value would be an ArrayList of your Line2D or pairs of Points.

answered Sep 03 '14 at 03:20

Hovercraft Full Of Eels

283,665
25
256
373

I wonder how this "epsilon-equality" should be done. The equals method has to be transitive. But when introducing an epsilon (ignoring the hashCode for now), you might have points like A=0.4, B=0.5, C=0.6. With an epsilon of 0.1, you'll have A==B and B==C, but not A==C ... (but maybe I misunderstood something here...) – Marco13 Sep 03 '14 at 08:59

Using Line2D in java with hashmaps

2 Answers2