Find number of rectangles from a given set of coordinates

How can I find if the following coordinates form a rectangle

Check whether the difference vectors are orthogonal, i.e. have dot product zero.

This does not check whether these coordinates are included in your list. It also does not check whether the rectangle is aligned with the coordinate axes, which would be a far simpler problem.

If you want to find all rectangles in your input, you could do the above check for all quadruples. If that is inacceptable for performance reasons, then you should update your question, indicating what kind of problem size and performance constrainst you are facing.

To check if 4 points form a rectangle:

1. for every two points calculate the distance. store all in array of floats.
2. sort the array.

you will have a[0] = a[1], a[2] = a[3], a[4] = a[5]

Separate your points in lists of 'y' coordinate, grouped by 'x' coordinate. In your case you would have two sorted lists:

3: [0,4,6,8,10]
6: [0,4,8,10]

Doing the intersection of both lists you get: [0,4,8,10]

Any two of those would form a rectangle:

[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...

This solution only works for orthogonal rectangles, this is, with sides parallel to x,y axis.

For every pair of points, say (x1, y1) and (x2, y2) consider it to be the diagonal of some rectangle. If there exist points (x1, y2) and (x2, y1) in the initial set then we have found our rectangle. It should be noted that there will exist 2 diagonals which will represent the same rectangle so we divide the final answer by 2.

This will work only for rectangles parallel to x-axis or y-axis.

PseudoCode C++:

answer = 0;
set<pair<int, int>> points;

for(auto i=points.begin(); i!=std::prev(points.end()); i++)
{
    for(auto j=i+1; j!=points.end(); j++)
    {
        pair<int, int> p1 = *i;
        pair<int, int> p2 = *j;

        if(p1.first == p2.first || p1.second == p2.second)
            continue;

        pair<int, int> p3 = make_pair(p1.first, p2.second);
        pair<int, int> p4 = make_pair(p2.first, p1.second);

        if(points.find(p3) != points.end() && points.find(p4) != points.end())
            ++answer;
    }
}

return answer/2;