# # # Nim's Runtime Library # (c) Copyright 2013 Robert Persson # # See the file "copying.txt", included in this # distribution, for details about the copyright. # import math import strutils ## Basic 2d support with vectors, points, matrices and some basic utilities. ## Vectors are implemented as direction vectors, ie. when transformed with a matrix ## the translation part of matrix is ignored. ## Operators `+` , `-` , `*` , `/` , `+=` , `-=` , `*=` and `/=` are implemented for vectors and scalars. ## ## Quick start example: ## ## # Create a matrix which first rotates, then scales and at last translates ## ## var m:Matrix2d=rotate(DEG90) & scale(2.0) & move(100.0,200.0) ## ## # Create a 2d point at (100,0) and a vector (5,2) ## ## var pt:Point2d=point2d(100.0,0.0) ## ## var vec:Vector2d=vector2d(5.0,2.0) ## ## ## pt &= m # transforms pt in place ## ## var pt2:Point2d=pt & m #concatenates pt with m and returns a new point ## ## var vec2:Vector2d=vec & m #concatenates vec with m and returns a new vector const DEG360* = PI * 2.0 ## 360 degrees in radians. DEG270* = PI * 1.5 ## 270 degrees in radians. DEG180* = PI ## 180 degrees in radians. DEG90* = PI / 2.0 ## 90 degrees in radians. DEG60* = PI / 3.0 ## 60 degrees in radians. DEG45* = PI / 4.0 ## 45 degrees in radians. DEG30* = PI / 6.0 ## 30 degrees in radians. DEG15* = PI / 12.0 ## 15 degrees in radians. RAD2DEGCONST = 180.0 / PI ## used internally by DegToRad and RadToDeg type Matrix2d* = object ## Implements a row major 2d matrix, which means ## transformations are applied the order they are concatenated. ## The rightmost column of the 3x3 matrix is left out since normally ## not used for geometric transformations in 2d. ax*,ay*,bx*,by*,tx*,ty*:float Point2d* = object ## Implements a non-homogeneous 2d point stored as ## an `x` coordinate and an `y` coordinate. x*,y*:float Vector2d* = object ## Implements a 2d **direction vector** stored as ## an `x` coordinate and an `y` coordinate. Direction vector means, ## that when transforming a vector with a matrix, the translational ## part of the matrix is ignored. x*,y*:float {.deprecated: [TMatrix2d: Matrix2d, TPoint2d: Point2d, TVector2d: Vector2d].} # Some forward declarations... proc matrix2d*(ax,ay,bx,by,tx,ty:float):Matrix2d {.noInit.} ## Creates a new matrix. ## `ax`,`ay` is the local x axis ## `bx`,`by` is the local y axis ## `tx`,`ty` is the translation proc vector2d*(x,y:float):Vector2d {.noInit,inline.} ## Returns a new vector (`x`,`y`) proc point2d*(x,y:float):Point2d {.noInit,inline.} ## Returns a new point (`x`,`y`) let IDMATRIX*:Matrix2d=matrix2d(1.0,0.0,0.0,1.0,0.0,0.0) ## Quick access to an identity matrix ORIGO*:Point2d=point2d(0.0,0.0) ## Quick acces to point (0,0) XAXIS*:Vector2d=vector2d(1.0,0.0) ## Quick acces to an 2d x-axis unit vector YAXIS*:Vector2d=vector2d(0.0,1.0) ## Quick acces to an 2d y-axis unit vector # *************************************** # Private utils # *************************************** proc rtos(val:float):string= return formatFloat(val,ffDefault,0) proc safeArccos(v:float):float= ## assumes v is in range 0.0-1.0, but clamps ## the value to avoid out of domain errors ## due to rounding issues return arccos(clamp(v,-1.0,1.0)) template makeBinOpVector(s:expr)= ## implements binary operators + , - , * and / for vectors proc s*(a,b:Vector2d):Vector2d {.inline,noInit.} = vector2d(s(a.x,b.x),s(a.y,b.y)) proc s*(a:Vector2d,b:float):Vector2d {.inline,noInit.} = vector2d(s(a.x,b),s(a.y,b)) proc s*(a:float,b:Vector2d):Vector2d {.inline,noInit.} = vector2d(s(a,b.x),s(a,b.y)) template makeBinOpAssignVector(s:expr)= ## implements inplace binary operators += , -= , /= and *= for vectors proc s*(a:var Vector2d,b:Vector2d) {.inline.} = s(a.x,b.x) ; s(a.y,b.y) proc s*(a:var Vector2d,b:float) {.inline.} = s(a.x,b) ; s(a.y,b) # *************************************** # Matrix2d implementation # *************************************** proc setElements*(t:var Matrix2d,ax,ay,bx,by,tx,ty:float) {.inline.}= ## Sets arbitrary elements in an existing matrix. t.ax=ax t.ay=ay t.bx=bx t.by=by t.tx=tx t.ty=ty proc matrix2d*(ax,ay,bx,by,tx,ty:float):Matrix2d = result.setElements(ax,ay,bx,by,tx,ty) proc `&`*(a,b:Matrix2d):Matrix2d {.noInit.} = #concatenate matrices ## Concatenates matrices returning a new matrix. # | a.AX a.AY 0 | | b.AX b.AY 0 | # | a.BX a.BY 0 | * | b.BX b.BY 0 | # | a.TX a.TY 1 | | b.TX b.TY 1 | result.setElements( a.ax * b.ax + a.ay * b.bx, a.ax * b.ay + a.ay * b.by, a.bx * b.ax + a.by * b.bx, a.bx * b.ay + a.by * b.by, a.tx * b.ax + a.ty * b.bx + b.tx, a.tx * b.ay + a.ty * b.by + b.ty) proc scale*(s:float):Matrix2d {.noInit.} = ## Returns a new scale matrix. result.setElements(s,0,0,s,0,0) proc scale*(s:float,org:Point2d):Matrix2d {.noInit.} = ## Returns a new scale matrix using, `org` as scale origin. result.setElements(s,0,0,s,org.x-s*org.x,org.y-s*org.y) proc stretch*(sx,sy:float):Matrix2d {.noInit.} = ## Returns new a stretch matrix, which is a ## scale matrix with non uniform scale in x and y. result.setElements(sx,0,0,sy,0,0) proc stretch*(sx,sy:float,org:Point2d):Matrix2d {.noInit.} = ## Returns a new stretch matrix, which is a ## scale matrix with non uniform scale in x and y. ## `org` is used as stretch origin. result.setElements(sx,0,0,sy,org.x-sx*org.x,org.y-sy*org.y) proc move*(dx,dy:float):Matrix2d {.noInit.} = ## Returns a new translation matrix. result.setElements(1,0,0,1,dx,dy) proc move*(v:Vector2d):Matrix2d {.noInit.} = ## Returns a new translation matrix from a vector. result.setElements(1,0,0,1,v.x,v.y) proc rotate*(rad:float):Matrix2d {.noInit.} = ## Returns a new rotation matrix, which ## represents a rotation by `rad` radians let s=sin(rad) c=cos(rad) result.setElements(c,s,-s,c,0,0) proc rotate*(rad:float,org:Point2d):Matrix2d {.noInit.} = ## Returns a new rotation matrix, which ## represents a rotation by `rad` radians around ## the origin `org` let s=sin(rad) c=cos(rad) result.setElements(c,s,-s,c,org.x+s*org.y-c*org.x,org.y-c*org.y-s*org.x) proc mirror*(v:Vector2d):Matrix2d {.noInit.} = ## Returns a new mirror matrix, mirroring ## around the line that passes through origo and ## has the direction of `v` let sqx=v.x*v.x sqy=v.y*v.y nd=1.0/(sqx+sqy) #used to normalize invector xy2=v.x*v.y*2.0*nd sqd=nd*(sqx-sqy) if nd==Inf or nd==NegInf: return IDMATRIX #mirroring around a zero vector is arbitrary=>just use identity result.setElements( sqd,xy2, xy2,-sqd, 0.0,0.0) proc mirror*(org:Point2d,v:Vector2d):Matrix2d {.noInit.} = ## Returns a new mirror matrix, mirroring ## around the line that passes through `org` and ## has the direction of `v` let sqx=v.x*v.x sqy=v.y*v.y nd=1.0/(sqx+sqy) #used to normalize invector xy2=v.x*v.y*2.0*nd sqd=nd*(sqx-sqy) i
parse/0: instruction: run
parse/0:   ingredient: {name: "
    default-space:address:array:location <- new location:type, 30:literal
    x:address:array:character <- new []
    y:address:array:character <- new [abcd]
    3:boolean/raw <- string-equal x:address:array:character, y:address:array:character
  ", value: 0, type: 0, properties: ["
    default-space:address:array:location <- new location:type, 30:literal
    x:address:array:character <- new []
    y:address:array:character <- new [abcd]
    3:boolean/raw <- string-equal x:address:array:character, y:address:array:character
  ": "literal-string"]}
parse/0: instruction: memory-should-contain
parse/0:   ingredient: {name: "
    3 <- 0  # "" != abcd
  ", value: 0, type: 0, properties: ["
    3 <- 0  # "" != abcd
  ": "literal-string"]}
after-brace/0: recipe string-equal-with-empty
after-brace/0: run ...
after-brace/0: memory-should-contain ...
new/0: routine allocated memory from 1000 to 101000
schedule/0: string-equal-with-empty
run/0: instruction string-equal-with-empty/0
run/0: run {name: "
    default-space:address:array:location <- new location:type, 30:literal
    x:address:array:character <- new []
    y:address:array:character <- new [abcd]
    3:boolean/raw <- string-equal x:address:array:character, y:address:array:character
  ", value: 0, type: 0, properties: ["
    default-space:address:array:location <- new location:type, 30:literal
    x:address:array:character <- new []
    y:address:array:character <- new [abcd]
    3:boolean/raw <- string-equal x:address:array:character, y:address:array:character
  ": "literal-string"]}
parse/0: instruction: new
parse/0:   ingredient: {name: "location", value: 0, type: 0, properties: ["location": "type"]}
parse/0:   ingredient: {name: "30", value: 0, type: 0, properties: ["30": "literal"]}
parse/0:   product: {name: "default-space", value: 0, type: 2-5-1, properties: ["default-space": "address":"array":"location"]}
parse/0: instruction: new
parse/0:   ingredient: {name: "", value: 0, type: 0, properties: ["": "literal-string"]}
parse/0:   product: {name: "x", value: 0, type: 2-5-4, properties: ["x": "address":"array":"character"]}
parse/0: instruction: new
parse/0:   ingredient: {name: "abcd", value: 0, type: 0, properties: ["abcd": "literal-string"]}
parse/0:   product: {name: "y", value: 0, type: 2-5-4, properties: ["y": "address":"array":"character"]}
parse/0: instruction: string-equal
parse/0:   ingredient: {name: "x", value: 0, type: 2-5-4, properties: ["x": "address":"array":"character"]}
parse/0:   ingredient: {name: "y", value: 0, type: 2-5-4, properties: ["y": "address":"array":"character"]}
parse/0:   product: {name: "3", value: 0, type: 3, properties: ["3": "boolean", "raw": ]}
new/0: location -> 1
new/0:  -> 0
name/0: assign x 1
new/0: abcd -> 0
name/0: assign y 2
after-brace/0: recipe run1001
after-brace/0: new ...
after-brace/0: new ...
after-brace/0: new ...
after-brace/0: string-equal ...
run/0: instruction run1001/0
run/0: {name: "default-space", value: 0, type: 2-5-1, properties: ["default-space": "address":"array":"location"]} <- new {name: "location", value: 1, type: 0, properties: ["location": "type"]}, {name: "30", value: 30, type: 0, properties: ["30": "literal"]}
mem/0: array size is 30
mem/0: new alloc: 1000
run/0: instruction run1001/1
run/0: {name: "x", value: 1, type: 2-5-4, properties: ["x": "address":"array":"character"]} <- new {name: "", value: 0, type: 0, properties: ["": "literal-string"]}
mem/0: storing 1031 in location 1002
run/0: instruction run1001/2
run/0: {name: "y", value: 2, type: 2-5-4, properties: ["y": "address":"array":"character"]} <- new {name: "abcd", value: 0, type: 0, properties: ["abcd": "literal-string"]}
mem/0: storing 1032 in location 1003
run/0: instruction run1001/3
run/0: {name: "3", value: 3, type: 3, properties: ["3": "boolean", "raw": ]} <- string-equal {name: "x", value: 1, type: 2-5-4, properties: ["x": "address":"array":"character"]}, {name: "y", value: 2, type: 2-5-4, properties: ["y": "address":"array":"character"]}
mem/0: location 1002 is 1031
mem/0: location 1003 is 1032
run/0: instruction string-equal/0
run/0: {name: "default-space", value: 0, type: 2-5-1, properties: ["default-space": "address":"array":"location"]} <- new {name: "location", value: 1, type: 0, properties: ["location": "type"]}, {name: "30", value: 30, type: 0, properties: ["30": "literal"]}
mem/0: array size is 30
mem/0: new alloc: 1037
run/0: instruction string-equal/1
run/0: {name: "a", value: 1, type: 2-5-4, properties: ["a": "address":"array":"character"]} <- next-ingredient 
run/0: product 0 is 1031
mem/0: storing 1031 in location 1039
run/0: instruction string-equal/2
run/0: {name: "a-len", value: 2, type: 1, properties: ["a-len": "integer"]} <- length {name: "a", value: 1, type: 2-5-4, properties: ["a": "address":"array":"character", "deref": ]}
mem/0: location 1039 is 1031
mem/0: storing 0 in location 1040
run/0: instruction string-equal/3
run/0: {name: "b", value: 3, type: 2-5-4, properties: ["b": "address":"array":"character"]} <- next-ingredient 
run/0: product 0 is 1032
mem/0: storing 1032 in location 1041
run/0: instruction string-equal/4
run/0: {name: "b-len", value: 4, type: 1, properties: ["b-len": "integer"]} <- length {name: "b", value: 3, type: 2-5-4, properties: ["b": "address":"array":"character", "deref": ]}
mem/0: location 1041 is 1032
mem/0: storing 4 in location 1042
run/0: instruction string-equal/6
run/0: trace {name: "string-equal", value: 0, type: 0, properties: ["string-equal": "literal-string"]}, {name: "comparing lengths", value: 0, type: 0, properties: ["comparing lengths": "literal-string"]}
string-equal/0: comparing lengths
run/0: instruction string-equal/7
run/0: {name: "length-equal?", value: 5, type: 3, properties: ["length-equal?": "boolean"]} <- equal {name: "a-len", value: 2, type: 1, properties: ["a-len": "integer"]}, {name: "b-len", value: 4, type: 1, properties: ["b-len": "integer"]}
run/0: ingredient 0 is a-len
mem/0: location 1040 is 0
run/0: ingredient 1 is b-len
mem/0: location 1042 is 4
run/0: product 0 is 0
mem/0: storing 0 in location 1043
run/0: instruction string-equal/8
run/0: break-if {name: "length-equal?", value: 5, type: 3, properties: ["length-equal?": "boolean"]}, {name: "", value: 1, type: , properties: ["": ]}
mem/0: location 1043 is 0
run/0: ingredient 0 is 0
run/0: jump-if fell through
run/0: instruction string-equal/9
run/0: reply {name: "0", value: 0, type: 0, properties: ["0": "literal"]}
run/0: result 0 is 0
mem/0: storing 0 in location 3
run/0: instruction string-equal-with-empty/1
run/0: memory-should-contain {name: "
    3 <- 0  # "" != abcd
  ", value: 0, type: 0, properties: ["
    3 <- 0  # "" != abcd
  ": "literal-string"]}
run/0: checking location 3
generated by cgit-pink 1.4.1-2-gfad0 (git 2.36.2.497.gbbea4dcf42) at 2025-06-30 20:17:36 +0000
y-t.ay*t.tx+p.x*t.ay-p.y*t.ax)/d p.x=newx proc `+`*(p:Point2d,v:Vector2d):Point2d {.noInit,inline.} = ## Adds a vector `v` to a point `p`, resulting ## in a new point. result.x=p.x+v.x result.y=p.y+v.y proc `+=`*(p:var Point2d,v:Vector2d) {.noInit,inline.} = ## Adds a vector `v` to a point `p` in place. p.x+=v.x p.y+=v.y proc `-`*(p:Point2d,v:Vector2d):Point2d {.noInit,inline.} = ## Subtracts a vector `v` from a point `p`, resulting ## in a new point. result.x=p.x-v.x result.y=p.y-v.y proc `-`*(p1,p2:Point2d):Vector2d {.noInit,inline.} = ## Subtracts `p2`from `p1` resulting in a difference vector. result.x=p1.x-p2.x result.y=p1.y-p2.y proc `-=`*(p:var Point2d,v:Vector2d) {.noInit,inline.} = ## Subtracts a vector `v` from a point `p` in place. p.x-=v.x p.y-=v.y proc equals(p1,p2:Point2d,tol=1.0e-6):bool {.inline.}= ## Checks if two points approximately equals with a tolerance. return abs(p2.x-p1.x)<=tol and abs(p2.y-p1.y)<=tol proc `=~`*(p1,p2:Point2d):bool {.inline.}= ## Checks if two vectors approximately equals with a ## hardcoded tolerance 1e-6 equals(p1,p2) proc polar*(p:Point2d,ang,dist:float):Point2d {.noInit.} = ## Returns a point with a given angle and distance away from `p` result.x=p.x+cos(ang)*dist result.y=p.y+sin(ang)*dist proc rotate*(p:var Point2d,rad:float)= ## Rotates a point in place `rad` radians around origo. let c=cos(rad) s=sin(rad) newx=p.x*c-p.y*s p.y=p.y*c+p.x*s p.x=newx proc rotate*(p:var Point2d,rad:float,org:Point2d)= ## Rotates a point in place `rad` radians using `org` as ## center of rotation. let c=cos(rad) s=sin(rad) newx=(p.x - org.x) * c - (p.y - org.y) * s + org.x p.y=(p.y - org.y) * c + (p.x - org.x) * s + org.y p.x=newx proc scale*(p:var Point2d,fac:float) {.inline.}= ## Scales a point in place `fac` times with world origo as origin. p.x*=fac p.y*=fac proc scale*(p:var Point2d,fac:float,org:Point2d){.inline.}= ## Scales the point in place `fac` times with `org` as origin. p.x=(p.x - org.x) * fac + org.x p.y=(p.y - org.y) * fac + org.y proc stretch*(p:var Point2d,facx,facy:float){.inline.}= ## Scales a point in place non uniformly `facx` and `facy` times with ## world origo as origin. p.x*=facx p.y*=facy proc stretch*(p:var Point2d,facx,facy:float,org:Point2d){.inline.}= ## Scales the point in place non uniformly `facx` and `facy` times with ## `org` as origin. p.x=(p.x - org.x) * facx + org.x p.y=(p.y - org.y) * facy + org.y proc move*(p:var Point2d,dx,dy:float){.inline.}= ## Translates a point `dx`, `dy` in place. p.x+=dx p.y+=dy proc move*(p:var Point2d,v:Vector2d){.inline.}= ## Translates a point with vector `v` in place. p.x+=v.x p.y+=v.y proc sgnArea*(a,b,c:Point2d):float= ## Computes the signed area of the triangle thru points `a`,`b` and `c` ## result>0.0 for counter clockwise triangle ## result<0.0 for clockwise triangle ## This is commonly used to determinate side of a point with respect to a line. return ((b.x - c.x) * (b.y - a.y)-(b.y - c.y) * (b.x - a.x))*0.5 proc area*(a,b,c:Point2d):float= ## Computes the area of the triangle thru points `a`,`b` and `c` return abs(sgnArea(a,b,c)) proc closestPoint*(p:Point2d,pts:varargs[Point2d]):Point2d= ## Returns a point selected from `pts`, that has the closest ## euclidean distance to `p` assert(pts.len>0) # must have at least one point var bestidx=0 bestdist=p.sqrDist(pts[0]) curdist:float for idx in 1..high(pts): curdist=p.sqrDist(pts[idx]) if curdist=0.0 and ang