Given this object, i wan't to merge all possible start and endpoints with a distance of x, thus creating three paths given below objects. The function only seems to see half of the connections.
The model below would output three elements in maker js using chaining, i wan't to recreate that.
How could i improve this function?
let mergedPaths = [
{
"id": 2,
"path": "M 19.8279000000 0.0000000000L -19.8300000000 0.0000000000",
"startPoint": {
"x": "19.8279000000",
"y": "0.0000000000",
},
"endPoint": {
"x": "-19.8300000000",
"y": "0.0000000000"
}
},
{
"id": 3,
"path": "M 24.8250000000 -5.1691000000L 24.8230000000 -5.1691000000",
"startPoint": {
"x": "24.8250000000",
"y": "-5.1691000000",
},
"endPoint": {
"x": "24.8230000000",
"y": "-5.1691000000",
}
},
{
"id": 4,
"path": "M -17.9684000000 -65.0000000000L 17.9664000000 -65.0000000000",
"startPoint": {
"x": "-17.9684000000",
"y": "-65.0000000000",
},
"endPoint": {
"x": "17.9664000000",
"y": "-65.0000000000",
}
},
{
"id": 5,
"path": "M -24.8271000000 -5.1691000000L -22.9656000000 -60.1691000000",
"startPoint": {
"x": "-24.8271000000",
"y": "-5.1691000000",
},
"endPoint": {
"x": "-22.9656000000",
"y": "-60.1691000000",
}
},
{
"id": 6,
"path": "M 22.9615000000 -60.1691000000L 24.8230000000 -5.1691000000",
"startPoint": {
"x": "22.9615000000",
"y": "-60.1691000000",
},
"endPoint": {
"x": "24.8230000000",
"y": "-5.1691000000",
}
},
{
"id": 7,
"path": "M 22.9615000000 -60.1691000000L 22.9635000000 -60.1691000000L 22.9635000000 -60.1691000000L 24.8250000000 -5.1691000000L 24.8250000000 -5.1691000000A 5.0000000000 5.0000000000 0 0 1 19.8279000000 0.0000000000",
"startPoint": {
"x": "22.9615000000",
"y": "-60.1691000000",
},
"endPoint": {
"x": "19.8279000000",
"y": "0.0000000000",
}
},
{
"id": 8,
"path": "M 24.8230000000 -5.1691000000A 5.0000000000 5.0000000000 0 0 1 19.8259000000 0.0000000000",
"startPoint": {
"x": "24.8230000000",
"y": "-5.1691000000",
},
"endPoint": {
"x": "19.8259000000",
"y": "0.0000000000",
}
},
{
"id": 9,
"path": "M 17.9643000000 -65.0000000000A 5.0000000000 5.0000000000 0 0 1 22.9615000000 -60.1691000000",
"startPoint": {
"x": "17.9643000000",
"y": "-65.0000000000",
},
"endPoint": {
"x": "22.9615000000",
"y": "-60.1691000000",
}
},
{
"id": 10,
"path": "M -22.9656000000 -60.1691000000A 5.0000000000 5.0000000000 0 0 1 -17.9684000000 -65.0000000000",
"startPoint": {
"x": "-22.9656000000",
"y": "-60.1691000000",
},
"endPoint": {
"x": "-17.9684000000",
"y": "-65.0000000000",
}
},
{
"id": 11,
"path": "M -19.8300000000 0.0000000000A 5.0000000000 5.0000000000 0 0 1 -24.8271000000 -5.1691000000",
"startPoint": {
"x": "-19.8300000000",
"y": "0.0000000000",
},
"endPoint": {
"x": "-24.8271000000",
"y": "-5.1691000000",
}
},
{
"id": 12,
"path": "M 17.9664000000 -65.0000000000A 5.0000000000 5.0000000000 0 0 1 22.9635000000 -60.1691000000",
"startPoint": {
"x": "17.9664000000",
"y": "-65.0000000000",
},
"endPoint": {
"x": "22.9635000000",
"y": "-60.1691000000",
}
},
{
"id": 13,
"path": "M 0.0000000000 -48.7500000000A 1.2500000000 1.2500000000 0 0 1 0.0000000000 -51.2500000000",
"startPoint": {
"x": "0.0000000000",
"y": "-48.7500000000",
},
"endPoint": {
"x": "0.0000000000",
"y": "-51.2500000000",
}
}
]
let pointMatchingDistance = 1;
getDistance = (x1: number, x2: number, y1: number, y2: number) => {
let y = x2 - x1;
let x = y2 - y1;
return Math.sqrt(x * x y * y);
}
for (let mergedPath of mergedPaths) {
for (let mergedPathCheck of mergedPaths) {
if (!mergedPathCheck.mergedWith && !mergedPath.mergedWith) {
let distanceStartToEndCheck = this.getDistance(
mergedPathCheck.endPoint?.x,
mergedPath.startPoint?.x,
mergedPathCheck.endPoint?.y,
mergedPath.startPoint?.y,
);
if (distanceStartToEndCheck <= pointMatchingDistance) {
mergedPaths = mergedPaths.map((mp) => {
return mp.id == mergedPath.id ? {
...mp,
path: mergedPathCheck.path mergedPath.path.replace("M", "L"),
startPoint: mergedPathCheck.startPoint,
mergedWith: mergedPathCheck.id
} : mp
}
)
}
}
}
}
CodePudding user response：
I'll do something that is not very helpfull most of the time - show you a completely different code solving the same problem. But it's incidentally something that I have recently written, and that is relatively thoroughly tested by now.
It takes into account some special cases that might or might not be applicable to your data:
- No prior knowledge about the order of the paths in the collection. A path to be "stitched" to another one may be earlier or later in the array.
- No prior knowledge whether successfull stitching will involve matching
path1.endPointtopath2.startPointorpath2.endPointtopath1.startPoint. - Stitching might even only be possible if you match
path1.startPointtopath2.startPointorpath1.endPointtopath2.endPoint, which means you have to reverse the direction of one of the paths. - A path may close in on itself, when
path1.endPointandpath1.startPointare within matching distance (before or after stitching multiple paths together).
As you can see, there are a lot of cases how the paths might fit together, and probably your code missed some of them.
Another difference is that your code tests the condition
if (!mergedPathCheck.mergedWith && !mergedPath.mergedWith)
Since you are changing existing paths, this means that no more than two paths can ever be stitched together - a resulting path made up of three or more parts can never happen. My code works like this:
splice an original path off of the source array (called
heap), and add it to a target array (chains) as a new, unconnected pathrun through the
heapsearching for paths matching the last path inchains. If you find one, stitch it onto the path. and run 2. again.If you find none, go back to 1., until
heapis empty.
One method is missing: Chainer.prototype.reverse(path). My original code had the path data as collections of point objects, not as strings. Therefore I can't provide you with code for reversing a path string.
class Chainer {
chains = [];
pointMatchingDistance = 1;
constructor (heap) {
while (heap.length) {
const { id, path, startPoint, endPoint } = heap.shift();
// start a new ordered array of matching paths
const ordered = {
paths: [{d: path, startPoint, id}],
closed: this.matchPoints(first, startPoint, endPoint),
endPoint
};
// recursively add matching paths to the ordered array
this.findNext(ordered, heap, startPoint, endPoint);
// after no more matching paths are found,
// add the ordered array to chains
this.chains.push(ordered);
}
}
matchPoints(p1, p2) {
const y = p2.x - p1.x;
const x = p2.y - p1.y;
return Math.hypot(x, y) <= this.pointMatchingDistance;
}
reverse(path) {
// TBD
}
// splice a path off heap and reverse its direction if needed
getNext(heap, idx, reverse) {
const add = heap.splice(idx, 1)[0];
if (reverse) {
return {
...add,
path: this.reverse(add.path),
startPoint: add.endPoint,
endPoint: add.startPoint
};
} else {
return {...add};
}
}
// add the path at the end of ordered
addNext(ordered, nextWay) {
const { id, path, startPoint, endPoint } = nextWay;
ordered.paths.push({d: path, first, id});
ordered.endPoint = endPoint;
return endPoint;
}
// add the path at the start of ordered
addPrev(ordered, prevWay) {
const { id, path, startPoint, endPoint } = prevWay;
ordered.paths.unshift({d: path, startPoint, id});
return startPoint;
}
// search for a matching path in the heap and identify the direction
findNext(ordered, heap, startPoint, endPoint) {
let next, prev, reverseNext, reversePrev;
for (const [idx, way] of heap.entries()) {
if(this.matchPoints(way.startPoint, endPoint)) {
next = idx;
break;
}
if (this.matchPoints(way.endPoint, startPoint)) prev = idx;
if (this.matchPoints(way.endPoint, endPoint)) reverseNext = idx;
if (this.matchPoints(way.startPoint, startPoint)) reversePrev = idx;
}
if (next !== undefined) {
endPoint = this.addNext(ordered, this.getNext(heap, next, false));
} else if (prev !== undefined) {
startPoint = this.addPrev(ordered, this.getNext(heap, prev, false));
} else if (reverseNext !== undefined) {
endPoint = this.addNext(ordered, this.getNext(heap, reverseNext, true));
} else if (reversePrev !== undefined) {
startPoint = this.addPrev(ordered, this.getNext(heap,reversePrev, true));
// if none of the matching criteria has been met, return
} else return;
// paths closing in on themselves can have no more matching paths
if (this.matchPoints(startPoint, endPoint)) {
ordered.closed = true;
return;
}
// try to find more matching paths
this.findNext(ordered, heap, startPoint, endPoint);
}
// take the ordered arrays in chains
// and join them to one path data string each
writePaths() {
return this.chains.map(ordered => {
let mergedPath;
ordered.paths.forEach(({d, id}) => {
if (mergedPath) {
mergedPath.d = d.replace("M", "L");
} else {
mergedPath = { d, id };
}
});
if (ordered.closed) mergedPath = "Z";
return mergedPath;
});
}
}
const chainer = new Chainer(paths);
const mergedPaths = chainer.writePaths();