CODEWITHSUNDEEP
pythonpython-3.xdrawingcoordinatescoordinate-systems
Marci
Marci

Reputation: 137

Python 3.x - counting drawing&&counting the possible squares in a coordinate system

So, for now, I have a coordinate system like:

.    .    .
.    .    .

(x=0, y=0)    (x=1, y=0)    (x=2, y=0)
(x=0, y=1)    (x=1, y=1)    (x=2, y=1)

We know that there are 3 possible rectangles to draw.

We know the coordinates of each element. (In the upper left corner its 0,0 (x,y)) (In the downer right corner its 2,1 (x,y))

We know a rectangle has 4 points, for now, its: (x, y), (x2, y), (x, y2), (x2, y2) so,

(x, y)    (x2, y)
(x, y2)   (x2, y2)

We know that a rectangle's area is bigger than 0, so x != x2 && y != y2.

We know that (in the example coordinate system) the three drawable rectangles coordinate's are:

1,
  0,0    1,0
  0,1    1,1
2,
  1,0    2,0
  1,1    2,1
3,
  0,0    2,0
  0,1    2,1

Now, rhombuses aren't in the play.

So, How can I get the solution (I want the solution to be the drawable rectangle's coordinates.) in Python? Can somebody please send me a code or instructions? I couldn't find any on the internet. Of course, it has to work with coordinate systems which has more coordinates in it.

I'm looking only for Python codes.

Upvotes: 2

Views: 947

Answers (2)

Riccardo Bucco
Riccardo Bucco

Reputation: 15364

The answer given by @Tibbles shows you how to generate the rectangles. Counting them (without generating them!!) is easy, and you just need some basic math:

rect_count = w * h * (w - 1) * (h - 1) / 4

where w is the max value of x and h is the max value of `y.

Upvotes: 0

bglbrt
bglbrt

Reputation: 2098

A very simple yet greedy way to count and output the number of rectangles in the given coordinate system is the following.

First, define a function to check if four points form a rectangle:

def is_rectangle(a, b, c, d):  
    # sort coordinates
    a, b, c, d = sorted([a, b, c, d])

    # check rectangle
    return a[0] == b[0] and c[0] == d[0] and a[1] == c[1] and b[1] == d[1]

Then, a function to count the rectangles in all possible four points combinations of your coordinate system:

def number_rectangles(coordinates):

    # output the number of rectangles
    return sum([is_rectangle(a, b, c, d) for (a, b, c, d) in itertools.combinations(coordinates, 4)])

And finally, a way to output the coordinates of those rectangles would be:

def get_rectangles(coordinates):

    # return each rectangle
    return [[a, b, c, d] for (a, b, c, d) in itertools.combinations(coordinates, 4) if is_rectangle(a, b, c, d)]

What you would get with your example is:

coordinates = [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)]

number_rectangles(coordinates)
# > 3

get_rectangles(coordinates)
# > [[(0, 0), (0, 1), (1, 0), (1, 1)],
# >  [(0, 0), (0, 2), (1, 0), (1, 2)],
# >  [(0, 1), (0, 2), (1, 1), (1, 2)]]

Upvotes: 2

Related Questions