Checking if 4 points make a square

Question

Following from the solution from this post here. It seems that using the points (1,0), (-1,0), (0,1), and (0,-1) the solution fails when it should return that these points indeed form a square.

Perhaps there is something wrong with my implementation. Here is my code:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

    class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

            double x1 = p1[0], x2 = p2[0], x3 = p3[0], x4 = p4[0];
            double y1 = p1[1], y2 = p2[1] , y3 = p3[1], y4 = p4[1];

            double cx = (x1+x2+x3+x4)/4;
            double cy = (y1+y2+y3+y4)/4;

            double a1 = (cx - x1), a2 = (cy - y1);
            double b1 = (cx - x2), b2 = (cy - y2);
            double c1 = (cx - x3), c2 = (cy - y3);
            double d1 = (cx - x4), d2 = (cy - y4);

            double dd1 = a1*a1 + a2*a2;
            double dd2 = b1*b1 + b2*b2;
            double dd3 = c1*c1 + c2*c2;
            double dd4 = d1*d1 + d2*d2;
            double epsilon = 0.00001;

            return abs(dd1 - dd2) < epsilon && abs(dd1 - dd3) < epsilon && abs(dd1 - dd4) < epsilon;
    }
};



int main() {

    vector<int> p1, p2, p3, p4;
    p1.push_back(1);
    p1.push_back(0);
    p2.push_back(-1);
    p2.push_back(0);
    p3.push_back(0);
    p3.push_back(1);
    p4.push_back(0);
    p4.push_back(-1);

    Solution m;
    bool x;
    x = m.validSquare(p1,p2,p3,p4);
    if(x == 1) {
        cout << "Points form a square" << endl;
    }
    else {
        cout << "Points do not form a square" << endl;
    }

    return 0;
}

The solution in the link is definitely correct but for some reason for these four points I do not get an accurate return. If anyone has any suggestions please let me know.

Update:

Following suggestions from users. I have changed a few lines. Using the points (0,0), (5,0), (5,4), and (0,4) should not return that these points can make a square. Unfortunately, my updated code still returns that these points are a square so I am not sure what the problem is.

Here is my code:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    bool isFloatEqual(double a, double b) {
        double epsilon = 0.001;
        return abs(a - b) < epsilon;
    }
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

            double x1 = p1[0], x2 = p2[0], x3 = p3[0], x4 = p4[0];
            double y1 = p1[1], y2 = p2[1] , y3 = p3[1], y4 = p4[1];

            double cx = (x1+x2+x3+x4)/4;
            double cy = (y1+y2+y3+y4)/4;

            double a1 = (cx - x1), a2 = (cy - y1);
            double b1 = (cx - x2), b2 = (cy - y2);
            double c1 = (cx - x3), c2 = (cy - y3);
            double d1 = (cx - x4), d2 = (cy - y4);

            double dd1 = a1*a1 + a2*a2;
            double dd2 = b1*b1 + b2*b2;
            double dd3 = c1*c1 + c2*c2;
            double dd4 = d1*d1 + d2*d2;

            return isFloatEqual(dd1,dd2) && isFloatEqual(dd1, dd3) &&isFloatEqual(dd1, dd4);

    }
};



int main() {

    vector<int> p1, p2, p3, p4;
    p1.push_back(0);
    p1.push_back(0);
    p2.push_back(5);
    p2.push_back(0);
    p3.push_back(5);
    p3.push_back(4);
    p4.push_back(0);
    p4.push_back(4);

    Solution m;
    bool x;
    x = m.validSquare(p1,p2,p3,p4);
    if(x == 1) {
        cout << "Points form a square" << endl;
    }
    else {
        cout << "Points do not form a square" << endl;
    }

    return 0;
}

`dd1 == dd2` with floating points is concerning. If you are comparing floats for equality, you are almost always doing something wrong. — Justin, Dec 22 '17 at 22:02
@Justin is right, anything based on floats is going to give you trouble and in any case won't give you an exact answer. Your solution is also overkill in terms of operations; if `(0,0)` and `(2,0)` are part of a square then the other two points must be either `(1,1) & (1,-1)` or `(0,2) & (2,2)` or `(0,-2) & (2, -2)` — n.caillou, Dec 22 '17 at 22:10
using abs(a - b) < 1E-6 for floating points a and b still does not seem to work. — Wolfy, Dec 22 '17 at 22:29
@Wolfy -- Why did you change the original code in the post? I suggest writing a function instead of writing that conditional statement "inline" like that. For example: `return isFloatEqual(dd1, dd2) && isFloatEqual(dd1, dd3) && isFloatEqual(dd1, dd4);`, and write the `isFloatEqual()` function separately, returning true or false. — PaulMcKenzie, Dec 22 '17 at 22:34
@PaulMcKenzie I changed it bases on the suggested comments. I can make that function you suggested how ever I dont think it will work but I will give it a try. — Wolfy, Dec 22 '17 at 22:35
@Wolfy I suggested writing the function so that 1) Any bugs become clear, 2) You can tailor the function with an optional third parameter denoting the epsilon value, and 3) You can reuse it for other apps that may want to test for equal floating point values. Three birds with one stone. — PaulMcKenzie, Dec 22 '17 at 22:38
@PaulMcKenzie Thank you for your suggestion I made an update to the post. — Wolfy, Dec 22 '17 at 22:40
@Wolfy -- Check whether those values are correct and whether your epsilon is small enough. Do this with pencil and paper first, and see where the program diverges from what you have done on paper. — PaulMcKenzie, Dec 22 '17 at 22:41

score 1 · Accepted Answer · answered Dec 22 '17 at 21:59

1

You have y3 = p3[2] -- is that supposed to be y3 = p3[1]? This was easy to find in c#, BTW ;)

answered Dec 22 '17 at 21:59

BlueMonkMN

25,079
9
80
146

It would also have been easier to find with `p3.at(2)` instead of `[]`. – melpomene Dec 22 '17 at 22:01
My bad nice catch – Wolfy Dec 22 '17 at 22:02
1

or with point class instead of vector of length 2 – RiaD Dec 22 '17 at 22:04
could you see my updated code, still does not seem to work correctly – Wolfy Dec 22 '17 at 22:30
@Wolfy Your updated code appears to represent a rectangle, not a square. – BlueMonkMN Dec 23 '17 at 01:40

Checking if 4 points make a square

1 Answers1