Finding whether a part is within a bunch of points

I’m having trouble trying to calculate whether a part is within the boundary or perimeter of a bunch of points. I’ve already tried searching this online and come across a function that works except for certain shapes.

This works but only with a polygon that is convex. Even if it does work, it returns false at positions that should return true because of the polygon not being convex.

local function PointWithinArea(Point, Points)
    local Side
    for i = 1, #Points do
        local Point0 = Points[i]
        local Point1 = Points[i == #Points and 1 or i + 1]
        local Value = (Point1 - Point0):Cross(Point - Point0).Y > 0
        if Side ~= nil and Value ~= Side then
            return false
        end
        Side = Value
    end
    return true
end

This image best represents what I’m trying to do:

1 Like

Whether a point is within a polygon?

Or whether a polygon is intersecting with another polygon?

1 Like

I want to figure out whether a part is within the polygon as in the image.

1 Like

You provided only works for convex polygons. For concave polygons, you’ll need a different way.
One common method for concave polygons is raycasting.
Check if a point is inside a polygon defined by a set of points.

raycasting would only work if there are physical parts surrounding the polygon. I want to avoid this and purely just have positions. Even if I were to do this, how can I detect whether a polygon is convex or concave?

1 Like

To check for concavity you need to examine the angles formed by adjacent vertices. If any angle is greater than 180 degrees, the polygon is concave.
But yea raycasting typically involves intersecting rays with physical geometry like parts, but it can also be simulated mathematically for non-physical representations like polygons defined by points.

1 Like

is there any of achieving the same thing without raycasting?

Could achieve the same effect by comparing the x and y axis of individual points

I just implemented this but I have the same problem.

Seems like the uppermost point is not being accounted for…

Might be an issue with your border determining code since only this area is working
image

I was able to find the solution by porting this code to Luau, it works flawlessly with both concave and convex polygons.

Here is the ported version:

local function pointInPolygon(point, polygon)
	local intersections = 0
	local x, y = point.X, point.Z

	for i = 1, #polygon do
		local x1, y1 = polygon[i].X, polygon[i].Z
		
		local nextVertex = polygon[i+1] or polygon[1]
		local x2, y2 = nextVertex.X, nextVertex.Z

		if (y < y1) ~= (y < y2) and x < (x2 - x1)*(y - y1)/(y2-y1)+x1 then
			intersections += 1
		end
	end

	return intersections % 2 == 1
end
2 Likes

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.