[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] quadtrees

Magnus Lie Hetland wrote:
> On Fri, 3 Oct 2003 05:08 am, Gerrit Holl wrote:
> > Has anyone ever implemented quadtrees in Python?
> 
> Just a thought (relating to the recent discussion about NN-queries in
> 2d): By using a Voronoi tesselation and a point location algorithm you
> can get a structure where you can add a point in O(log n) time and
> search for the nearest neighbor of a query point also in O(log n)
> time. (Similar stuff can be done with Delaunay triangulations, for
> example by temporarily adding the query point to the triangulation.)

I am afraid I do not understand what you are saying, I do not have
enough background knowledge: I have never heard of "Voronoi tesselation"
or "Delaunay triangulations" and don't know what "NN-queries" are, but
this does give me some more terms to Google for.

> In case there are others here interested in general proximity search,
> I found the mention of the use of Delaunay triangulations in the
> following paper, which is very good, IMO:
> 
>   http://citeseer.nj.nec.com/avez99searching.html

OK, I will read this one. Thanks for the link!

> (I haven't found any descriptions of the Delaunay NN-search algorithm
> online, though, other than the approach of adding the query to the
> triangulation.)

Thanks for the answer!

Gerrit.

-- 
172. If her husband made her no gift, she shall be compensated for her
gift, and she shall receive a portion from the estate of her husband,
equal to that of one child. If her sons oppress her, to force her out of
the house, the judge shall examine into the matter, and if the sons are at
fault the woman shall not leave her husband's house. If the woman desire
to leave the house, she must leave to her sons the gift which her husband
gave her, but she may take the dowry of her father's house. Then she may
marry the man of her heart.
        -- 1780 BC, Hammurabi, Code of Law
--
Asperger Syndroom - een persoonlijke benadering:
	http://people.nl.linux.org/~gerrit/
Het zijn tijden om je zelf met politiek te bemoeien:
	http://www.sp.nl/