From: Christian Haselbach
Subject: Geometry Library for Common Lisp?
Date:
Message-ID: <e168ka$q3u$1@online.de>
Hello,
is there a good geometry library for cl? I am primarily looking for
something to handle 2D polygons and finding intersections of polygons or
getting the intersecting points of a line and a polygon.
While I am at it: Are there any open source GIS programs / libraries /
... in cl?
Thanky.
Regards,
Christian
Christian Haselbach <······@muon.de> wrote:
> is there a good geometry library for cl? I am primarily looking for
> something to handle 2D polygons and finding intersections of polygons or
> getting the intersecting points of a line and a polygon.
You could have a look at regions.lisp and transforms.lisp of McCLIM
(http://www.cl-user.net/asp/libs/mcclim)
Arthur
From: Christian Haselbach
Subject: Re: Geometry Library for Common Lisp?
Date:
Message-ID: <e190nk$n8s$1@online.de>
Arthur Lemmens schrieb:
> You could have a look at regions.lisp and transforms.lisp of McCLIM
> (http://www.cl-user.net/asp/libs/mcclim)
Thanks for the hint. This seems to be a bit heavyweight for my needs.
I started to write my own, which can be found below.
Comments are very welcome (I am still rather new to Lisp). Especially:
Would it be better to use vectors instead of lists to represent
(mathematical/geomatrical) vectors. If so, how can the destructuring
part be made in a way that it works with any sequence?
Regards,
Christian
;; Package for geometric calculations
;; ----------------------------------
;;
;; Resources:
;; -
http://geometryalgorithms.com/Archive/algorithm_0104/algorithm_0104B.htm
;;
(defpackage #:geom
(:use #:common-lisp))
(in-package #:geom)
(defmacro v- (&rest rest)
"Minus operator for geom. vectors."
`(mapcar #'- ,@rest))
(defmacro v+ (&rest rest)
"Plus operator for geom. vectors."
`(mapcar #'+ ,@rest))
(defmacro s* (x p)
"Scalar multiplication of scalar x to geom. vector p."
`(mapcar #'(lambda (y) (* ,x y)) ,p))
(defmacro dot (p q)
"Dot operator on two vectors."
`(apply #'+ (mapcar #'* ,p ,q)))
(defmacro perp (p &optional q)
"The perp operator. Assuming that p is 2d geom. vector, the
perp operation is performed on p. If q is not specified, the
result of this operation is returnied. Otherwise, the perp
product of p and q is returnied."
`(destructuring-bind (p1 p2) ,p
(let ((pp (list (- p2) p1)))
,(if (null q) 'pp `(dot pp ,q)))))
(defun in-line-2d (p p0 p1)
"Assuming that p, p0, and p1 are collinear, this function
returnes true iff p is in the segment p0p1. The result is
undefined if the points are not collinear."
(destructuring-bind
((p.x p.y) (p0.x p0.y) (p1.x p1.y)) `(,p ,p0 ,p1)
(if (not (= p0.x p1.x))
;; p0p1 is not vertical
(or
(and (<= p0.x p.x) (<= p.x p1.x))
(and (>= p0.x p.x) (>= p.x p1.x)))
;; p0p1 is vertical
(or
(and (<= p0.y p.y) (<= p.y p1.y))
(and (>= p0.y p.y) (>= p.y p1.y))))))
(defun in-line-mvalue-2d (p p0 p1)
"Same as in-line-2d, but has a multi value return which is
compatible with line-intersection-2d. Hence, the fist value
is true iff p lies within p0p1 (assuming the points are collinear),
the second value is p, the third value is nil, the fourth value
is s with p=p0+s*(p1-p0)."
(if (eq p p0)
(values t p nil 0)
(let* ((u (v- p1 p0))
(v (v- p p0)))
(destructuring-bind
((u.x u.y) (v.x v.y)) `(,u ,v)
(let ((s (if (zerop u.x) (/ v.y u.y) (/ v.x u.x))))
(values (and (<= 0 s) (<= s 1)) p nil s))))))
(defun overlap-2d (p0 p1 q0 q1)
"Checks whether two collinear segments overlap.
The multi value return is compatible to line-interection-2d."
(let ((v (v- q1 q0))
(w (v- p0 q0))
(w2 (v- p1 q0)))
(destructuring-bind
(v.x v.y w.x w.y w2.x w2.y) `(,@v ,@w ,@w2)
(let* ((r (if (zerop v.x)
`(,(/ w.x v.x) ,(/ w2.x v.x))
`(,(/ w.y v.y) ,(/ w2.y v.y))))
(r0 (min r)) (r1 (max r)))
(if (or (> r0 1) (< 0 r1))
(values nil nil nil nil)
(let ((r0c (max 0 r0)) (r1c (min 1 r1)))
(values t
(v+ q0 (s* r0c v))
(if (not (= r0c r1c)) (v+ q0 (s* r1c v)))
r0c)))))))
(defun line-intersection-2d (p0 p1 q0 q1)
"Checks whether the two segments p0p1, q0q1 intersect,
returning true iff they do. Furthermore, the second value
is the point where the intersection starts. Also, if p0p1 and
q0q1 are not parallel and do not intersect, the second value
gives the intersection of their infinite extension. If the
intersection is a segment, the third value specifes the end,
otherwise it is nil. The fourth value is for future use."
(let ((u (v- p1 p0))
(v (v- q1 q0))
(w (v- p0 q0)))
(if (zerop (perp u v))
(if (or (not (zerop (perp u w))) (not (zerop (perp v w))))
;; parallel but not collinear
(values nil nil nil nil)
;; collinear or degenearate
(let ((du-zp (zerop (dot u u)))
(dv-zp (zerop (dot v v))))
(cond
((and du-zp dv-zp) (if (eq p0 p1)
(values t p0 1)
(values nil nil nil)))
(du-zp (in-line-mvalue-2d p0 q0 q1))
(dv-zp (in-line-mvalue-2d q0 p0 p1))
(t (overlap-2d p0 p1 q0 q1)))))
;; segements are skew
(destructuring-bind
(u.x u.y v.x v.y w.x w.y) `(,@u ,@v ,@w)
(let ((s (/ (-(* v.y w.x)(* v.x w.y))
(-(* v.x u.y)(* v.y u.x)))))
(values (and (<= 0 s) (<= s 1)) (v+ p0 (s* s u)) nil s))))))
Christian Haselbach <······@muon.de> writes:
> Thanks for the hint. This seems to be a bit heavyweight for my needs.
> I started to write my own, which can be found below.
>
> Comments are very welcome (I am still rather new to Lisp). Especially:
> Would it be better to use vectors instead of lists to represent
> (mathematical/geomatrical) vectors. If so, how can the destructuring
> part be made in a way that it works with any sequence?
OK, here are a few comments.
Yes, use vectors instead of list. Not sure what is "the destructuring part".
Do you mean that you write a lot of code like:
> (destructuring-bind
> ((u.x u.y) (v.x v.y)) `(,u ,v)
If so, what you do is you write some sort of logical
accessor using SYMBOL-MACROLET, e.g.
WARNING UNTESTED CODE, SLAPPED RIGHT IN NEWSREADER FOLLOWS!
(defmacro with-point ((x y) p &body body)
`(symbol-macrolet ((,x (svref ,p 0))
(,y (svref ,p 1)))
,@body))
(with-point ((u.x u.y) u)
(with-point ((v.x v.y) v)
;;; stuff on u.x u.y v.x v.y....
You wrote a lot of operations as macros, e.g.
> (defmacro s* (x p)
> "Scalar multiplication of scalar x to geom. vector p."
> `(mapcar #'(lambda (y) (* ,x y)) ,p))
If you look at this macro, you notice that all of it's arguments
are evaluated exactly once. This is normally a hint that this
is really a function. The following:
(defun s* (x p)
(mapcar (lambda (y) (* y x)) p))
does the same, except that now you have a new function
available to do functional programming with---i.e. you
can access this code with (function s*).
This means you'll be able to do things like CURRY and COMPOSE
on it, which will undoubtedly be very useful in this problem
domain.
Next, you've made some assumptions in your code, e.g. in
> (defmacro v+ (&rest rest)
> "Plus operator for geom. vectors."
> `(mapcar #'+ ,@rest))
What happens if I call
(v+ (list 1 2 3) (list 1 2)) ?
I get (2 4). Is that what you intended?
I would think that adding 2 vectors of differing
dimensions is an error.
Anyway, this should get you thinking a bit.
Good luck!
From: Christian Haselbach
Subject: Re: Geometry Library for Common Lisp?
Date:
Message-ID: <e1bimt$di6$2@online.de>
Alain Picard worte:
> OK, here are a few comments.
Thank you very much. That was indeed very helpful.
> Next, you've made some assumptions in your code, e.g. in
Yes, for the sake of simplicity I did. I should clean this up.
Regards,
Christian
Christian Haselbach <······@muon.de> writes:
> Comments are very welcome (I am still rather new to Lisp). Especially:
> Would it be better to use vectors instead of lists to represent
> (mathematical/geomatrical) vectors. If so, how can the destructuring
> part be made in a way that it works with any sequence?
<snip>
> (defmacro v- (&rest rest)
> "Minus operator for geom. vectors."
> `(mapcar #'- ,@rest))
Don't forget CL:MAP which works for both lists and vectors.
You can standardise on using vectors and still get the
convenience of using mapping functions
(defun sum (&rest vectors)
(apply #'map 'vector #'+ vectors))
CL-USER> (sum #(10 20 30) #(9 8 7))
#(19 28 37)
Alan Crowe
Edinburgh
Scotland