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

Groups > comp.programming > #997

Re: inside parallelogram?

Show all headers | View raw

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.

-- 
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