在任何F＃（或C＃）R树实现？ [英] Any R-Tree implementation in F# (or C#)?

问题描述

可能重复：结果
的是否有任何记载自由R树实施.NET？

是否有F＃的R树实施

假设是：无需插入或删除，固定集电子围栏（地区）。
需要是：非常快的搜索时间

感谢您

解决方案

下面的这一个OCaml中，以F＃。

<预类=郎毫升prettyprint-覆盖> 命名空间RTREE

打开系统

模块信封=

型T =浮浮* * *浮浮

让ranges_intersect AB一个'b'= A'< = b和;&安培;一个与所述; = B'

让相交（X0，X1，Y0，Y1）（X0'，X1'，Y0'，Y1'）=
（*对于两个信封相交，无论它们的范围做*）
ranges_intersect X0 X1 X0'X1'和;&安培; ranges_intersect Y0 Y1 Y0'Y1'

让添加（X0，X1，Y0，Y1）（X0'，X1'，Y0'，Y1'）=
分钟X0 X0'，最大X1 X1'，Y0分钟Y0'，最大Y1 Y1'

让REC add_many =函数
| Ë:: [] - > E $ B $ C | Ë:: ES - >加E（add_many ES）
| [] - >提高（ArgumentException的不能零信封）

让区域（X0，X1，Y0，Y1）=
（X1 - X0）*（Y1 - Y0）

让内（X0，X1，Y0，Y1）（X0'，X1'，Y0'，Y1'）=
X0&下; = X0'和;&放大器; X1> = X1'和;&安培; Y0< Y0 ='和;&安培; Y1> Y1 ='

让空= 0，0，0，0，

模块RTREE =

型'的=（Envelope.t *'的）名单
的
节点| （Envelope.t *'一）名单
叶|空

让max_node_load = 8

让空=空
让empty_node =（Envelope.empty，空）

让enlargement_neededË E'=
Envelope.area（Envelope.add E E'） - Envelope.areaË

让REC partition_by_min_enlargement E =函数
| （E'_）为n :: [] - >
N，[]，enlargement_needed E E'
| （E'_）为n :: NS - >
让利扩大= enlargement_needed E E'
让分，MAXS，放大'= partition_by_min_enlargementËNS
如果肿大<扩大'，那么
N，分:: MAXS，扩大
，否则
分，正:: MAXS，放大'
| [] - >
加薪（ArgumentException的不能分区空节点）

让pairs_of_list XS =（*（积）*）
List.concat（List.map（好玩点¯x - > List.map（乐趣Ÿ - >（X，Y））。XS）XS）

（*这是Guttman的二次型分裂算法*）
让split_pick_seeds NS =
让双= pairs_of_list NS
让利成本（E0，_）（E1，_）=
（Envelope.area（Envelope.add E0 E1）） -
（Envelope.area E0 ） - （Envelope.area E1）
让REC max_cost =函数
| （N，N'）:: [] - GT;成本N N'（N'）
| （N，N-'）作为对:: NS - >
让max_cost'，对'= max_cost NS
让利成本=成本N N'
如果成本> max_cost'，那么
的成本，对
，否则
max_cost'，对'
| [] - >提高（ArgumentException的不能计算为空名单上分裂）
设（_，团体）=成群成对max_cost

让split_pick_next E0 E1 NS =
让差异（ E，_）=
ABS（（enlargement_needed E0 E） - （enlargement_needed E1 E））
让REC max_difference =函数
| ñ:: [] - >差异N，
| ñ:: NS - >
让差异'，N'= max_difference NS
让差异=差异N
如果DIFF>差异，那么
差异，N
，否则
差异'，N'
| [] - >提高（ArgumentException的不能计算为空名单上的最大差异）
设（_，N）在N

= max_difference Ns我们split_nodes NS =
让REC分区XS xs_envelope YS ys_envelope =函数
| [] - > （XS，xs_envelope），（YS，ys_envelope）
|其余的 - >
设（E，_）为n = split_pick_next xs_envelope ys_envelope休息
让休息'= List.filter（（<>）N），其余
让enlargement_x = enlargement_neededËxs_envelope
让enlargement_y = enlargement_neededËys_envelope
如果enlargement_x< enlargement_y然后
分区（N :: XS）（Envelope.add xs_envelope E）YS ys_envelope休息'
，否则
分区XS xs_envelope（N :: YS）（Envelope.add ys_envelope E）休息'
设（（（E0，_）为N0），（（E1，_）为N1））= split_pick_seeds NS
分区[N0] E0 [N1] E1（List.filter（乐趣ñ - > N<> N0和放大器;&安培; N<> N1）NS）

