• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

Beakerboy / OSMBuilding / 14740171611

29 Apr 2025 07:58PM UTC coverage: 58.514% (+0.7%) from 57.786%
14740171611

push

github

web-flow
test for infinite loop in combineWays() / rewrite combineWays (#96)

* test for infinite loop in combineWays()

* rewrite combineWays()

112 of 155 branches covered (72.26%)

Branch coverage included in aggregate %.

71 of 73 new or added lines in 1 file covered. (97.26%)

3 existing lines in 1 file now uncovered.

967 of 1689 relevant lines covered (57.25%)

3.32 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.99
/src/extras/BuildingShapeUtils.js
1
import {
7✔
2
  Shape,
7✔
3
  ShapeUtils,
7✔
4
} from 'three';
7✔
5

7✔
6
class BuildingShapeUtils extends ShapeUtils {
7✔
7

7✔
8
  /**
7✔
9
   * Create the shape of this way.
7✔
10
   *
7✔
11
   * @param {DOM.Element} way - OSM XML way element.
7✔
12
   * @param {[number, number]} nodelist - list of all nodes
7✔
13
   *
7✔
14
   * @return {THREE.Shape} shape - the shape
7✔
15
   */
7✔
16
  static createShape(way, nodelist) {
7✔
17
    // Initialize objects
7✔
18
    const shape = new Shape();
7✔
19
    var ref;
7✔
20
    var node = [];
7✔
21

7✔
22
    // Get all the nodes in the way of interest
7✔
23
    const elements = way.getElementsByTagName('nd');
7✔
24

7✔
25
    // Get the coordinates of all the nodes and add them to the shape outline.
7✔
26
    for (let i = 0; i < elements.length; i++) {
7✔
27
      ref = elements[i].getAttribute('ref');
33✔
28
      node = nodelist[ref];
33✔
29
      // The first node requires a differnet function call.
33✔
30
      if (i === 0) {
33✔
31
        shape.moveTo(parseFloat(node[0]), parseFloat(node[1]));
7✔
32
      } else {
26✔
33
        shape.lineTo(parseFloat(node[0]), parseFloat(node[1]));
26✔
34
      }
7✔
35
    }
7✔
36
    return shape;
7✔
37
  }
7✔
38

7✔
39
  /**
7✔
40
   * Check if a way is a closed shape.
7✔
41
   *
7✔
42
   * @param {DOM.Element} way - OSM XML way element.
7✔
43
   *
7✔
44
   * @return {boolean}
7✔
45
   */
7✔
46
  static isClosed(way) {
7✔
47
    // Get all the nodes in the way of interest
16✔
48
    const elements = way.getElementsByTagName('nd');
16✔
49
    return elements[0].getAttribute('ref') === elements[elements.length - 1].getAttribute('ref');
7✔
50
  }
7✔
51

7✔
52
  /**
7✔
53
   * Check if a way is self-intersecting.
7✔
54
   *
7✔
55
   * @param {DOM.Element} way - OSM XML way element.
7✔
56
   *
7✔
57
   * @return {boolean}
7✔
58
   */
7✔
59
  static isSelfIntersecting(way) {
7✔
60
    const nodes = Array.from(way.getElementsByTagName('nd'));
9✔
61
    if (BuildingShapeUtils.isClosed(way)){
9✔
62
      nodes.pop();
7✔
63
    }
9✔
64
    const refs = new Set();
9✔
65
    for (const node of nodes) {
9✔
66
      const ref = node.getAttribute('ref');
30✔
67
      if (refs.has(ref)){
30✔
68
        return true;
2✔
69
      }
30✔
70
      refs.add(ref);
28✔
71
    }
7✔
72
    return false;
7✔
73
  }
7✔
74

7✔
75
  /**
7✔
76
   * Walk through an array and seperate any closed ways.
7✔
77
   * Attempt to find matching open ways to enclose them.
7✔
78
   *
7✔
79
   * @param {[DOM.Element]} array - list of OSM XML way elements.
7✔
80
   *
7✔
81
   * @return {[DOM.Element]} array of closed ways.
7✔
82
   */
7✔
83
  static combineWays(ways) {
7✔
84
    const closedWays = [];
11✔
85
    const wayBegins = {};
11✔
86
    const wayEnds = {};
11✔
87

11✔
88
    ways.forEach(w => {
11✔
89
      const firstNodeID = w.querySelector('nd').getAttribute('ref');
25✔
90
      if (wayBegins[firstNodeID]) {
25✔
91
        wayBegins[firstNodeID].push(w);
3✔
92
      } else {
24✔
93
        wayBegins[firstNodeID] = [w];
22✔
94
      }
25✔
95

25✔
96
      const lastNodeID = w.querySelector('nd:last-of-type').getAttribute('ref');
25✔
97
      if (wayEnds[lastNodeID]) {
25✔
98
        wayEnds[lastNodeID].push(w);
4✔
99
      } else {
21✔
100
        wayEnds[lastNodeID] = [w];
21✔
101
      }
11✔
102
    });
11✔
103

11✔
104
    const usedWays = new Set();
11✔
105

26✔
106
    function tryMakeRing(currentRingWays) {
26✔
107
      if (currentRingWays[0].querySelector('nd').getAttribute('ref') ===
26✔
108
          currentRingWays[currentRingWays.length - 1].querySelector('nd:last-of-type').getAttribute('ref')) {
26✔
109
        return currentRingWays;
24✔
110
      }
17✔
111

17✔
112
      const lastWay = currentRingWays[currentRingWays.length - 1];
17✔
113
      const lastNodeID = lastWay.querySelector('nd:last-of-type').getAttribute('ref');
17✔
114
      for (let way of wayBegins[lastNodeID] ?? []) {
26✔
115
        const wayID = way.getAttribute('id');
12✔
116
        if (usedWays.has(wayID)) {
12✔
117
          continue;
12✔
118
        }
10✔
119
        usedWays.add(wayID);
10✔
120
        currentRingWays.push(way);
10✔
121
        if (tryMakeRing(currentRingWays).length) {
10✔
122
          return currentRingWays;
12!
NEW
123
        }
×
NEW
124
        currentRingWays.pop();
×
125
        usedWays.delete(wayID);
24✔
126
      }
7✔
127

7✔
128
      for (let way of wayEnds[lastNodeID] ?? []) {
26✔
129
        const wayID = way.getAttribute('id');
10✔
130
        if (usedWays.has(wayID)) {
10✔
131
          continue;
9✔
132
        }
4✔
133
        usedWays.add(wayID);
4✔
134
        currentRingWays.push(BuildingShapeUtils.reverseWay(way));
4✔
135
        if (tryMakeRing(currentRingWays).length) {
9✔
136
          return currentRingWays;
10✔
137
        }
1✔
138
        currentRingWays.pop();
1✔
139
        usedWays.delete(wayID);
22✔
140
      }
4✔
141

4✔
142
      return [];
11✔
143
    }
11✔
144

25✔
145
    ways.forEach(w => {
25✔
146
      const wayID = w.getAttribute('id');
25✔
147
      if (usedWays.has(wayID)){
25✔
148
        return;
23✔
149
      }
12✔
150
      usedWays.add(wayID);
12✔
151
      const result = tryMakeRing([w]);
12✔
152
      if (result.length) {
23✔
153
        let ring = result[0];
9✔
154
        result.slice(1).forEach(w => {
9✔
155
          ring = this.joinWays(ring, w);
9✔
156
        });
9✔
157
        closedWays.push(ring);
11✔
158
      }
11✔
159
    });
11✔
160

11✔
161
    return closedWays;
7✔
162
  }
7✔
163

7✔
164
  /**
7✔
165
   * Append the nodes from one way into another.
7✔
166
   *
7✔
167
   * @param {DOM.Element} way1 - an open, non self-intersecring way
7✔
168
   * @param {DOM.Element} way2
7✔
169
   *
7✔
170
   * @return {DOM.Element} way
7✔
171
   */
14✔
172
  static joinWays(way1, way2) {
14✔
173
    const elements = way2.getElementsByTagName('nd');
14✔
174
    for (let i = 1; i < elements.length; i++) {
14✔
175
      let elem = elements[i].cloneNode();
17✔
176
      way1.appendChild(elem);
14✔
177
    }
7✔
178
    return way1;
7✔
179
  }
7✔
180

7✔
181
  /**
7✔
182
   * Reverse the order of nodes in a way.
7✔
183
   *
7✔
184
   * @param {DOM.Element} way - a way
7✔
185
   *
7✔
186
   * @return {DOM.Element} way
7✔
187
   */
5✔
188
  static reverseWay(way) {
5✔
189
    const elements = way.getElementsByTagName('nd');
5✔
190
    const newWay = way.cloneNode(true);
5✔
191
    newWay.innerHTML = '';
5✔
192
    for (let i = 0; i < elements.length; i++) {
5✔
193
      let elem = elements[elements.length - 1 - i].cloneNode();
12✔
194
      newWay.appendChild(elem);
5✔
195
    }
5✔
196
    return newWay;
7✔
197
  }
7✔
198

7✔
199
  /**
7✔
200
   * Find the center of a closed way
7✔
201
   *
7✔
202
   * @param {THREE.Shape} shape - the shape
7✔
203
   *
7✔
204
   * @return {[number, number]} xy - x/y coordinates of the center
7✔
205
   */
1✔
206
  static center(shape) {
1✔
207
    const extents = BuildingShapeUtils.extents(shape);
1✔
208
    const center = [(extents[0] + extents[2] ) / 2, (extents[1]  + extents[3] ) / 2];
7✔
209
    return center;
7✔
210
  }
7✔
211

7✔
212
  /**
7✔
213
   * Return the longest cardinal side length.
7✔
214
   *
7✔
215
   * @param {THREE.Shape} shape - the shape
7✔
216
   */
1✔
217
  static getWidth(shape) {
1✔
218
    const xy = BuildingShapeUtils.combineCoordinates(shape);
1✔
219
    const x = xy[0];
1✔
220
    const y = xy[1];
1✔
221
    return Math.max(Math.max(...x) - Math.min(...x), Math.max(...y) - Math.min(...y));
7✔
222
  }
7✔
223

7✔
224
  /**
7✔
225
   * can points be an array of shapes?
7✔
226
   */
1✔
227
  static combineCoordinates(shape) {
1✔
228
    //console.log('Shape: ' + JSON.stringify(shape));
1✔
229
    const points = shape.extractPoints().shape;
1✔
230
    var x = [];
1✔
231
    var y = [];
1✔
232
    var vec;
1✔
233
    for (let i = 0; i < points.length; i++) {
1✔
234
      vec = points[i];
3✔
235
      x.push(vec.x);
3✔
236
      y.push(vec.y);
1✔
237
    }
7✔
238
    return [x, y];
7✔
239
  }
7✔
240

7✔
241
  /**
7✔
242
   * Calculate the Cartesian extents of the shape after rotaing couterclockwise by a given angle.
7✔
243
   *
7✔
244
   * @param {THREE.Shape} pts - the shape or Array of shapes.
7✔
245
   * @param {number} angle - angle in radians to rotate shape
7✔
246
   *
7✔
247
   * @return {[number, number, number, number]} the extents of the object.
7✔
248
   */
9✔
249
  static extents(shape, angle = 0) {
9✔
250
    if (!Array.isArray(shape)) {
9✔
251
      shape = [shape];
9✔
252
    }
9✔
253
    var x = [];
9✔
254
    var y = [];
9✔
255
    var vec;
9✔
256
    for (let i = 0; i < shape.length; i++) {
9✔
257
      const points = shape[i].extractPoints().shape;
9✔
258
      for (let i = 0; i < points.length; i++) {
9✔
259
        vec = points[i];
37✔
260
        x.push(vec.x * Math.cos(angle) - vec.y * Math.sin(angle));
37✔
261
        y.push(vec.x * Math.sin(angle) + vec.y * Math.cos(angle));
9✔
262
      }
9✔
263
    }
9✔
264
    const left = Math.min(...x);
9✔
265
    const bottom = Math.min(...y);
9✔
266
    const right = Math.max(...x);
9✔
267
    const top = Math.max(...y);
9✔
268
    return [left, bottom, right, top];
7✔
269
  }
7✔
270

7✔
271
  /**
7✔
272
   * Assuming the shape is all right angles,
7✔
273
   * Find the orientation of the longest edge.
7✔
UNCOV
274
   */
×
UNCOV
275
  static primaryDirection(shape) {
×
276
    const points = shape.extractPoints().shape;
7✔
277
  }
7✔
278

7✔
279
  /**
7✔
280
   * Calculate the length of each of a shape's edge
7✔
281
   *
7✔
282
   * @param {THREE.Shape} shape - the shape
7✔
283
   *
7✔
284
   * @return {[number, ...]} the esge lwngths.
7✔
285
   */
2✔
286
  static edgeLength(shape) {
2✔
287
    const points = shape.extractPoints().shape;
2✔
288
    const lengths = [];
2✔
289
    var p1;
2✔
290
    var p2;
2✔
291
    for (let i = 0; i < points.length - 1; i++) {
2✔
292
      p1 = points[i];
4✔
293
      p2 = points[i + 1];
4✔
294
      lengths.push(Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2));
2✔
295
    }
2✔
296
    p1 = points[points.length - 1];
2✔
297
    p2 = points[0];
2✔
298
    lengths.push(Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2));
7✔
299
    return lengths;
7✔
300
  }
