4

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.

  • Can the rectangle be under an angle, e.g., 45 degrees? –  Oct 16 '13 at 10:20
  • @Evert Yes. Any orientation. Unknown. –  Oct 16 '13 at 10:21
  • 1
    You might be better off asking at http://math.stackexchange.com/ . Your actual problem has little to do (directly) with programming. –  Oct 16 '13 at 10:22
  • @Evert So I tagged the general "algorithm" tag. Plus, I think it is programming-related, as some of the Python specific function may help solve this problem elegantly. –  Oct 16 '13 at 10:24
  • @mavErick start by reading the entry on 'Range Search' in the hitchhiker's guide to algorithms (Steven Skiena's *Algorithm Design Manual*) – Colonel Panic Oct 16 '13 at 10:33
  • Possible duplicate of [Finding whether a point lies inside a rectangle or not](http://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not) – Shashank Oct 16 '13 at 10:43
  • @ShashankGupta Finding whether a point lies inside a rectangle or not is expensive. That is exactly why I bring this question up. –  Oct 16 '13 at 10:46
  • "Briefly, I was enumerating all the integer points and checked whether that point was in the rectangle or not." What bounds did you use? Obviously not -infinity..infinity. – mbeckish Oct 16 '13 at 13:02
  • Just so you know, a four sided shape that does not have 90 degree angles is not called a rectangle. The general term is quadrilateral. – jcfollower Oct 16 '13 at 13:06

2 Answers2

3

Your rectangle shall be bounded by four lines. Say you have the following rectangle

      A
      /\
     /  \
   B \   \ 
      \  /C
       \/
        D

Now draw 2 horizontal lines, one passing through B, the other passing through C. This divides the rectangle in 3 regions.

      A
      /\
     /__\P
   B \___\ 
     Q\  /C
       \/
        D

All the three regions are defined by 2 different sets of lines.

Top: AB to AP.
Middle: BQ to PC.
Bottom: QD to CD.

For each of these regions, Iterate for integer values of x and y that satisfy the boundary line conditions. For example if the points A, B, D and C are (0,10.5), (-10.5, 0), (0, -10.5) and (10.5, 0), a rotated square,
There shall be only 1 horizontal line (the X-axis).

For Top region, the loop can be something like the following (you can modify it for python):

for ( int y = 10; y >= 0; y-- )
  for ( int x = int(y-10.5); x <= int(10.5-y); x++ ) // the int an be changed to floor or ceiling.
    print( x, y );

Order of Complexity: O(N) where N is the number of integer points.

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
0

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.

Kevin
  • 97
  • 2