In 2D plane, I have a rectangle defined by 4 vertices, A, B, C and D. I now wish to find the integer points (coordinates are integer) that fall into rectangle ABCD.
Before asking, what I did is extremely expensive in computation. Briefly, I was enumerating all the integer points and checked whether that point was in the rectangle or not. I found that it was too brutal to be used in my project, as I have many many point.
How should this be done elegantly?
UPDATE: Note that the rectangle can be of a random orientation, depending on the coordinates of the four points. Assuming nicely-placed is kinda cheating.
You can map the 4 vertices on the coordinate axis. Suppose the A(x1, y1),B(x2, y1), C(x1, y2),D(x2, y2) and x1 <= x2 && y1 <= y2, if and only if x1<= x <=x2 and y1 <= y <= y2, the point p(x,y) falls into rectangle ABCD.
Find integer points within a rectangle in Python?