Website)
Region2D (Copyright © 2017 by Sean Werkema
Licensed under the Apache 2.0 Open Source License.
NOTE: For more information, a demo, and tutorials, visit the website.
Region2D usage
A Region2D
is an opaque object that represents a set of points in the 2-D plane, and is always composed of a series of nonoverlapping axis-aligned rectangles.
Construction:
// Normal construction:
var myRegion = new Region2D([x1, y1, x2, y2]);
var myRegion = new Region2D({ x:, y:, width:, height: });
var myRegion = new Region2D({ left:, top:, right:, bottom: });
var myRegion = new Region2D(htmlElement);
// Creation by unioning many rectangles:
var myRegion = Region2D.fromRects([ ...array of rectangles... ]);
// Fast creation using raw row data:
var myRegion = Region2D.fromRawRows([ ...array of raw row data... ]);
There are several ways to construct a Region2D
instance, as depicted above:
- You can create a
Region2D
from an array containing a set of exactly four numbers, which will be interpreted as the rectangle's leftmostx1
, topmosty1
, its leftmostx2
, and its rightmosty2
, in that order. - You can create a
Region2D
from any object with numericx
,y
,width
, andheight
properties. - You can create a
Region2D
from any object with numericleft
,top
,right
, andbottom
properties. - In browser environments, you can pass in an
HTMLElement
instance (a DOM element) to construct a region from its bounding box (page-relative). - There is also a helper that creates regions from arrays of many rectangles.
- There is another high-speed helper that creates regions from raw row data.
However the rectangle is represented, Region2D
always follows the following rules, both for rectangles used as input to it and for those that it produces as output:
x = left
y = top
width = right - left
height = bottom - top
Region2D
is designed to be reasonably efficient: All methods on Region2D
run in O(n) time, except for the binary operations (which run in O(n+m) time), and for a few operations that are O(1) or O(lg n), as noted below.
Region2D includes many operations for manipulating its set of points:
Set-theoretic operations:
var newRegion = myRegion.union(yourRegion);
var newRegion = myRegion.intersect(yourRegion);
var newRegion = myRegion.xor(yourRegion);
var newRegion = myRegion.subtract(yourRegion);
var newRegion = myRegion.not();
Transformation operations:
var newRegion = myRegion.transform(scaleX, scaleY, offsetX, offsetY);
var newRegion = myRegion.translate(offsetX, offsetY);
var newRegion = myRegion.scale(scaleX, scaleY);
Testing and comparison:
var bool = myRegion.isEmpty(); // O(1)
var bool = myRegion.isInfinite(); // O(1). True if any rect reaches +inf or -inf.
var bool = myRegion.isFinite(); // O(1). Opposite of isInfinite().
var bool = myRegion.isRectangular(); // O(1). True if region is exactly one rect.
var bool = myRegion.doesIntersect(yourRegion); // O(n+m)
var bool = myRegion.relate(yourRegion); // O(n+m): '', 'intersect', 'a-contain-b', 'equal'
var bool = myRegion.isPointIn(x); // O(lg n)
var bool = myRegion.equals(yourRegion); // O(n)
Data extraction:
var numberOfRects = myRegion.getCount(); // O(1)
var arrayOfRects = myRegion.getRects(); // Returns a copy, not the original rects.
var rect = myRegion.getBounds(); // O(1)
var arrayOfPolygons = myRegion.getPath(); // Array of arrays of {x:,y:} points.
var hashCode = myRegion.getHashCode(); // O(1)
var rawRows = myRegion.getRawRows(); // O(n), where n is the number of rows.
Static instances:
var nothing = Region2D.empty;
var everything = Region2D.infinite;
Region1D usage
This library also includes an implementation of Region1D
, which is used internally by Region2D
but can be useful in its own right. A Region1D
is an opaque object that represents a set of points on the number line, and is always composed of a series of nonoverlapping nonadjacent [start,end) pairs.
Construction:
var myRegion = new Region1D([span1Min, span1Max, span2Min, span2Max, span3Min, span3Max, ...]);
1-D regions are composed of spans of included content. Span endpoints are of the form [min, max). The minima and maxima of a span may include either positive or negative infinity. Spans must not overlap or adjoin, and must appear in strictly ascending order. All 1-D regions are immutable once constructed.
There is also a global Region1D.empty
static instance available, which consists of no spans.
Region1D
is designed to be reasonably efficient: All Region1D
operations run in O(n) time, except for the binary operations (which run in O(n+m) time), and for a few operations that are O(1) or O(lg n), as noted below.
Region1D includes many operations for manipulating its set of points:
Set-theoretic operations:
var newRegion = myRegion.union(yourRegion);
var newRegion = myRegion.intersect(yourRegion);
var newRegion = myRegion.xor(yourRegion);
var newRegion = myRegion.subtract(yourRegion);
var newRegion = myRegion.not();
Transformation operations:
var newRegion = myRegion.transform(scale, offset);
var newRegion = myRegion.translate(offset);
var newRegion = myRegion.scale(scale);
Testing and comparison:
var bool = myRegion.isEmpty(); // O(1)
var bool = myRegion.isPointIn(x); // O(lg n)
var bool = myRegion.doesIntersect(yourRegion); // O(n+m)
var bool = myRegion.relate(yourRegion); // O(n+m): '', 'intersect', 'a-contain-b', 'equal'
var bool = myRegion.equals(yourRegion); // O(n)
Data extraction:
var numberOfSpans = myRegion.getCount(); // O(1)
var arrayOfRects = myRegion.getAsRects(minY, maxY);
var arrayOfSpans = myRegion.getRawSpans(); // Returns a copy, not the original spans.
var minAndMax = myRegion.getBounds(); // O(1)
var hashCode = myRegion.getHashCode(); // O(1)
Static instances:
var nothing = Region1D.empty;
Implementation Details
Overview
This implementation uses the banded rectangles technique, which is used in many implementations of X Windows, and which was chosen for its speed.
Each Region2D
is conceptually represented as a set of nonoverlapping rectangles, where no rectangle may have a minimum or maximum Y coordinate between any other rectangle's minimum or maximum Y coordinate. Thus the rectangles effectively form horizontal bands, where all of the rectangles in a given band have the same minimum and maximum Y coordinate. In Region2D
, each band is implemented as a simple object of the form { region:, minY:, maxY: }
, where the region
property represents the rectangles but is actually a Region1D
object. The bands are stored in an array, and are always in strictly ascending Y-coordinate order.
While banded rectangles do not always result in the fewest possible number of rectangles to represent a region, they allow set-theoretic operations to be performed very simply and quickly: To union, intersect, subtract, or exclusive-or any two regions, you need only line up those regions' bands where they overlap, and apply Region1D
operations on each pair of bands to produce the result. (There are considerable details to make that work reliably and efficiently, but that is the basic idea.)
It also comes with the nice side effect that a readout of all rectangles in the region will always have coordinates that read top-to-bottom, left-to-right, which can be useful for some applications.
Invariants
Certain invariants are always maintained for a Region2D
's bands:
- Bands are always in sorted order of ascending Y coordinate.
- No band may ever be empty (i.e., empty bands must be discarded).
- No band may have a minimum Y or maximum Y between the minimum Y and maximum Y of another band (i.e., bands may not overlap).
- Two successive bands may not have identical rectangles if the minimum Y of one band matches the maximum Y of another (i.e., identical bands must be coalesced).
Within each band, since its rectangles are implemented as a Region1D
, the Region1D
invariants also hold for the band's rectangles:
- Rectangles must be in strictly sorted order of ascending X coordinates.
- No rectangle's maximum X may be greater than or equal to the minimum X of its successor (i.e., rectangles must not be directly adjacent or overlapping).
Performance
Using the banded rectangles design ensures that:
- All binary operations run in a worst-case time of O(n+m).
- All unary operations run in a worst-case time of O(n).
- Some operations (such as a point-test) can run in O(lg n) time.
However, this speed does come at a cost in space, in that Region2D
may (in a pathological case) require O(n^2) rectangles compared to an optimal representation of the same region.
But in normal scenarios, Region2D
requires between n and 2*n rectangles compared to an optimal representation of the same region, and is much, much faster than an optimal representation. (Region2D
requires O(n+m) time for most operations, whereas the optimal representation typically requires O(n*m) time.)
Prior Art
This pure-JavaScript Region2D
is comparable in functionality to many similar data structures in other environments:
Region
in X WindowsGdkRegion
in GDK (Gnome)HRGN
in Microsoft WindowsSystem.Drawing.Region
in .NET- The region handle in classic Mac OS (Carbon) programming.
This implementation is missing some features common to other implementations:
- Creation of a region from a polygon, from a Bézier curve, or from an arbitrary clipping path
- Non-axis-aligned region boundaries
- Direct (efficient) intersection/containment testing of a rectangle against a region
- Direct (efficient) unioning of a rectangle to a region
- Direct (efficient) creation of a region from a set of many rectangles
License
This library is licensed under the Apache 2.0 open-source license, which basically means:
- It's free, and you can -
- Do what you want with it, but -
- Don't claim you wrote it, and -
- Don't complain if it breaks.