From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1G2WQOE000758 for ; Thu, 16 Feb 2012 03:32:26 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AssBAJ9pPE+GoCGimWdsb2JhbABDgw6tewEBAQEBBg0LBxQngXIBAQQBOEAGCwsYCRYPCQMCAQIBRRMGAgEBBYd2CblHi1QBAgUBARYEEgMMAQIHCAIEAQUDAQgEBw8JAoNtBycKAgcHAgQGAxCDHQSIS4xrhV2NGg X-IronPort-AV: E=Sophos;i="4.73,426,1325458800"; d="scan'208";a="144456142" Received: from postman2.riken.jp (HELO postman.riken.jp) ([134.160.33.162]) by mail1-smtp-roc.national.inria.fr with ESMTP; 16 Feb 2012 03:32:23 +0100 Received: from postman.riken.jp (postman2.riken.jp [127.0.0.1]) by postman.riken.jp (Postfix) with SMTP id 8950412602D8; Thu, 16 Feb 2012 11:32:21 +0900 (JST) Received: from [172.27.98.103] (rikad98.riken.jp [134.160.214.98]) by postman.riken.jp (Postfix) with ESMTPA id 9BDAF127007D; Thu, 16 Feb 2012 11:32:20 +0900 (JST) Message-ID: <4F3C6AB4.6090100@riken.jp> Date: Thu, 16 Feb 2012 11:32:20 +0900 From: Francois Berenger User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.26) Gecko/20120131 Thunderbird/3.1.18 MIME-Version: 1.0 To: caml-list@inria.fr References: <4F346DB9.2070303@riken.jp> <20120210182914.GA17498@annexia.org> <87wr7tb77z.fsf@frosties.localnet> <4F36AA45.1070502@colba.net> <4F38D455.1040204@irisa.fr> <4F3B0A46.3070105@riken.jp> <87mx8kruk1.fsf@frosties.localnet> In-Reply-To: <87mx8kruk1.fsf@frosties.localnet> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-PMX-Version: 5.6.0.2009776, Antispam-Engine: 2.7.2.376379, Antispam-Data: 2012.2.13.54815 Subject: Re: [Caml-list] Fwd: interval trees On 02/16/2012 12:21 AM, Goswin von Brederlow wrote: > Francois Berenger writes: > >> Hello, >> >> I did a naive implementation of interval trees for float intervals. >> >> It is available here: >> https://github.com/HappyCrow/interval-tree >> >> I wonder if it is possible to construct the trees in a tail recursive >> fashion. Maybe I knew how to do this when I was still at university. >> >> Regards, >> Francois. > > | Node of > (* x_mid left_list right_list left_tree right_tree *) > float * interval list * interval list * interval_tree * interval_tree > > Why interval list? You only need a single interval in leafes and none in > other nodes (although it can help to store min and max in each node). Not in my case, there is a payload associated with each interval in my application so I need to keep track of the individual intervals. > You are also missing insert and remove operations, I don't miss anything: I don't need these operations in my application. > which is the actually > hard part in this. Inserting an interval might require merging the > rightmost interval left of the root and the leftmost interval right of > the root. So you would have 2 removals and one insertion of a combined > interval, which complicates balancing the whole thing efficiently. I hope you have a good book on this. By the way, the one I refer to in my code is quite nice. At first I thought it was too theoretical for me, but in fact they give algorithms in recursive form so the book can become pretty handy. > That is the part I'm struggling with. You might be intersted into having a look at the Computational Geometry Algorithms Library: http://www.cgal.org/ It's open source and it's also an INRIA product, which makes two good points. ;) You might want to bind your code to this library (they introduced some framework recently, SWIG if I remember well, so that it should be easy to do wrappers for any language). It's heavily templated C++ code, good luck if you read their code. They have a lot of crazily useful data structures (interval skip lists, k-d trees, segment trees, range trees, AABB trees), and their code is impossible to crash when using some specific math kernels. Regards, F.