Phrases/Geometry

Classic geometry

The following adverbs are used in further definitions.

NB.*Atnp a applies verb dyadically to neighbouring pairs (including first
NB. and last)
Atnp=:(/\) (2&) (@(, {.))

NB.*Atc a applies verb monadically to all circular permutations of a list
Atc=:("_1)(@(i.@# |."0 _ ]))

Solving triangles

Check if sides form a triangle

NB.*isT v check if given 3 segments form a triangle
isT=:[: *./ <`+/ Atc

Calculate angle from 3 sides

For three given sides calculate angle between first two using cosine theorem.
cosα=(a²+b²-c²)/(2·a·b)
It is convenient for certain applications to set angle for non-trinagles equal to 180° (c>a+b) or 0° (a>c+b || b>a+c)

NB.*af3s v angle of a triangle from 3 sides
NB. a b c → α (between a and b)
caf3s=:( +`-/@:*: % 2&([*/@,{.) ) "1
af3s=: 0:`(_2&o.)`(1p1"_)@.(+/@(_1 1&>))@caf3s

Coordinate geometry

The following cues in the name tip on a kind of parameter verb accepts:

P Points on a plain are represented as 2-vectors of (x,y) coordinates.

V When interpreted as vectors for offset or direction points are denoted with V

L Lines are represented as 3-vectors (a,b,c) of their equation ax+by+c=0.

C Circles are given as triples (x,y,r) of center coordinates and radius

Basic formulas

Line by 2 points

NB.*lnPP v line passing through 2 points
lnPP=:(-/ .* ,~ [: (,~ -)/ -~/)@,:"1

If point lies to the left of x.→y. vector then Ax+By+C will be positive, if it lies to the right it will be negative

Parallel shift line in given direction

NB. parallel shift line in given direction
lnVL=:(lnLV=:[ -/@,: _3 {. +/@:*&(2&{.))~

Parallel shift circle in given direction

ciVC=:ciCV=:+/@,:

line through a point in a given direction

NB. line through a point in a given direction
lnPV=:lnVL (,~-)/
lnVP=:lnPV~

Point of intersection of 2 lines

NB.*ptLL v point of intersection of 2 lines
ptLL=:(-@{:"1 %. 2&{."1)@,:"1

Perpendicular

NB.*lnLP v line passing through a point and perpendicular to other line
lnLP=:(,-)/@|.@}:@[ ([ , -@(+/)@:*) ]
lnPL=:lnLP~

Projection of a point to a line

NB.*ptLP v perpendicular projection of a point to a line
ptLP=:[ ptLL lnLP
ptPL=:ptLP~

Distance between 2 points

NB.*dPP v distance between 2 points
dPP=:[: +/&.:*: -

Dot product

NB.*norml v normalize line equation
norml=:% +/&.:*:@}:

NB.*dot v
dot=:+/@:*/@(,:!.1)"1

P dot Q is a dot product of vectors P and Q L dot P applies line to point. In case line is normalized this is equal to distance from point to a line.

Intersection of 2 circles

Points of intersection of 2 circles:

NB. [ and ] are circles defined as (x,y,r)
ptCC=:}:@[ +"1 {:@[ +.@r. af3s@(dPP&}: , ,&{:) (+ , -~) 12 o. [: j./ -&}:~

Points of intersection of a line and a circle

 1NB. Point of intersection of a line and a circle
 2NB. (x0 y0,:x1 y1) ← (a b c) ptLC (x y r)
 3ptLC=: 4 : 0
 4 assert. 3=#x.
 5 assert. 3=#y.
 6 'a b c'=.x.
 7 'x y r'=.y.
 8 if. a >&| b do.
 9   yy=.>1{ p. ((2*a*c*x)+(c*c)+-/*:a*x,r,y),(2*(a*b*x)+(b*c)-a*a*y),+/*:a,b
10   xx=.-a%~c+b*yy
11 elseif. 0~:b do.
12   xx=.>1{ p. ((2*b*c*y)+(c*c)+-/*:b*x,r,y),(2*(a*b*y)+(a*c)-b*b*x),+/*:a,b
13   yy=.-b%~c+a*xx
14 elseif. do.
15   assert. 0
16 end.
17 r#~*./,(=+)r=.  xx ,. yy
18)
19ptCL=:ptLC~

Coordinate algorithms

Signed area

Signed area is positive when vertices are listed counterclockwise and negative otherwise. To get area from signed area just take absolute value.

NB.*area v signed area of a polygon defined as a list of coordinates
NB. A=½Σ(y(n+1)+y(n))·(x(n+1)-x(n))
area=:[: +/ (-&{: -:@* +&{.)~ Atnp

For example:

   area 0 0,0 1,1 1,:1 0                NB. Unit square clockwise
_1
   area |.0 0,0 1,1 1,:1 0              NB. Unit square widdershins
1
   area 1 1 _1 _1*-:%:2 0,0 2,2 0,:0 2  NB. Another unit square
1
   area p2c"1] 0.64852517,.2p1*5%~i.5   NB. Unit pentagon
1

Where

p2c=: +.@(r./) NB.* p2c: convert 2-D polar to Cartesian

Perimeter of Polygon

NB.* perimeter v return perimeter of 2-D polygon given points as 2-column matrix.
perimeter=: [:+/(dPP Atnp)

Some examples to give us confidence that we're doing the right thing:

   perimeter 1 0,1 1,0 1,:0 0                 NB. Unit square
4
   cr=. 0.56437525    NB. corner radius for unit centagon: 100-sided polygon
   area centagon=. p2c"1] cr,.2p1*100%~i.100  NB. Unit centagon
1
   perimeter centagon
3.545491

This should be close to perimeter of comparable circle:

   (2*o. cr),o. *:cr                          NB. Perimeter and area of circumscribing circle
3.5460743 1.0006583

Circle through 3 points

NB.*xy3P v center of a circle passing through 3 points
xy3P=:[: (+/ % #) [: ptLL Atnp (lnPP lnLP -:@+) Atnp

The center of a circle circumscribing a triangle lies at a point of intersection of 3 central perpendiculars to the sides. This function calculates 3 pairwise points of intersection and averages the result to soften roundoff errors.

NB.*xyrf3P v center and radius of a circle passing through 3 points
xyrf3P=:(, [: (+/ % #) dPP"1)@xy3P

Average distance from a center to each of three vertices

TODO: Lines passing through a point and tangent to a circle

TODO: Lines tangent to a pair of circles

Point in Polygon

Is a point in the internal area of a polygon?

Crossing Number

{*} Auto start: File:Pointpoly.ijs (random), File:Pointpoly2.ijs (sample)

NB.*crossPnP v point in closed polygon, crossing number
NB.  bool=. points crossPnP polygon
crossPnP=: 4 : 0"2
  'X Y'=. |:x
  'x0 y0 x1 y1'=. |:2 ,/\^:(2={:@$@]) y
  p1=. ((y0<:/Y)*. y1>/Y) +. (y0>/Y)*. y1<:/Y
  p2=. (x0-/X) < (x0-x1) * (y0-/Y) % (y0 - y1)
  2|+/ p1*.p2
)

points:: N by 2 array

polygon:: M by 2 array of single closed contour, or M-1 by 4 array composite contour

Example

SQUAREV=:          0   0   , 10  0   , 10  10  ,: 0   10
SQUAREV=: SQUAREV, 2.5 2.5 , 7.5 0.1 , 7.5 7.5 ,: 2.5 7.5

ESAV=: 3 0 , 7 0 , 10 5 , 7 10 , 3 10 ,: 0 5

ESA=:        (0 1,1 2,2 3,3 4,4 5,:5 0) , .{ ESAV
SQUARE=:     (0 1,1 2,2 3,:3 0)         , .{ SQUAREV
SQUAREHOLE=: (0 1,1 2,2 3,3 0,4 5,5 6,6 7,:7 4) , .{ SQUAREV
STRANGE=:    (0 4,4 3,3 7,7 6,6 2,2 1,1 5,:5 0) , .{ SQUAREV

POINTS=: 5 5,5 8,2 2,0 0,10 10,2.5 2.5,0.01 5,2.2 7.4,0 5,10 5,:_4 10

Test

   (<POINTS) crossPnP every ESA;SQUARE;SQUAREHOLE;STRANGE
1 1 1 0 0 1 1 1 0 1 0
1 1 1 0 0 1 1 1 0 1 0
0 1 1 0 0 1 1 1 0 1 0
1 0 0 0 0 0 0 1 0 1 0

See also

• Geometry Algorithms, Dan Sunday
• Eric Haines, Point in Polygon Strategies. Eric Haines web site, Graphics Gems IV - ACM
• Point in polygon (ray casting algorithm), Rosetta Code
• Point in polygon, Wikipedia
• 2010-04 thread on JForum

Comments

This page needs better descriptions of how to represent arguments within the domain of these functions to be useful. For example

   isT 0 1,0 2,:1 2
0 1

From the description I would expect a 1 or a zero from a well formed argument, but not both.

-- Raul Miller <<DateTime(2008-09-23T19:47:29Z)>>

Oops - now I know why area did not work for me at first: I defined things in the wrong order. See my explanation here. -- Devon McCormick <<DateTime(2008-10-11T12:34:56Z)>>