So I needed to check if discs (for disc golf) are out-of-bounds. The problem is that the shape of a playing field can be very crazy. However, I realized that this is basically just trying to check if a point resides within a polygon. After a 2 minute googling search, I found a simple method: simply cast a ray through the shape, and count the number of intersections. If the number of intersections is odd, then the point is within the shape. If it’s even, then it’s out of the shape.
Super simple to implement, since I can just cast the ray toward the basket.
Here’s a test of the implemented method:
And here’s the code:
-- point: Vector3
-- walls: Table of BaseParts
-- ray: Ray pointing through the walls
function IsInArea(point, walls, ray)
local function CalcMaxDistance()
local maxDistance = 0
for _,wall in pairs(walls) do
local d = (point - wall.Position).Magnitude
if (d > maxDistance) then
maxDistance = d
end
end
return maxDistance * 1.5
end
local function FastRemove(t, item)
local n = #t
for i = 1,n do
if (t[i] == item) then
t[i] = t[n]
t[n] = nil
break
end
end
end
local intersections = 0
local distance = CalcMaxDistance()
local wallsWhitelist = {}
for i = 1,#walls do wallsWhitelist[i] = walls[i] end
local lastPoint = point
-- Continuously cast a ray and count the number of intersections that occur:
while ((lastPoint - point).Magnitude < distance) do
local r = Ray.new(lastPoint, ray.Direction * 999)
local hit, pos = workspace:FindPartOnRayWithWhitelist(r, wallsWhitelist)
if (hit) then
intersections = (intersections + 1)
FastRemove(wallsWhitelist, hit)
end
lastPoint = pos
end
return (intersections % 2) == 1
end
Just thought I’d share. I thought this was going to be way harder than it ended up being!
Completely arbitrary. I’m basing the max distance based off of the center of each wall piece, but really I should be checking the distance of the corners. In my rush to put this together, I decided to just multiply the center-based distance by 1.5 since I knew that would certainly cover the actual maximum distance just fine. In theory, the ray would go to infinity.
Also this actually performs really well. Under the example model, a single call of IsInArea never exceeded 0.5ms, which is pretty cool. It’s operating under half a millisecond. Considering this will only be called once every time someone’s disc lands on the ground, this will have virtually no performance impact whatsoever. I could even run it in real-time without any slight issue in performance.
local function PointInPolygon(Point, Polygon)
local current = Polygon
local inside = false
local A = current.Position
local ax, az = A.X, A.Z
local px, pz = Point.X, Point.Z
repeat
local B = current.Next.Position
local bx, bz = B.X, B.Z
if ((az >= pz) ~= (bz >= pz)) and ((px - ax) <= (bx - ax)*(pz - az)/(bz - az)) then
inside = not inside
end
current = current.Next
A, ax, az = B, bx, bz
until current == Polygon
return inside
end
local function CreatePolygonFromPoints(Points)
local Polygon = {Position = Points[1]}
local First = Polygon
for i = 2, #Points do
Polygon.Next = {Previous = Polygon, Position = Points[i]}
Polygon = Polygon.Next
end
Polygon.Next, First.Previous = First, Polygon
return First
end
CreatePolygonFromPoints takes a table of Vector3s and returns a “Polygon”, which is a circular doubly linked list of vertices. PointInPolygon takes a point and a polygon and returns whether the point is inside that polygon.
This is about what I use for Ultimate Boxing and my OBJ optimizer. It has the advantage of not requiring a re-implementation of ray tracing in other languages.
