Skip to content

Commit f2cd893

Browse files
lehnilehni
committed
Implement simpler strategy to iteratively find nearest points on paths.
Based on method described on http://pomax.github.io/bezierinfo/
1 parent fa34ea5 commit f2cd893

3 files changed

Lines changed: 132 additions & 0 deletions

File tree

‎examples/Scripts/NearestPoint.html‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
<!DOCTYPE html>
2+
<html>
3+
<head>
4+
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
5+
<title>NearestPoint</title>
6+
<link rel="stylesheet" href="../css/style.css">
7+
<script type="text/javascript" src="../../dist/paper.js"></script>
8+
<script type="text/paperscript" canvas="canvas">
9+
window.performance = window.performance || {};
10+
performance.now = (function() {
11+
return performance.now ||
12+
performance.mozNow ||
13+
performance.msNow ||
14+
performance.oNow ||
15+
performance.webkitNow ||
16+
function() { return new Date().getTime(); };
17+
})();
18+
19+
var path = project.importSVG(document.getElementById('svg')).firstChild,
20+
total = 0,
21+
slower = 0;
22+
23+
function getNearest(point) {
24+
var t1 = performance.now();
25+
var loc1 = path.getNearestLocation(point);
26+
t1 = performance.now() - t1;
27+
var t2 = performance.now();
28+
var loc2 = path._getNearestLocation(point);
29+
t2 = performance.now() - t2;
30+
total++;
31+
if (t2 > t1) {
32+
slower++;
33+
console.log('slower', slower / total, t1, t2, point)
34+
}
35+
if (loc2.distance > loc1.distance) {
36+
console.log('not precise');
37+
}
38+
return [loc1.point, loc2.point];
39+
}
40+
41+
for (var i = 0; i < 1000; i++) {
42+
getNearest(new Point(1028, 286));
43+
}
44+
/*
45+
*/
46+
47+
function onMouseMove(event) {
48+
var res = getNearest(event.point);
49+
console.log(res.join());
50+
var circle = new Path.Circle({
51+
center: res[0],
52+
radius: 2,
53+
strokeColor: 'red'
54+
}).removeOnMove();
55+
var line = new Path.Line({
56+
from: res[0],
57+
to: event.point,
58+
strokeColor: 'red'
59+
}).removeOnMove();
60+
var circle = new Path.Circle({
61+
center: res[1],
62+
radius: 4,
63+
strokeColor: 'green'
64+
}).removeOnMove();
65+
}
66+
</script>
67+
</head>
68+
<body>
69+
<canvas id="canvas" resize></canvas>
70+
<svg id="svg" version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px" xml:space="preserve" style="display: none;">
71+
<path fill="none" stroke="#000000" stroke-miterlimit="10" d="M167,265c33.321,23.568,53,38,72.886,109.353
72+
c22.516,80.792-52.284,163.541-74.631,92.135C95,242,393.045,246.871,399.326,431.434C402,510,286.311,474.239,289,369
73+
c1.961-76.747,78.663-125.069,162.393-91.026C540,314,562.299,442.872,476.159,390.783C424.547,359.573,382.365,317.41,383,221"/>
74+
</svg>
75+
</body>
76+
</html>

‎src/path/Curve.js‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1246,6 +1246,48 @@ new function() { // Scope for methods that require numerical integration
12461246
Math.sqrt(minDist));
12471247
},
12481248

1249+
_getNearestLocation: function(point) {
1250+
var values = this.getValues(),
1251+
step = 1 / 100,
1252+
minDist = Infinity,
1253+
minT = 0;
1254+
1255+
for (var t = 0; t <= 1; t += step) {
1256+
var pt = Curve.evaluate(values, t, true, 0),
1257+
dist = point.getDistance(pt, true);
1258+
if (dist < minDist) {
1259+
minDist = dist;
1260+
minT = t;
1261+
}
1262+
}
1263+
1264+
function refine(t, dist, precision) {
1265+
if(precision < 0.0000001) return t;
1266+
// refinement
1267+
// smaller distances?
1268+
var t1 = t - precision;
1269+
if (t1 >= 0) {
1270+
var dist1 = point.getDistance(
1271+
Curve.evaluate(values, t1, true, 0), true);
1272+
if (dist1 < dist)
1273+
return refine(t1, dist1, precision);
1274+
}
1275+
var t2 = t + precision;
1276+
if (t2 <= 1) {
1277+
var dist2 = point.getDistance(
1278+
Curve.evaluate(values, t2, true, 0), true);
1279+
if (dist2 < dist)
1280+
return refine(t2, dist2, precision);
1281+
}
1282+
// larger distances
1283+
return refine(t, dist, precision / 2);
1284+
}
1285+
1286+
minT = refine(minT, minDist, step);
1287+
var pt = Curve.evaluate(values, minT, true, 0);
1288+
return new CurveLocation(this, minT, pt, null, point.getDistance(pt));
1289+
},
1290+
12491291
getNearestPoint: function(point) {
12501292
return this.getNearestLocation(point).getPoint();
12511293
}

‎src/path/Path.js‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1552,6 +1552,20 @@ var Path = this.Path = PathItem.extend(/** @lends Path# */{
15521552
return minLoc;
15531553
},
15541554

1555+
_getNearestLocation: function(point) {
1556+
var curves = this.getCurves(),
1557+
minDist = Infinity,
1558+
minLoc = null;
1559+
for (var i = 0, l = curves.length; i < l; i++) {
1560+
var loc = curves[i]._getNearestLocation(point);
1561+
if (loc._distance < minDist) {
1562+
minDist = loc._distance;
1563+
minLoc = loc;
1564+
}
1565+
}
1566+
return minLoc;
1567+
},
1568+
15551569
/**
15561570
* Returns the nearest point on the path to the specified point.
15571571
*

0 commit comments

Comments
 (0)