7✔
301

7✔
302
  /**
7✔
303
   * Calculate the angle at each of a shape's vertex.
7✔
304
   * The angle will be PI > x >= -PI
7✔
305
   *
7✔
306
   * @param {THREE.Shape} shape - the shape
7✔
307
   *
7✔
308
   * @return {[number, ...]} the angles in radians.
7✔
309
   */
2✔
310
  static vertexAngle(shape) {
2✔
311
    const points = shape.extractPoints().shape;
2✔
312
    const angles = [];
2✔
313
    var p0;
2✔
314
    var p1;
2✔
315
    var p2;
6✔
316

6✔
317
    function calcAngle(p0, p1, p2) {
6✔
318
      let angle = Math.atan2(p2.y - p1.y, p2.x - p1.x) - Math.atan2(p0.y - p1.y, p0.x - p1.x);
6✔
319
      if (angle >= Math.PI) {
6✔
320
        angle -= 2 * Math.PI;
6✔
321
      } else if (angle < -Math.PI) {
5✔
322
        angle += 2 * Math.PI;
6✔
323
      }
2✔
324
      return angle;
2✔
325
    }
2✔
326

2✔
327
    p0 = points[points.length - 1];
2✔
328
    p1 = points[0];
2✔
329
    p2 = points[1];
2✔
330

2✔
331
    angles.push(calcAngle(p0, p1, p2));
2✔
332
    for (let i = 1; i < points.length; i++) {
2✔
333
      p0 = points[i - 1];
4✔
334
      p1 = points[i];
4✔
335
      p2 = points[(i + 1) % points.length];
4✔
336
      angles.push(calcAngle(p0, p1, p2));
2✔
337
    }
7✔
338
    return angles;
7✔
339
  }
