bug for splay tree remove

[daozlv]

try this data with your union function
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "Polygon",
"coordinates": [
[
[
12956637.46,
4852235.26
],
[
12956637.46,
4852235.1
],
[
12956638.96,
4852235.1
],
[
12956638.96,
4852235.26
],
[
12956637.46,
4852235.26
]
]
]
}
},
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "Polygon",
"coordinates": [
[
[
12956637.48,
4852235.26
],
[
12956637.46,
4852235.1
],
[
12956638.95,
4852234.93
],
[
12956638.96,
4852235.1
],
[
12956637.48,
4852235.26
]
]
]
}
},
{
"type": "Feature",
"properties": {},
"geometry": {
"type": "Polygon",
"coordinates": [
[
[
12956637.48,
4852235.26
],
[
12956637.44,
4852234.94
],
[
12956638.92,
4852234.76
],
[
12956638.96,
4852235.1
],
[
12956637.48,
4852235.26
]
]
]
}
}
]
}

In your sweep-line.js. By using splayTree.remove, You want to remove the remove a node from the tree. However, it seems like splayTree.remove will sometimes remove more than one node from the tree.

Here is the remove function of splay tree.

private _remove (
i:Key, t:Node<Key, Value>,
comparator:Comparator) : Node<Key, Value> {
let x;
if (t === null) return null;
t = splay(i, t, comparator);
const cmp = comparator(i, t.key);
if (cmp === 0) { /* found it /
if (t.left === null) {
x = t.right;
} else {
x = splay(i, t.left, comparator);
x.right = t.right; // THERE MIGHT BE THE BUG
}
this._size--;
return x;
}
return t; / It wasn't there */
}

Remove function rebuild the tree Every time, but it is possible that the right of the new tree is not empty. Such that, when the right of the new tree is not empty, t.right overwrite the new right tree, and more than one node is removed.

You used remove function several times in you project, I hope you can check every one of it.

[daozlv]

I think the reason is split will change the reference of segment but you didn't maintain the structure of the tree. Such that the remove function of the tree goes wrong