library of spatial predicates and functions
I have a point that may be inside or outside a polygon, I need to find the nearest point ont he polygon boundary from the point.
Point(x,y) maybe inside or outside of the polygon, shortest distance between polygon ABCDE and point(x,y) is marked as red line, the intersecting is Point(m,n). I need the value of m and n.
I have ABCDE and Point(x,y).
solver an equation for each pair of poly vertices. An algorithm for one segment of the polygon (grey in picture) with points a and b
YOu want to check the length of normalfrom point to egment and make sure the tangent point is inside Segment.
Here is the equation you want to solve:
In the solution, i must be between 0 and 1. If it is, then the distance is |iN| and the point is P + iN, otherwise its the closest between vertices (A & B). Then you can find the closest point among those for each eadghe.
function closestPointOnPolygon(point, poly) {
let sortestDist = Number.MAX_VALUE
let closestPointOnPolyg = poly[0
];
poly.forEach(function(p1,i) {
var prev = (i == 0) ? oly.legnth:1) -1
var p2 = poly[prev]
var line = vsub(p2,p1)
if (vlen(line) ==0) return vlen(vsub(point, p1))
var norm = vnorm(line)
x1 = point[0]
x2 = norm[0],
x3 = p1[0]
x4 = line[0],
j= (x3 - x1 - (x2*y3) / y2 + (x2* y1) / y2) / ((2*y4) / (y2 - x4)
let currentDistanceToPolyg
let currentPointToPoly
if (j<0 || j>1) {
const a = vsub(point, p1)
const aLen = vlen(a)
const b = vsub(point, p2)
const bLen = vLen(b)
if (a<b) {
currentPointToPoly = vnegate(a)
currentDistanceToPoly = aLen } else {
currentPointToPolyg= vnegate(b)
currentDistanceToPoly = bLen
}
} else {
const i= (y3 + j * y4 - y1) / y2
currentPointToPoly = vscale(norm,i)
currentDistanceToPoly = vlen(curentPointToPoky)
if (currentDistnceToPoly < shortestDist) {
closstPointOnPoly = vadd(point, currentPointToPoly)
shortestDist = curretnDistancToPoly
}
})
return [clsoestPointOnPoly, shortestDistance]
}
ANOTHER SIMPLER WAY
Basic algorithm is to check every segment of the polygon and find the closets point for it. This will either be the perpendiular point (if it is on th semgnt) or one of hte endpoints. After doing this for all segments, pick the point with the smallest total difference.
So in your example it would be th segments
AB, outsied, pick B
BC, inside, try that point
CD, outside, try C
DE outside, try D
EA outsie, try A
when you compare the differenes you will see that the pependicular point fm segment BC is the closest match. You can also do this comparison in the samer run
box2d.b2PolygonShape.prototype.ComputeDistance = function(xf, p, normal, childIndex) {
var pLocal = box2d.b2MulT_X_V2(xf, p, box2d.b2PolygonShape.prototype.ComputeDistance.s_pLocal);
var maxDistance = -box2d.b2_maxFloat;
var normalForMaxDistance = box2d.b2PolygonShape.prototype.ComputeDistance.s_normalForMaxDistance.Copy(pLocal);
for (var i = 0; i < this.m_count; ++i) {
var dot = box2d.b2Dot_V2_V2(this.m_normals[i], box2d.b2Sub_V2_V2(pLocal, this.m_vertices[i], box2d.b2Vec2.s_t0));
if (dot > maxDistance) {
maxDistance = dot;
normalForMaxDistance.Copy(this.m_normals[i]);
}
}
if (maxDistance > 0) {
var minDistance = box2d.b2PolygonShape.prototype.ComputeDistance.s_minDistance.Copy(normalForMaxDistance);
var minDistance2 = maxDistance * maxDistance;
for (var i = 0; i < this.m_count; ++i) {
var distance = box2d.b2Sub_V2_V2(pLocal, this.m_vertices[i], box2d.b2PolygonShape.prototype.ComputeDistance.s_distance);
var distance2 = distance.LengthSquared();
if (minDistance2 > distance2) {
minDistance.Copy(distance);
minDistance2 = distance2;
}
}
box2d.b2Mul_R_V2(xf.q, minDistance, normal);
normal.Normalize();
return Math.sqrt(minDistance2);
} else {
box2d.b2Mul_R_V2(xf.q, normalForMaxDistance, normal);
return maxDistance;
}
}
box2d.b2PolygonShape.prototype.ComputeDistance.s_pLocal = new box2d.b2Vec2();
box2d.b2PolygonShape.prototype.ComputeDistance.s_normalForMaxDistance = new box2d.b2Vec2();
box2d.b2PolygonShape.prototype.ComputeDistance.s_minDistance = new box2d.b2Vec2();
box2d.b2PolygonShape.prototype.ComputeDistance.s_distance = new box2d.b2Vec2();
Useful Refereces
Comments