C#•6mo ago

Is Inside a polygon algorithm..

Does anyone know how to make an algorithm on how to check if a Vector3 position is inside a set of Vector3 corners? I tried raycasting, but its not giving me the correct results. So basicallyt the blue dots are the corners, and the red is how is where its "active" ( Where I get detected ). The black lines is how i want it. As said I tried raycasting and the results of that is in the image below. I know that winding numbers would be accurate 100%, but I want to be able to have the corners in a randomized order, and not a clockwise or counterclockwise way. Does anyone know how to do this? Red = Zone I get detected. Blue = The corners Black = How I want it to work..

    private bool IsInsidePolygon(Vector3 point, IReadOnlyCollection<Vector3> polygonVertices)
    {
        var count = polygonVertices.Count;
        var centroid = GetCentroid(polygonVertices);

        // Sort vertices based on angle from centroid
        var sortedVertices = polygonVertices.OrderBy(v => Mathf.Atan2(v.z - centroid.z, v.x - centroid.x)).ToList();
        var inside = false;
        
        
        for (int i = 0, j = count - 1; i < count; j = i++)
        {
            if (sortedVertices[i].z > point.z == sortedVertices[j].z > point.z ||
                !(point.x < (sortedVertices[j].x - sortedVertices[i].x) * (point.z - sortedVertices[i].z) / (sortedVertices[j].z - sortedVertices[i].z) + sortedVertices[i].x))
                continue;
            
            if (point.y <= Height && point.y >= Min)
                inside = !inside;
        }

        return inside;
    }

    private Vector3 GetCentroid(IReadOnlyCollection<Vector3> vertices)
    {
        var centroid = new Vector3(0, 0, 0);
        vertices.ToList().ForEach(v => centroid += v);
        return centroid / vertices.Count;
    }

    private bool IsInsidePolygon(Vector3 point, IReadOnlyCollection<Vector3> polygonVertices)
    {
        var count = polygonVertices.Count;
        var centroid = GetCentroid(polygonVertices);

        // Sort vertices based on angle from centroid
        var sortedVertices = polygonVertices.OrderBy(v => Mathf.Atan2(v.z - centroid.z, v.x - centroid.x)).ToList();
        var inside = false;
        
        
        for (int i = 0, j = count - 1; i < count; j = i++)
        {
            if (sortedVertices[i].z > point.z == sortedVertices[j].z > point.z ||
                !(point.x < (sortedVertices[j].x - sortedVertices[i].x) * (point.z - sortedVertices[i].z) / (sortedVertices[j].z - sortedVertices[i].z) + sortedVertices[i].x))
                continue;
            
            if (point.y <= Height && point.y >= Min)
                inside = !inside;
        }

        return inside;
    }

    private Vector3 GetCentroid(IReadOnlyCollection<Vector3> vertices)
    {
        var centroid = new Vector3(0, 0, 0);
        vertices.ToList().ForEach(v => centroid += v);
        return centroid / vertices.Count;
    }

2 Replies

StilauGamer•6mo ago

I believe it has something to do with how I am sorting the vertices based on the centroid.

cap5lut•6mo ago

u could simply choose a random direction from the point and calculate with that ray how many surface triangles it intersects, if the number is odd the point is inside, if the number is even its outside

Gaming

Programming

Is Inside a polygon algorithm..