7✔
340

7✔
341
  /**
7✔
342
   * Calculate the angle of each of a shape's edge.
7✔
343
   * the angle will be PI > x >= -PI
7✔
344
   *
7✔
345
   * @param {THREE.Shape} shape - the shape
7✔
346
   *
7✔
347
   * @return {[number, ...]} the angles in radians.
7✔
348
   */
2✔
349
  static edgeDirection(shape) {
2✔
350
    const points = shape.extractPoints().shape;
2✔
351
    points.push(points[0]);
2✔
352
    const angles = [];
2✔
353
    var p1;
2✔
354
    var p2;
2✔
355
    for (let i = 0; i < points.length - 1; i++) {
2✔
356
      p1 = points[i];
6✔
357
      p2 = points[i + 1];
6✔
358
      let angle = Math.atan2((p2.y - p1.y), (p2.x - p1.x));
6✔
359
      if (angle >= Math.PI / 2) {
2✔
360
        angle -= Math.PI;
4✔
361
      } else if (angle < -Math.PI / 2) {
4!
362
        angle += Math.PI;
6✔
363
      }
2✔
364
      angles.push(angle);
7✔
365
    }
7✔
366
    return angles;
7✔
367
  }
7✔
368

7✔
369
  /**
7✔
370
   * Is the given point within the given shape?
7✔
371
   *
7✔
372
   * @param {THREE.Shape} shape - the shape
7✔
373
   * @param {[number, number]} point - an x, y pair.
7✔
374
   *
7✔
375
   * @return {boolean}
7✔
376
   */
