Public
Edited
Sep 12, 2020
{
// parameters
const segmentCount = 5;
const densificationLength = 0.1;
const set1 = randomSegments(segmentCount);
const set2 = randomSegments(segmentCount);
// my own algorithm
let start = performance.now();
const dSet1 = densifyAll(set1, densificationLength);
const dSet2 = densifyAll(set2, densificationLength);
const hOwn = maxHausdorffDistance(dSet1, dSet2);
let end = performance.now();
const ownTime = end - start;
// jsts
start = performance.now();
const reader = new jsts.io.WKTReader();
const mls1 = reader.read(toMultiLineString(set1));
const mls2 = reader.read(toMultiLineString(set2));
const hJsts = jsts.algorithm.distance.DiscreteHausdorffDistance.distance(mls1, mls2, 0.1);
end = performance.now();
const jstsTime = end - start;
return md`
| Comparison | |
|-|-|
| Own Algorithm Time | ${ownTime.toFixed(2)} ms |
| JSTS Time | ${jstsTime.toFixed(2)} ms |
| Segment Count | ${segmentCount} |
| Densification Length | ${densificationLength} |
| Distance (own) | ${hOwn} |
| Distance (JSTS) | ${hJsts} |
`;
}
{
// parameters
const segmentCount = 500;
const densificationLength = 0.01;
const set1 = randomSegments(segmentCount);
const set2 = randomSegments(segmentCount);
// jsts
const start = performance.now();
const reader = new jsts.io.WKTReader();
const mls1 = reader.read(toMultiLineString(set1));
const mls2 = reader.read(toMultiLineString(set2));
const hJsts = jsts.algorithm.distance.DiscreteHausdorffDistance.distance(mls1, mls2, 0.1);
const end = performance.now();
const jstsTime = end - start;
return md`
| JSTS algorithm | |
|-|-|
| JSTS Time | ${jstsTime.toFixed(2)} ms |
| Segment Count | ${segmentCount} |
| Densification Length | ${densificationLength} |
| Distance (JSTS) | ${hJsts} |
`;
}
{
/*
A = LINESTRING (0 0, 100 0, 10 100, 10 100)
B = LINESTRING (0 100, 0 10, 80 10)
DHD(A, B) = 22.360679774997898
HD(A, B) ~= 47.8
*/
const set1 = [
s(v(0, 0), v(100, 0)),
s(v(100, 0), v(10, 100)),
s(v(10, 100), v(10, 100)),
];
const set2 = [
s(v(0, 100), v(0, 10)),
s(v(0, 10), v(80, 10)),
];
const dSet1 = densifyAll(set1, 0.1);
const dSet2 = densifyAll(set2, 0.1);
const h = maxHausdorffDistance(dSet1, dSet2);
const hJsts = jstsHausdorffDistance(set1, set2, 0.1);
return {
hOwn: h,
hJsts
}
}
{
const set1 = [
s(v(1, 0), v(0, 1)),
s(v(0, 1), v(0, 2)),
s(v(0, 2), v(1, 3)),
];
const set2 = [
s(v(1, 0), v(0, 1)),
s(v(0, 2), v(1, 3)),
];
const dSet1 = densifyAll(set1, 0.1);
const dSet2 = densifyAll(set2, 0.1);
const h = maxHausdorffDistance(dSet1, dSet2);
const hJsts = jstsHausdorffDistance(set1, set2, 0.01);
return createFigure(dSet1, dSet2, h, hJsts);
}
{
const set1 = [
s(v(1, 0), v(0, 1)),
s(v(0, 1), v(0, 2)),
s(v(0, 2), v(1, 3)),
];
const set2 = set1.map(seg => {
return s(v(seg.p1.x + 0.1, seg.p1.y + 0.1), v(seg.p2.x + 0.1, seg.p2.y + 0.1))
});
const dSet1 = densifyAll(set1, 0.1);
const dSet2 = densifyAll(set2, 0.1);
const h = maxHausdorffDistance(dSet1, dSet2);
const hJsts = jstsHausdorffDistance(set1, set2, 0.1);
return createFigure(dSet1, dSet2, h, hJsts);
}
{
while (true) {
yield new Promise(resolve => {
setTimeout(() => resolve(createRandomizedFigure()), 1000);
});
}
}
function createRandomizedFigure() {
const set1 = [
s(v(1, 0), v(0, 1)),
s(v(0, 1), v(0, 2)),
s(v(0, 2), v(1, 3)),
];
const dSet1 = densifyAll(set1, 0.1);
const set2 = randomizeSegments(set1);
const dSet2 = densifyAll(set2, 0.1);
const h = maxHausdorffDistance(dSet1, dSet2);
const hJsts = jstsHausdorffDistance(set1, set2, 0.1);
return createFigure(dSet1, dSet2, h, hJsts);
}
{
const set1 = [
s(v(1, 0), v(0, 1)),
s(v(0, 1), v(0, 2)),
s(v(0, 2), v(1, 3)),
];
const set2 = [
s(v(1, 0), v(0, 1)),
s(v(0, 2), v(1, 3)),
];
return {
set1: toMultiLineString(set1),
set2: toMultiLineString(set2)
}
}
function toMultiLineString(segments) {
return 'MULTILINESTRING (' +
segments.map(s => `(${s.p1.x} ${s.p1.y}, ${s.p2.x} ${s.p2.y})`).join(',')
+ ')';
}
function jstsHausdorffDistance(set1, set2, densifyFrac) {
const reader = new jsts.io.WKTReader();
const mls1 = reader.read(toMultiLineString(set1));
const mls2 = reader.read(toMultiLineString(set2));
const h = jsts.algorithm.distance.DiscreteHausdorffDistance.distance(mls1, mls2, densifyFrac);
return h;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
