Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #998

Re: inside parallelogram?

Show all headers | View raw

On Sun, 06 Nov 2011 20:49:10 +0000, James Waldby wrote:

> On Sat, 05 Nov 2011 14:40:03 -0700, lloyd wrote:
> 
>> Could someone help with the simplest way to check whether an integer
>> lattice point is inside (or on the boundary of) a parallelogram? The
>> parallelogram has corners (a,b), (i,j), (m,n) (p,q), which are sorted
>> so that b<q, b<=j<=q, b<=n<=q, a<p, i<=m. I want to check whether (x,y)
>> is in the parellogram, or on its boundary. All coordinates are
>> integers. Thanks for any hints!
> 
> I will disregard your stated point sort and instead suppose the
> parallelogram has corners C_r, going around it counterclockwise.
> 
> Suppose (i,j) and (m,n) are two consecutive points C_r and C_{r+1 mod
> 4}.  Let d = m-i, e = n-j, c = j*d - e*i, and f_r(x,y) = d*y - e*x - c.
> 
> The line through C_r and C_{r+1 mod 4} is given by f_r(x,y) = 0. (x,y)
> is in the same halfplane as the parallelogram if f_r(x,y) > 0. (x,y) is
> in or on the parallelogram if f_r(x,y) >= 0 for all r.

Note, since d, e are the same (except with reversed signs) for
opposite sides of parallelogram, you don't need to compute 
d*y - e*x as many times if you test in order f_0, f_2, f_1, f_3.
(Of course, some signs or tests need reversing to avoid recomputation.)

-- 
jiw

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

inside parallelogram? lloyd <lloyd.houghton@gmail.com> - 2011-11-05 14:40 -0700
  Re: inside parallelogram? James Waldby <not@valid.invalid> - 2011-11-06 20:49 +0000
    Re: inside parallelogram? James Waldby <not@valid.invalid> - 2011-11-06 21:02 +0000
  Re: inside parallelogram? Sjouke Burry <burry@planet.nl> - 2011-11-06 21:18 +0000
    Re: inside parallelogram? lloyd <lloyd.houghton@gmail.com> - 2011-11-06 21:37 -0800
      Re: inside parallelogram? Sjouke Burry <burry@planet.nl> - 2011-11-07 06:47 +0000

csiph-web