让envelope_of_nodes NS = Envelope.add_many（List.map（FUN（E，_） - GT ; E）NS）

让REC插入'ELEM E =函数
|节点NS - >
设（_，分），MAXS，_ = partition_by_min_enlargementËNS
匹配插入'ELEMË分钟，
|分'，（_，空） - GT;
让NS =分钟':: MAXS
让E'= envelope_of_nodes NS'
（E'，节点NS），empty_node
|分，分时（List.length的数字MAXS + 2）LT; max_node_load - >
让NS =分钟'::分钟'':: MAXS
让E'= envelope_of_nodes NS'
（E'，节点NS），empty_node
|分，分' - >
设（一，envelope_a），（B，envelope_b）=
split_nodes（分'::分钟':: MAXS）
（envelope_a，节点A），（envelope_b，节点B ）
|叶ES - >
让ES =（E，ELEM）:: ES
如果List.length的数字ES'> max_node_load然后
让利（一，envelope_a），（B，envelope_b）= split_nodes ES'
（envelope_a，叶一），（envelope_b，叶B）
，否则
（envelope_of_nodes ES，叶ES'），empty_node
|空 - >
（即叶[E，ELEM]），empty_node

让将考勤ELEM E =
匹配插入'ELEM（E T）与
| （_，一），（_，空） - >一个
| A，B - >节点[A; B]（*根分割*）

让filter_intersecting E =
List.filter（FUN（E'，_） - GT; Envelope.intersects E E'）

让REC发现TE =
匹配吨，
|节点NS - >
让相交= filter_intersectingËNS
让利发现= List.map（FUN（_，N） - GT;求n E）相交
List.concat发现
|叶ES - > List.map SND（filter_intersectingËES）
|空 - > []

让REC大小=函数
|节点NS - >
让sub_sizes = List.map（FUN（_，N） - GT;大小为n）NS
List.fold（+）0 sub_sizes
|叶ES - >
List.length的数字ES
|空 - >
0


Possible Duplicate:
Is there any documented free R-Tree implementation for .NET?

Are there any R-Tree implementations in F#?

Assumptions are: no need for insertion or deletion, fixed set of Geo-Fences (regions). Needs are: very fast search time.

Thank you

解决方案

Here's a quick translation of this one in OCaml to F#.

namespace RTree

open System

module Envelope =

  type t = float * float * float * float

  let ranges_intersect a b a' b' = a' <= b && a <= b'

  let intersects (x0, x1, y0, y1) (x0', x1', y0', y1') =
    (* For two envelopes to intersect, both of their ranges do. *)
    ranges_intersect x0 x1 x0' x1' && ranges_intersect y0 y1 y0' y1'

  let add (x0, x1, y0, y1) (x0', x1', y0', y1') =
    min x0 x0', max x1 x1', min y0 y0', max y1 y1'

  let rec add_many = function
    | e :: [] -> e
    | e :: es -> add e (add_many es)
    | [] -> raise (ArgumentException "can't zero envelopes")

  let area (x0, x1, y0, y1) =
    (x1 - x0) * (y1 - y0)

  let within (x0, x1, y0, y1) (x0', x1', y0', y1') =
    x0 <= x0' && x1 >= x1' && y0 <= y0' && y1 >= y1'

  let empty = 0., 0., 0., 0.

