-
Notifications
You must be signed in to change notification settings - Fork 934
/
index.js
204 lines (179 loc) · 7.15 KB
/
index.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
import rbush from 'geojson-rbush';
import square from '@turf/square';
import bbox from '@turf/bbox';
import truncate from '@turf/truncate';
import lineSegment from '@turf/line-segment';
import lineIntersect from '@turf/line-intersect';
import nearestPointOnLine from '@turf/nearest-point-on-line';
import { getCoords, getType } from '@turf/invariant';
import { featureEach, featureReduce, flattenEach} from '@turf/meta';
import { lineString, featureCollection } from '@turf/helpers';
/**
* Split a LineString by another GeoJSON Feature.
*
* @name lineSplit
* @param {Feature<LineString>} line LineString Feature to split
* @param {Feature} splitter Feature used to split line
* @returns {FeatureCollection<LineString>} Split LineStrings
* @example
* var line = turf.lineString([[120, -25], [145, -25]]);
* var splitter = turf.lineString([[130, -15], [130, -35]]);
*
* var split = turf.lineSplit(line, splitter);
*
* //addToMap
* var addToMap = [line, splitter]
*/
function lineSplit(line, splitter) {
if (!line) throw new Error('line is required');
if (!splitter) throw new Error('splitter is required');
var lineType = getType(line);
var splitterType = getType(splitter);
if (lineType !== 'LineString') throw new Error('line must be LineString');
if (splitterType === 'FeatureCollection') throw new Error('splitter cannot be a FeatureCollection');
if (splitterType === 'GeometryCollection') throw new Error('splitter cannot be a GeometryCollection');
// remove excessive decimals from splitter
// to avoid possible approximation issues in rbush
var truncatedSplitter = truncate(splitter, {precision: 7});
switch (splitterType) {
case 'Point':
return splitLineWithPoint(line, truncatedSplitter);
case 'MultiPoint':
return splitLineWithPoints(line, truncatedSplitter);
case 'LineString':
case 'MultiLineString':
case 'Polygon':
case 'MultiPolygon':
return splitLineWithPoints(line, lineIntersect(line, truncatedSplitter));
}
}
/**
* Split LineString with MultiPoint
*
* @private
* @param {Feature<LineString>} line LineString
* @param {FeatureCollection<Point>} splitter Point
* @returns {FeatureCollection<LineString>} split LineStrings
*/
function splitLineWithPoints(line, splitter) {
var results = [];
var tree = rbush();
flattenEach(splitter, function (point) {
// Add index/id to features (needed for filter)
results.forEach(function (feature, index) {
feature.id = index;
});
// First Point - doesn't need to handle any previous line results
if (!results.length) {
results = splitLineWithPoint(line, point).features;
// Add Square BBox to each feature for GeoJSON-RBush
results.forEach(function (feature) {
if (!feature.bbox) feature.bbox = square(bbox(feature));
});
tree.load(featureCollection(results));
// Split with remaining points - lines might needed to be split multiple times
} else {
// Find all lines that are within the splitter's bbox
var search = tree.search(point);
if (search.features.length) {
// RBush might return multiple lines - only process the closest line to splitter
var closestLine = findClosestFeature(point, search);
// Remove closest line from results since this will be split into two lines
// This removes any duplicates inside the results & index
results = results.filter(function (feature) { return feature.id !== closestLine.id; });
tree.remove(closestLine);
// Append the two newly split lines into the results
featureEach(splitLineWithPoint(closestLine, point), function (line) {
results.push(line);
tree.insert(line);
});
}
}
});
return featureCollection(results);
}
/**
* Split LineString with Point
*
* @private
* @param {Feature<LineString>} line LineString
* @param {Feature<Point>} splitter Point
* @returns {FeatureCollection<LineString>} split LineStrings
*/
function splitLineWithPoint(line, splitter) {
var results = [];
// handle endpoints
var startPoint = getCoords(line)[0];
var endPoint = getCoords(line)[line.geometry.coordinates.length - 1];
if (pointsEquals(startPoint, getCoords(splitter)) ||
pointsEquals(endPoint, getCoords(splitter))) return featureCollection([line]);
// Create spatial index
var tree = rbush();
var segments = lineSegment(line);
tree.load(segments);
// Find all segments that are within bbox of splitter
var search = tree.search(splitter);
// Return itself if point is not within spatial index
if (!search.features.length) return featureCollection([line]);
// RBush might return multiple lines - only process the closest line to splitter
var closestSegment = findClosestFeature(splitter, search);
// Initial value is the first point of the first segments (beginning of line)
var initialValue = [startPoint];
var lastCoords = featureReduce(segments, function (previous, current, index) {
var currentCoords = getCoords(current)[1];
var splitterCoords = getCoords(splitter);
// Location where segment intersects with line
if (index === closestSegment.id) {
previous.push(splitterCoords);
results.push(lineString(previous));
// Don't duplicate splitter coordinate (Issue #688)
if (pointsEquals(splitterCoords, currentCoords)) return [splitterCoords];
return [splitterCoords, currentCoords];
// Keep iterating over coords until finished or intersection is found
} else {
previous.push(currentCoords);
return previous;
}
}, initialValue);
// Append last line to final split results
if (lastCoords.length > 1) {
results.push(lineString(lastCoords));
}
return featureCollection(results);
}
/**
* Find Closest Feature
*
* @private
* @param {Feature<Point>} point Feature must be closest to this point
* @param {FeatureCollection<LineString>} lines Collection of Features
* @returns {Feature<LineString>} closest LineString
*/
function findClosestFeature(point, lines) {
if (!lines.features.length) throw new Error('lines must contain features');
// Filter to one segment that is the closest to the line
if (lines.features.length === 1) return lines.features[0];
var closestFeature;
var closestDistance = Infinity;
featureEach(lines, function (segment) {
var pt = nearestPointOnLine(segment, point);
var dist = pt.properties.dist;
if (dist < closestDistance) {
closestFeature = segment;
closestDistance = dist;
}
});
return closestFeature;
}
/**
* Compares two points and returns if they are equals
*
* @private
* @param {Array<number>} pt1 point
* @param {Array<number>} pt2 point
* @returns {boolean} true if they are equals
*/
function pointsEquals(pt1, pt2) {
return pt1[0] === pt2[0] && pt1[1] === pt2[1];
}
export default lineSplit;