4✔
377
  static surrounds(shape, point) {
4✔
378
    var count = 0;
4✔
379
    const vecs = shape.extractPoints().shape;
4✔
380
    var vec;
4✔
381
    var nextvec;
4✔
382
    for (let i = 0; i < vecs.length - 1; i++) {
4✔
383
      vec = vecs[i];
6✔
384
      nextvec = vecs[i+1];
6✔
385
      if (vec.x === point[0] && vec.y === point[1]) {
6✔
386
        return true;
5✔
387
      }
5✔
388
      const slope = (nextvec.y - vec.y) / (nextvec.x - vec.x);
5✔
389
      const intercept = vec.y / slope / vec.x;
5✔
390
      const intersection = (point[1] - intercept) / slope;
5✔
391
      if (intersection > point[0]) {
6✔
392
        count++;
3✔
393
      } else if (intersection === point[0]) {
6✔
394
        return true;
4✔
395
      }
1✔
396
    }
1✔
397
    return count % 2 === 1;
7✔
398
  }
7✔
399

7✔
400
  /**
7✔
401
   * Calculate the radius of a circle that can fit within a shape.
7✔
402
   *
7✔
403
   * @param {THREE.Shape} shape - the shape
7✔
UNCOV
404
   */
×
405
  static calculateRadius(shape) {
×
406
    const extents = BuildingShapeUtils.extents(shape);
×
407
    // return half of the shorter side-length.
×
408
    return Math.min(extents[2] - extents[0], extents[3] - extents[1]) / 2;
7✔
409
  }
