r_tree 1.0.6

RTree Build Status

A recursive RTree library written in Dart. This R-tree implementation is used to index and query two-dimensional data. Items are inserted and balanced via the RTree class and can then be queried by Rectangle. The balancing can be tweaked by modifying the branch factor of the RTree.

"R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons." - http://en.wikipedia.org/wiki/R-tree

Example #

Run the example app for a visual demonstration of the RTree

pub serve example

Navigate to http://localhost:8080. A canvas is drawn, click & drag on the canvas to add rectangles of various colors to your RTree, then click the search button and click & drag over an area of the canvas to search it for rectangles.

Benchmarks #

Run the benchmarks in the command line (Dart VM) using:

dart benchmark/benchmarks.dart

You can also run them in a browser using dart2js using pub serve benchmark or pub build benchmark and then serving them with your http server of choice. Click the run button and observe the output in the browser console.

1.0.6 #

  • Added docstrings, example app, and this file!

1.0.5 #

  • Dart 2 support (still supports Dart 1, too)

1.0.4 #

  • Additional benchmarks and the ability to run benchmarks in the browser
  • Minor performance enhancements in dart2js

1.0.3 #

  • Improved performance and reduced GC churn when calling overlaps on RTreeContributor

1.0.2 #

  • No functional changes, CI cleanup etc

1.0.1 #

  • Strong mode compliance
  • Added generics to nodes

1.0.0 #

  • Initial release

example/main.dart

import 'dart:async';
import 'dart:html';
import 'package:r_tree/r_tree.dart';

Future main() async {
  var rtree = new RTree<String>();
  var app = querySelector('#app');
  var canvas = new CanvasElement(width: 640, height: 480);
  app.append(canvas);
  canvas.context2D
    ..fillStyle = '#ccc'
    ..fillRect(0, 0, 640, 480);

  int startX, startY;
  canvas.onMouseDown.listen((MouseEvent event) {
    var target = event.currentTarget as HtmlElement;
    var boundingRect = target.getBoundingClientRect();
    startX = ((event.client.x - boundingRect.left) + target.scrollLeft).floor();
    startY = ((event.client.y - boundingRect.top) + target.scrollTop).floor();
  });

  canvas.onMouseUp.listen((MouseEvent event) {
    if (startX == null || startY == null) return;

    var target = event.currentTarget as HtmlElement;
    var boundingRect = target.getBoundingClientRect();
    var endX =
        ((event.client.x - boundingRect.left) + target.scrollLeft).floor();
    var endY = ((event.client.y - boundingRect.top) + target.scrollTop).floor();

    var rectangle = new Rectangle(startX, startY, endX - startX, endY - startY);

    if (currentBrush == 'search') {
      var resultList = querySelector('#results');
      resultList.children = [];
      for (RTreeDatum match in rtree.search(rectangle)) {
        var color = '';
        switch (match.value) {
          case red:
            color = 'Red';
            break;
          case green:
            color = 'Green';
            break;
          case blue:
            color = 'Blue';
            break;
          default:
            print('no match for ${match.value}');
        }
        resultList
            .append(new LIElement()..innerHtml = '$color at ${match.rect}');
      }
      if (resultList.children.isEmpty) {
        resultList
            .append(new LIElement()..innerHtml = 'No results in $rectangle');
      }
    } else {
      canvas.context2D.fillStyle = currentBrush;
      canvas.context2D.fillRect(startX, startY, endX - startX, endY - startY);
      rtree.insert(new RTreeDatum(rectangle, currentBrush));
    }
  });

  querySelector('#red').onClick.listen((_) => currentBrush = '$red');
  querySelector('#green').onClick.listen((_) => currentBrush = '$green');
  querySelector('#blue').onClick.listen((_) => currentBrush = '$blue');
  querySelector('#search').onClick.listen((_) => currentBrush = 'search');
}

const String alpha = '88';
const String red = '#ff0000$alpha';
const String green = '#00ff00$alpha';
const String blue = '#0000ff$alpha';
String currentBrush = '$red';

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  r_tree: ^1.0.6

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

Alternatively, your editor might support pub get or flutter pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:r_tree/r_tree.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
65
Health:
Code health derived from static analysis. [more]
98
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
100
Overall:
Weighted score of the above. [more]
82
Learn more about scoring.

We analyzed this package on Aug 22, 2019, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.4.0
  • pana: 0.12.19

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:r_tree/r_tree.dart.

Health suggestions

Fix lib/src/r_tree/r_tree_datum.dart. (-1 points)

Analysis of lib/src/r_tree/r_tree_datum.dart reported 2 hints:

line 24 col 14: Don't type annotate initializing formals.

line 24 col 35: Don't type annotate initializing formals.

Fix lib/src/r_tree/node.dart. (-0.50 points)

Analysis of lib/src/r_tree/node.dart reported 1 hint:

line 91 col 9: Use isEmpty instead of length

Fix lib/src/r_tree/non_leaf_node.dart. (-0.50 points)

Analysis of lib/src/r_tree/non_leaf_node.dart reported 1 hint:

line 83 col 9: Use isEmpty instead of length

Fix lib/src/r_tree/r_tree.dart. (-0.50 points)

Analysis of lib/src/r_tree/r_tree.dart reported 1 hint:

line 35 col 9: Use isEmpty instead of length

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=1.24.3 <3.0.0
dart2_constant ^1.0.0 1.0.2+dart2
Dev dependencies
benchmark_harness any
build_runner >=0.6.0 <2.0.0
build_test >=0.9.0 <1.0.0
build_web_compilers >=0.2.0 <1.0.0
coverage >=0.10.0 <0.13.0
dart_dev ^2.0.0
dart_style ^1.0.9
test >=0.12.30 <2.0.0