Calculating which of the Collider line segments was hit in Unity? (Placing gameobjects around the perimeter of a collider)

Question

For a game I'm working on I'm trying to write some code that places GameObjects around the perimeter of a PolygonCollider2D. In my game, an object can touch a platform and then starts spreading a subtance around that platform. I want the substance to procedurally spread around the platform, placing GameObjects every x units. For an example of what I mean, please take a look at this .gif where I did the same thing with RayCasts.

Trying to do this with raycasts introduced a lot of edge cases. To eliminate these, I want to apply a more consistent method.

In Unity, a collider holds an array of Collider.points which holds the coordinates of the points that make up the collider. In theory, if you start placing gameobjects at point[0], look at the direction of point[1], and start placing objects in that direction untill you reach point[1], look at the direction of point[2] and repeat, you should be able to neatly place objects around the perimeter of said collider.

My problem is that I wouldn't know whether my initial spreader object would have to start this object placing algorithm between point[0] and point[1] or point[n] and point[n+1].

Please take a look at this example:

If my collision happens on the red marker, I would need to somehow figure out that the collision took place on line segment E between point[4] and point[5], so I could then know the 'starting position' along the perimeter and start writing code that places the objects in both directions simultaneously along the perimeter.

My first thought was finding the world position of the collision, and finding the world positions of the closest two points in points[] to that collision point . But in the above example, that wouldn't work - it'd find positions 2 and 4 (which is not even a segment), even though the collision is touching the line segment between 4 and 5 (segment E).

Does anyone have any suggestions on how to do this?

Answer 1

One solution would be to search the points for the pair whose line the collision point is closest to. So basically, we want our CollisionEnter2D function on the polygon to look something like this:

private void OnCollisionEnter2D(Collision2D collision)
{
    Vector2 contactPoint = collision.GetContact(0).point;
    (Vector2, Vector2) closestLine = FindClosestLine(contactPoint);

    if (closestLine != null)
        print(closestLine);
}

My solution can be described with the following illustration:

(excuse the drawing, I'm a programmer).

As a pseudo algorithm:

define point = collisionPoint;
define pair;
define minDistance;

for pair := (p1, p2) in collider.points:
    if (dist := shortestDistance(point, pair) < minDistance):
        minDistance = dist
        pair = (p1, p2)

At the end of this loop, we would have the two points we're looking for. Here's a rough implementation I came up with:

private (Vector2, Vector2)? FindClosestLine(Vector2 contactPoint)
{
    var localScale = transform.localScale;
    var points = polygonCollider.points;

    (Vector2, Vector2) closestLine = (default, default);
    var shortestDistance = float.MaxValue;

    for (var i = 1; i < points.Length; i++)
    {
        // We multiply the points by localScale, because the collider 
        // scales them to 1 internally, regardless of our size.
        var line = (points[i - 1] * localScale, points[i] * localScale);
        var distance = MinDistPointToLine(contactPoint, line);
        if (distance < shortestDistance)
        {
            shortestDistance = distance;
            closestLine = line;
        }
    }

    if (shortestDistance < float.MaxValue)
        return closestLine;
    else return null;
}

To figure out the shortest distance, we can use some basic trigonometry (again, please excuse the drawing.)

The code would look something like this:

private static float MinDistPointToLine(Vector2 point, (Vector2, Vector2) line)
{
    // Calculate the shortest distance between the line (p[n+1] - p[n]) and the given point.

    var (end, start) = line;
    var lineLength = (start - end).magnitude;
    var lineLengthSqr = lineLength * lineLength;
    var distToStartSqr = (point - end).sqrMagnitude;
    var distToEndSqr = (point - start).sqrMagnitude;
    
    // Equation found by algebra. 
    return distToStartSqr - (distToStartSqr - distToEndSqr - lineLengthSqr) / (2 * lineLength);
}

In this case, we're just printing the two points, but you would obviously use them to implement the algorithm you described.

Answer 2

If you already have your contact point you could go through all the vertices (point) and check to which line the contact point is closest.

Following two methods are taken from HandleUtility (see source code) but it exists only in the Editor so since you want to use it on runtime simply copy it to a custom runtime class

public static class VectorUtils
{
    // Project /point/ onto a line.
    public static Vector3 ProjectPointLine(Vector3 point, Vector3 lineStart, Vector3 lineEnd)
    {
        Vector3 relativePoint = point - lineStart;
        Vector3 lineDirection = lineEnd - lineStart;
        float length = lineDirection.magnitude;
        Vector3 normalizedLineDirection = lineDirection;
        if (length > .000001f)
            normalizedLineDirection /= length;

        float dot = Vector3.Dot(normalizedLineDirection, relativePoint);
        dot = Mathf.Clamp(dot, 0.0F, length);

        return lineStart + normalizedLineDirection * dot;
    }

    // Calculate distance between a point and a line.
    public static float DistancePointLine(Vector3 point, Vector3 lineStart, Vector3 lineEnd)
    {
        return Vector3.Magnitude(ProjectPointLine(point, lineStart, lineEnd) - point);
    }
}

Now assuming your points are all consecutive you can use this e.g. like

// Allows to do some iteration queries on IEnumerable collections
using System.Linq;

...

public static void GetTouchSegmentEndpoints(
    // The Collider.points
    PolygonCollider2D collider, 
    // Your given collision point
    Vector3 touchPoint, 
    // After this method call these two will be filled with the information
    out Vector3 resultA, out Vector3 resultB)
{
    // Assign default values
    resultA = Vector3.zero;
    resultB = Vector3.zero;

    var localPoints = collider.points;

    // First of all the PolygonCollider2D.points are in LOCAL SPACE
    // so firs we need to convert them to worldSpace 
    // using Linq we can do this in a single line
    var worldPoints = collider.points.Select(p => collider.transform.TransformPoint(p)).ToArray();  
    // This basically equals doing something like
    //var worldPoints = new Vector3 [localPoints.Length];
    //for(var i = 0; i < localPoints.Length; i++)
    //{ 
    //    worldPoints[i] = collider.transform.TransformPoint(localPoints[i]);
    //} 

    // for comparing the distance to the current line
    var minDistance = float.PositiveInfinity;

    // Go through the world space points
    for(var i = 0; i < worldPoints.Length; i++)
    {
        // Get the next i with wrap around at the end
        var nextI = i == (worldPoints.Length - 1) ? 0 : i + 1;

        // Get the two corner points for the current line
        var pointA = worldPoints[i];
        var pointB = worldPoints[nextI];

        // get the distance between that line and the given touch point
        var distance = VectorUtils.DistancePointLine(touchPoint, pointA, pointB);

        // if it is smaller than the current minDistance 
        if(distance < minDistance)
        {
            // replace the results 
            resultA = pointA;
            resultB = pointB;

            minDistance = distance;
        }
    }
}

And finally you would simply call it like e.g.

PolygonCollider2D yourCollider;
Vector3 yourWorldTouchPoint;

VectorUtils.GetTouchSegmentEndpoints(yourCollider, yourWorldTouchPoint, out var lineA, out var lineB);

// Do something with lineA and lineB

If this is the most efficient way I don't know ^^