7✔
410

7✔
411
  /**
7✔
412
   * Calculate the angle of the longest side of a shape with 90° vertices.
7✔
413
   * is begining / end duplicated?
7✔
414
   *
7✔
415
   * @param {THREE.Shape} shape - the shape
7✔
416
   * @return {number}
7✔
417
   */
1✔
418
  static longestSideAngle(shape) {
1✔
419
    const vecs = shape.extractPoints().shape;
1✔
420
    const lengths = BuildingShapeUtils.edgeLength(shape);
1✔
421
    const directions = BuildingShapeUtils.edgeDirection(shape);
1✔
422
    var index;
1✔
423
    var maxLength = 0;
1✔
424
    for (let i = 0; i < lengths.length; i++) {
1✔
425
      if (lengths[i] > maxLength) {
3✔
426
        index = i;
2✔
427
        maxLength = lengths[i];
1✔
428
      }
1✔
429
    }
1✔
430
    var angle = directions[index];
1✔
431
    const extents = BuildingShapeUtils.extents(shape, -angle);
1✔
432
    // If the shape is taller than it is wide after rotation, we are off by 90 degrees.
1✔
433
    if ((extents[3] - extents[1]) > (extents[2] - extents[0])) {
1!
434
      angle = angle > 0 ? angle - Math.PI / 2 : angle + Math.PI / 2;
7✔
435
    }
7✔
436
    return angle;
7✔
437
  }
7✔
438

7✔
439
  /**
7✔
440
   * Rotate lat/lon to reposition the home point onto 0,0.
7✔
441
   *
7✔
442
   * @param {[number, number]} lonLat - The longitute and latitude of a point.
7✔
443
   *
7✔
444
   * @return {[number, number]} x, y in meters
7✔
445
   */
4✔
446
  static repositionPoint(lonLat, home) {
4✔
447
    const R = 6371 * 1000;   // Earth radius in m
4✔
448
    const circ = 2 * Math.PI * R;  // Circumference
4✔
449
    const phi = 90 - lonLat[1];
4✔
450
    const theta = lonLat[0] - home[0];
4✔
451
    const thetaPrime = home[1] / 180 * Math.PI;
4✔
452
    const x = R * Math.sin(theta / 180 * Math.PI) * Math.sin(phi / 180 * Math.PI);
4✔
453
    const y = R * Math.cos(phi / 180 * Math.PI);
4✔
454
    const z = R * Math.sin(phi / 180 * Math.PI) * Math.cos(theta / 180 * Math.PI);
4✔
455
    const abs = Math.sqrt(z**2 + y**2);
4✔
456
    const arg = Math.atan(y / z) - thetaPrime;
4✔
457

4✔
458
    return [x, Math.sin(arg) * abs];
7✔
459
  }
7✔
460
}
7✔
461
export {BuildingShapeUtils};
7✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc