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;
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.