Hey,
I am a newbie at LISP. I have undertaken to write a small program for
Dealaunay triangulation/Voronoi Diagram in LISP. I found quite a few
newsgroup and other links to help me with the algorithm but i having
syntax and dealing with lists and parsin thru lists in LISP. So, I was
wondering if someone could help me with this... If someone has some
LISP code for similar purposes which I could refer too than tht would
be great.
Any kind of help will be really appreciated.
-Nihit
··············@techemail.com (Nick) writes:
> I am a newbie at LISP. I have undertaken to write a small program for
> Dealaunay triangulation/Voronoi Diagram in LISP. I found quite a few
> newsgroup and other links to help me with the algorithm but i having
> syntax and dealing with lists and parsin thru lists in LISP. So, I was
> wondering if someone could help me with this... If someone has some
> LISP code for similar purposes which I could refer too than tht would
> be great.
I understand that this isn't helpful as such, but I'm curious:
If you're a newbie, why have you undertaken to write something
decidedly non-trivial in Lisp? I mean, why not either write it
in a language you're a non-newbie at, or work some more on
improving your fluency in Lisp before attempting it?
What algorithm are you proposing to use for Delaunay triangulation?
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> wrote in message news:<··············@g.mccaughan.ntlworld.com>...
> ··············@techemail.com (Nick) writes:
>
> > I am a newbie at LISP. I have undertaken to write a small program for
> > Dealaunay triangulation/Voronoi Diagram in LISP. I found quite a few
> > newsgroup and other links to help me with the algorithm but i having
> > syntax and dealing with lists and parsin thru lists in LISP. So, I was
> > wondering if someone could help me with this... If someone has some
> > LISP code for similar purposes which I could refer too than tht would
> > be great.
>
> I understand that this isn't helpful as such, but I'm curious:
> If you're a newbie, why have you undertaken to write something
> decidedly non-trivial in Lisp? I mean, why not either write it
> in a language you're a non-newbie at, or work some more on
> improving your fluency in Lisp before attempting it?
>
> What algorithm are you proposing to use for Delaunay triangulation?
Well, the reason for that is, I started off with Delaunay
triangulation/Voronoi Diagram and not with LISP. I was thinking of
implementing it and thought why not do it in LISP. I have been meaning
to get my hands into LISP for quite sometime and that's how I landed
here.
And, I am planning on using the Bowyer-Watson algorithm.
-Nihit
··············@techemail.com (Nick) writes:
> > > I am a newbie at LISP. I have undertaken to write a small program for
> > > Dealaunay triangulation/Voronoi Diagram in LISP. I found quite a few
> > > newsgroup and other links to help me with the algorithm but i having
> > > syntax and dealing with lists and parsin thru lists in LISP. So, I was
> > > wondering if someone could help me with this... If someone has some
> > > LISP code for similar purposes which I could refer too than tht would
> > > be great.
> >
> > I understand that this isn't helpful as such, but I'm curious:
> > If you're a newbie, why have you undertaken to write something
> > decidedly non-trivial in Lisp? I mean, why not either write it
> > in a language you're a non-newbie at, or work some more on
> > improving your fluency in Lisp before attempting it?
> >
> > What algorithm are you proposing to use for Delaunay triangulation?
>
> Well, the reason for that is, I started off with Delaunay
> triangulation/Voronoi Diagram and not with LISP. I was thinking of
> implementing it and thought why not do it in LISP. I have been meaning
> to get my hands into LISP for quite sometime and that's how I landed
> here.
>
> And, I am planning on using the Bowyer-Watson algorithm.
Sounds plausible. So, you need data structures that let you
keep track of the points and triangles, and that let you
identify which triangle a given point is in and find the
neighbours of a given triangle. You shouldn't try to do this
all with lists. You'll want types for points (it may well
be good enough to use a cons cell (x . y) to represent a point),
for triangles (you'll want a structure or a CLOS class for this),
and for quadtree nodes (you'll want a structure or a CLOS class
for this too). Quadtrees are by no means the only game in
town for point location; whatever you use is likely to be
some kind of tree, but you'll want to use structures or
classes for the nodes.
Here are a few fragments that may give you ideas.
I don't guarantee that they're suitable for putting
into your code as they stand :-).
(defun triangles-nearby (p t1 already-seen)
"P is a point, T1 a triangle whose circumcircle
contains P, and ALREADY-SEEN a list containing
the triangles -- including T1 -- that have already
been noted to have circumcircles containing P;
the corresponding hash values are all T. Return
a list containing every such triangle that can
be reached from T1 without going via a triangle
in ALREADY-SEEN, together with the contents of
ALREADY-SEEN, no triangle appearing more than
once. Note that when T1 is the only element of
ALREADY-SEEN, this yields a list of *all* triangles
having P in their circumcircles."
(dolist (t2 (triangle-neighbours t1))
(unless (member t2 already-seen)
(when (triangle-circumcircle-contains t2 p)
(setf already-seen
(triangles-nearby p t2 (cons t2 already-seen)))))
already-seen))
(defun triangles-to-replace (p triangulation)
"P is a point. Return a list containing all triangles
whose circumcircles contain P, once each."
(let ((t1 (find-triangle-containing p triangulation)))
(triangles-nearby p t1 (list t1))))
(You might actually want to return a little more information
from this function, to make the retriangulation go more
smoothly. I haven't thought this through.)
(defun shuffle (items)
"A vector containing each element of ITEMS just once,
in random order. If ITEMS is a vector rather than a
list, the returned value may be the same object as
ITEMS."
(let* ((new-items (coerce items 'vector))
(n (length new-items)))
(loop for i below (1- n) do
(rotatef (svref new-items i)
(svref new-items (+ i (random (- n i))))))
new-items))
Shuffling a list randomly and returning another list,
rather than a vector, is harder to do efficiently.
(defun delaunay-triangulation (points)
(let ((triangulation (make-initial-triangulation)))
(loop for p across (shuffle points) do
(add-point p triangulation))
(clean-up triangulation)))
One not-particularly-relevant note about nomenclature.
No active Lisp user calls the language "LISP" these days,
partly because the all-caps style looks so old-fashioned
and partly because modern Lisp is no longer about "list
processing" alone. You'd talk about "LISP 1.5" (a classic
early version of the language), but not about "Common LISP"
(the dominant modern version). Similarly, you'd talk about
"FORTRAN IV" but "Fortran 95"; *that* language is no longer
simply about FORmula TRANslation nowadays :-).
I'm not sure whether any of the above is actually helpful;
it's not quite clear what level you're at. If it's either
insultingly elementary or confusingly advanced, please
accept my apologies and see if you can be more specific
about what's giving you problems...
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
> One not-particularly-relevant note about nomenclature.
> No active Lisp user calls the language "LISP" these days,
> partly because the all-caps style looks so old-fashioned
> and partly because modern Lisp is no longer about "list
> processing" alone. You'd talk about "LISP 1.5" (a classic
> early version of the language), but not about "Common LISP"
> (the dominant modern version). Similarly, you'd talk about
> "FORTRAN IV" but "Fortran 95"; *that* language is no longer
> simply about FORmula TRANslation nowadays :-).
Actually, it's just typographical error. Neither Fortran nor Lisp are
acronyms. They are not to be capitalized, but rendered in small-caps
when possible. Lowercase small-caps are not uppercase letters. :)
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain <·····@nyct.net> writes:
> Gareth McCaughan <················@pobox.com> writes:
>
> > One not-particularly-relevant note about nomenclature.
> > No active Lisp user calls the language "LISP" these days,
> > partly because the all-caps style looks so old-fashioned
> > and partly because modern Lisp is no longer about "list
> > processing" alone. You'd talk about "LISP 1.5" (a classic
> > early version of the language), but not about "Common LISP"
> > (the dominant modern version). Similarly, you'd talk about
> > "FORTRAN IV" but "Fortran 95"; *that* language is no longer
> > simply about FORmula TRANslation nowadays :-).
>
> Actually, it's just typographical error. Neither Fortran nor Lisp are
> acronyms. They are not to be capitalized, but rendered in small-caps
> when possible. Lowercase small-caps are not uppercase letters. :)
I assume this is a joke (in case it isn't: yes, LISP
and FORTRAN *were* originally acronyms, with the expansions
I mentioned), but actually something very similar did
happen with "Unix", which was "UNIX" for a long while
because Ritchie and Thompson had wanted to show off
their system's ability to typeset small caps.
--
Gareth McCaughan
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
> I assume this is a joke (in case it isn't: yes, LISP
> and FORTRAN *were* originally acronyms, with the expansions
> I mentioned),
Those aren't acronyms.
> but actually something very similar did
> happen with "Unix", which was "UNIX" for a long while
> because Ritchie and Thompson had wanted to show off
> their system's ability to typeset small caps.
Lisp and Fortran are properly typeset with small caps, just like Unix.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain <·····@nyct.net> writes:
> Gareth McCaughan <················@pobox.com> writes:
>
> > I assume this is a joke (in case it isn't: yes, LISP
> > and FORTRAN *were* originally acronyms, with the expansions
> > I mentioned),
>
> Those aren't acronyms.
My dictionary says that an acronym is a word formed
from the initial letters or parts of other words.
Are you saying (1) that "LISP" and "FORTRAN" weren't
formed from "LISt Processing" and "FORmula TRANslation",
(2) that they weren't words, or (3) that my dictionary
is wrong?
My current best guess is #2; if so, that claim is
hard to confirm or refute since the definition of
"word" is fuzzy. None the less, your original statement
"it's just typographical error" confuses me; I'm
not sure what it means, and I can't find any meaning
that makes much sense to me.
- If it means "People nowadays who write LISP or
FORTRAN are committing only a typographical
error; they should be writing those in small
capitals" then it's wrong because the small-caps
versions of those names are *not* the ones
preferred by the standards bodies or the user
communities of the languages in question.
- If it means "People nowadays who write LISP or
FORTRAN are committing only (or: are merely the
victims of) a typographical error; they have
misread, or someone has misprinted, the old
small-caps renditions as if they are uppercase"
then it's wrong because it's just not true
that "LISP" and "FORTRAN" were always meant
to be read as lowercase caps-and-small-caps.
(I am prepared to be corrected on this score,
if you have some evidence...)
- If it means "People in olden times who wrote
LISP or FORTRAN were committing only a typographical
error: they should have rendered those names in
small caps, not in full capitals" then the same
applies as in the previous paragraph.
I'm sorry to be making such heavy weather of what
was originally (I think) a light-hearted remark...
>> but actually something very similar did
>> happen with "Unix", which was "UNIX" for a long while
>> because Ritchie and Thompson had wanted to show off
>> their system's ability to typeset small caps.
>
> Lisp and Fortran are properly typeset with small caps, just like Unix.
They are not properly so typeset now. That is not how their
user communities and official representatives typeset them:
I've done a brief survey of the modern Fortran books, software
products, draft standards, etc, that I can find on the web;
not one uses small caps for the name. (Almost all use "Fortran".
One book uses "FORTRAN" in the title, but the rest of the title
is all-caps too.) Similarly for Lisp. Perhaps there's some
other reason why you think they should be typeset in small
caps (e.g., because they are abbreviations of some particular
sort that should always be typeset in small caps), but I am
unaware of any typographical principle that would justify this.
I am not aware that they were properly so typeset in the
Old Days (say, the time of LISP 1.5 and of FORTRAN IV), but
as I said above I'm prepared to be corrected.
--
Gareth McCaughan
.sig under construc
* Gareth McCaughan:
> ... that "LISP" and "FORTRAN" weren't formed from "LISt Processing"
> and "FORmula TRANslation",
I live under the impression that LISP stands for list processor, at
least since `Recursive Functions of Symbolic Expressions and Their
Computation by Machine, Part I' by John McCarthy.
The F in FLPL is for FORTRAN is for formular translator...
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
From: Christopher C. Stacy
Subject: Re: Delaunay Triangulation in Lisp
Date:
Message-ID: <ullkrwzwv.fsf@news.dtpq.com>
>>>>> On 19 Apr 2004 10:32:49 +0100, Gareth McCaughan ("Gareth") writes:
Gareth> I am not aware that they were properly so typeset in the
Gareth> Old Days (say, the time of LISP 1.5 and of FORTRAN IV), but
Gareth> as I said above I'm prepared to be corrected.
In books of the "Old Days", which is when I learned, Fortran was
always written as "FORTRAN" in books. It was never typeset in
small caps or written in mixed-case. Nowadays people think
it looks neater in mixed-case, and they are also accustomed to
seeing random invented words (which may or may not be ancronyms,
but which can carry an abstract meaning of identity) . For example,
everybody also accepts the ancronym "radar", although they certainly
had typewriters with lowercase letters back when it was RADAR.
Now it's just a word. So are Fortran and Lisp.
Gareth McCaughan <················@pobox.com> writes:
> ··············@techemail.com (Nick) writes:
>
...
>> And, I am planning on using the Bowyer-Watson algorithm.
>
...
> You'll want types for points (it may well be good enough to use a
> cons cell (x . y) to represent a point),
Or use a complex number which may come in handy if/when it turns out
you need to do math with these things.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp