I am trying to get the closest line segment on a PolygonCollider2D from the mouse.
I am getting the closest point easy enough. How do i get the closest line segment?
Before you read. This is more a lesson on maths, rather than the code for it.
First off, lets just get out of the way that the nearest point will not come into play for the nearest segment. Take example this image:
The red dot is nearest the green side, yet the nearest point is at purple.
So lets define ‘nearest’. If you’re “inside” some polygon (like that red dot) or within its bounding box. The nearest side is going to be one where if you treated a side as a numberline, and lowered the dot onto it, it exists within the region of that number line where the side does:
Note how the red dot does not fit in the pink region, or the green region, but it does the red. It also would for the 2 vertical sides, so this won’t be the complete task. But it definitely reduces our potential sides from 5 to 3.
We’ll use vector projection via the dot product to do this.
But first lets get all the sides:
You’ll be concerned in the ‘paths’ of a PolygonCollider2d, these are all the sides of the collider, considering that the sides may not be continuous and the polygon an have holes in them, and the collider is actually made of main smaller polygons.
PolygonCollider2d.pathCount:
PolygonCollider2d.GetPath:
So if we loop from 0 to pathCount and call GetPath for each, we get back 2 Vector2 values which are the end points of that side. Now we have a way to check all the sides.
Next we need determine what sides are eligible. A simple way to do this is to scalar project your point onto the line. This would be done with the ‘dot product’:
So AB is the line segment we get from GetPath.
M1 is our mouse position.
First we need to get relative vectors to do the math.
(note ||x|| means magnitude of some vector x)
v1 = M1 - A
v2 = normalize(B - A)
v1 dot v2 = ||v1|| * cos(theta) = the length of the red line from A to where the green dotted line touches AB
That value we calculate will be positive and less than the distance from A to B if it exists inside the range of A to B. If that red line sits between A and B.
Note how I have M2, M2 is another hypothetical mouse position. If we projected it onto the segment:
v1 = M2 - A
v2 = normalize(B - A)
v1 dot v2 = the length of thin red line
This value would be negative though, since it’s in the opposite direction of the line segment. OT, if you calced v2 as A - B, it’d be positive, but larger than the distance from A to B.
SO, if we do this. We will find the all the sides that we are in the range of. Ignore any side that returns a negative, or a value larger than length of AB (||AB||).
The last step is to then find the length of the green dotted line. The smallest absolute value will be our nearest side.
Well it’s a right triangle, so we can just use some trig to do that. ||v1|| is the length of the hypotenuse, and trig says the length of the opposite side of some angle in a right triangle is sin(angle) * hyp. So:
Get theta as:
theta = arccos(v1 dot v2 / ||v1||);
length green is than:
sin(theta) * ||v1||
In the end, the algorithm is:
Loop over paths
Throw out paths whose scalar projection of the point on the segment is out of range
Calculate the nearness with a little extra trig
Keep the one with smallest
NOTE - if all paths scalar projections don’t intersect. Than you’re outside the bounding box of the entire polygon. In this case, any path whose point is the closest is the nearest.
saw this just few days ago,
“Find closest point in a polygon or polyCollider”