module rtree =

  type 'a t =
      Node of (Envelope.t * 'a t) list
    | Leaf of (Envelope.t * 'a) list
    | Empty

  let max_node_load = 8

  let empty = Empty
  let empty_node = (Envelope.empty, Empty)

  let enlargement_needed e e' =
    Envelope.area (Envelope.add e e') - Envelope.area e

  let rec partition_by_min_enlargement e = function
    | (e', _) as n :: [] ->
        n, [], enlargement_needed e e'
    | (e', _) as n :: ns ->
        let enlargement = enlargement_needed e e' 
        let min, maxs, enlargement' = partition_by_min_enlargement e ns 
        if enlargement < enlargement' then
          n, min :: maxs, enlargement
        else
          min, n :: maxs, enlargement'
    | [] ->
        raise (ArgumentException "cannot partition an empty node")

  let pairs_of_list xs =  (* (cross product) *)
    List.concat (List.map (fun x -> List.map (fun y -> (x, y)) xs) xs)

  (* This is Guttman's quadradic splitting algorithm. *)
  let split_pick_seeds ns =
    let pairs = pairs_of_list ns 
    let cost (e0, _) (e1, _) =
      (Envelope.area (Envelope.add e0 e1)) -
      (Envelope.area e0) - (Envelope.area e1) 
    let rec max_cost = function
      | (n, n') :: [] -> cost n n', (n, n')
      | (n, n') as pair :: ns ->
          let max_cost', pair' = max_cost ns 
          let cost = cost n n' 
          if cost > max_cost' then
            cost, pair
          else
            max_cost', pair'
      | [] -> raise (ArgumentException "can't compute split on empty list") 
    let (_, groups) = max_cost pairs in groups

  let split_pick_next e0 e1 ns =
    let diff (e, _) =
      abs ((enlargement_needed e0 e) - (enlargement_needed e1 e)) 
    let rec max_difference = function
      | n :: [] -> diff n, n
      | n :: ns ->
          let diff', n' = max_difference ns 
          let diff = diff n 
          if diff > diff' then
            diff, n
          else
            diff', n'
      | [] -> raise (ArgumentException "can't compute max diff on empty list") 
    let (_, n) = max_difference ns in n

  let split_nodes ns =
    let rec partition xs xs_envelope ys ys_envelope = function
      | [] -> (xs, xs_envelope), (ys, ys_envelope)
      | rest -> 
          let (e, _) as n = split_pick_next xs_envelope ys_envelope rest 
          let rest' = List.filter ((<>) n) rest 
          let enlargement_x = enlargement_needed e xs_envelope 
          let enlargement_y = enlargement_needed e ys_envelope 
          if enlargement_x < enlargement_y then
            partition (n :: xs) (Envelope.add xs_envelope e) ys ys_envelope rest'
          else
            partition xs xs_envelope (n :: ys) (Envelope.add ys_envelope e) rest'
    let (((e0, _) as n0), ((e1, _) as n1)) = split_pick_seeds ns 
    partition [n0] e0 [n1] e1 (List.filter (fun n -> n <> n0 && n <> n1) ns)

  let envelope_of_nodes ns = Envelope.add_many (List.map (fun (e, _) -> e) ns)

  let rec insert' elem e = function
    | Node ns -> 
        let (_, min), maxs, _ = partition_by_min_enlargement e ns 
        match insert' elem e min with
          | min', (_, Empty) ->
              let ns' = min' :: maxs 
              let e' = envelope_of_nodes ns' 
              (e', Node ns'), empty_node
          | min', min'' when (List.length maxs + 2) < max_node_load ->
              let ns' = min' :: min'' :: maxs 
              let e' = envelope_of_nodes ns' 
              (e', Node ns'), empty_node
          | min', min'' ->
              let (a, envelope_a), (b, envelope_b) =
                split_nodes (min' :: min'' :: maxs) 
              (envelope_a, Node a), (envelope_b, Node b)
    | Leaf es ->
        let es' = (e, elem) :: es 
        if List.length es' > max_node_load then
          let (a, envelope_a), (b, envelope_b) = split_nodes es' 
          (envelope_a, Leaf a), (envelope_b, Leaf b)
        else
          (envelope_of_nodes es', Leaf es'), empty_node
    | Empty ->
        (e, Leaf [e, elem]), empty_node

  let insert t elem e =
    match insert' elem e t with
      | (_, a), (_, Empty) -> a
      | a, b -> Node [a; b]  (* root split *)

  let filter_intersecting e =
    List.filter (fun (e', _) -> Envelope.intersects e e')

  let rec find t e =
    match t with
      | Node ns ->
          let intersecting = filter_intersecting e ns 
          let found = List.map (fun (_, n) -> find n e) intersecting 
          List.concat found
      | Leaf es -> List.map snd (filter_intersecting e es)
      | Empty -> []

  let rec size = function
    | Node ns ->
        let sub_sizes = List.map (fun (_, n) -> size n) ns 
        List.fold (+) 0 sub_sizes
    | Leaf es ->
        List.length es
    | Empty ->
        0

这篇关于在任何F＃（或C＃）R树实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！