Need help with grid code

pug6_4 · July 22, 2022, 12:43am

hello, i need some help with my quadtree, i’ve figured everything out but i can’t seem to find out how to fix it.

local function FindQuadrant(pos)
	local function RecursiveTracking(times,lasttable)
		times += 1
		if times >= Max then
			return lasttable
		end
		
		local Sorted = table.clone(lasttable)
		Sorted.Position = nil
		Sorted.Quad1 = nil
		Sorted.Quad2 = nil
		for index,Table in pairs(Sorted) do
			if Table.Position then
				local p1,p2,p3,p4,mid = UnpackArray(Table.Position)
				local InPoly = GetPointInPolgyon(pos.X,pos.Z,unwrapper({p1,p2,p3,p4}))
				for i,v in pairs(Table.Position) do
					
					local part = Instance.new("Part")
					local gui = game.ReplicatedStorage.SurfaceGui:Clone()
					gui.Parent = part
					gui.Adornee = part
					gui.TextLabel.Text = i
					part.Size = InPoly and Vector3.new(5,100,5) or Vector3.new(15,15,15)
					part.Position = v
					part.Anchored = true
					part.Color = InPoly and Color3.new(0.14902, 1, 0) or Color3.new(1, 0, 0)
					part.Parent = workspace.Folder
				end
				if InPoly then
					return RecursiveTracking(times,Table)
				end
			else
				return "Positions not here"
			end
		end
	end
	local Quadrant = RecursiveTracking(0,Grid)
	return Quadrant
end


workspace.Part:GetPropertyChangedSignal("Position"):Connect(function()
	workspace.Folder:ClearAllChildren()
	FindQuadrant(workspace.Part.Position)
end)

local function GetPointInPolgyon(x,y,poly)
	-- By Pedro Gimeno, donated to the public domain
	local x1, y1, x2, y2
	local len = #poly
	x2, y2 = poly[len - 1], poly[len]
	local wn = 0
	for idx = 1, len, 2 do
		x1, y1 = x2, y2
		x2, y2 = poly[idx], poly[idx + 1]

		if y1 > y then
			if (y2 <= y) and (x1 - x) * (y2 - y) < (x2 - x) * (y1 - y) then
				wn = wn + 1
			end
		else
			if (y2 > y) and (x1 - x) * (y2 - y) > (x2 - x) * (y1 - y) then
				wn = wn - 1
			end
		end
	end
	return wn ~= 0 -- even/odd rule
end
local function unwrapper(tbl)
	local unwrapped = {}
	for i,v in pairs(tbl) do
		unwrapped[#unwrapped + 1] = v.X
		unwrapped[#unwrapped + 1] = v.Z
	end
	return unwrapped
end

local function UnpackArray(array)
	local dict = {}
	for i,v in pairs(array) do
		table.insert(dict,v)
	end
	return table.unpack(dict)
end

Don’t worry about the quadtree creation as i can confirm the points are correct, lmk if you want the grid structure though.

nicemike40 · July 22, 2022, 1:46am

What exactly are you trying to achieve? What is the problem?

pug6_4 · July 22, 2022, 1:48am

im trying to use my quadtree to find where to search for a quad for my ocean system but my find point in polygon function won’t function

nicemike40 · July 22, 2022, 1:59am

Ah I see, you’re trying to solve the problem we talked about in your last post, namely, finding the triangle a point is on?

Try isolating the GetPointInPolygon function in a simpler environment, without the whole Quadtree stuff.

One problem I see off the bat is that GetPointInPolygon looks like it assumes a 0-based array while you’re feeding it a 1-based array

pug6_4 · July 22, 2022, 2:03am

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

new function im using, it works exactly the same way and im having the same issue.
the function isn’t the issue, that’s apparent.
i isolated the function earlier and it seems to work by itself, but i think it may have to do with the order of my polygons (someone suggested it)

this is how i should have them, but this is how i have them:

so ill try that first.

pug6_4 · July 22, 2022, 2:07am

im going to move from this function to this:

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

it’s more appropriate for what im doin

nicemike40 · July 22, 2022, 2:09am

Neither of those are correct. The vertices should be listed in a cycle:

1     2

4     3

or

pug6_4 · July 22, 2022, 2:14am

damn im confused as crap. rearraning anything doesnt do anything btw, still the same so ill drop that idea tbh.

nicemike40 · July 22, 2022, 4:39am

You triangles are arranged in a grid.

Calculate the grid square your point is in with math.

Check the two triangles in that grid square and the triangles in the surrounding eight quads as well just in case the points have shifted in the XZ plane a lot.

Like take this image example:

Purplish lines are the original positions of your triangles, before your waves moved them around.

Your goal is to find the triangle the red dot sits on.

First you find the grid square the red dot is on with some simple math

local offset = dot - GRID_ORIGIN
local row = 1 + math.floor(offset.Z / GRID_SQUARE_SIDE)
local col = 1 + math.floor(offset.X / GRID_SQUARE_SIDE)

Cool, now you know the red dot’s in the middle square. Check if it’s actually on top of one of those two triangles with your PointWithinArea function (it’s not).

Then check the other triangles in the immediately neighboring squares as well. Eventually you’ll figure out it’s in the bottom-left triangle in the upper neighbor, and you’re done.

You only have to check 16 triangles in the worst case, which is really quick. Expand the “ring” of triangles you check if your vertices are getting offset by more than a single grid row width.

pug6_4 · July 22, 2022, 1:47pm

local Grid = {}
local function RecursiveGridMake(LastTimes,Amount,pos,lasttable)
	LastTimes += 1
	if LastTimes >= Max then
		return
	end
	local SubI = 0
	
	for y = 1,2,1 do
		for x = 1,2,1 do
			SubI += 1
			local Anchor = pos
			local increment = baseplate.Size.X/(2^LastTimes)
			local offset = Vector3.new(increment,0,increment)
			local pos = Anchor + Vector3.new(increment*x,0,increment * y) - offset
			lasttable[LastTimes.." "..SubI] = {["Position"] = {
				p1 = pos + Vector3.new(0,0,increment),
				p2 = pos,
				p3 = pos + Vector3.new(increment,0,0),
				p4 = pos + Vector3.new(increment,0,increment),
				mid = pos + Vector3.new(increment/2,0,increment/2)
			}}
			if LastTimes == Max - 1 then
				local mid = lasttable[LastTimes.." "..SubI].Position.mid
				local lowerleft = mid - Vector3.new(increment/4,0,increment/4)
				local upperright = mid + Vector3.new(increment/4,0,increment/4)
				
				local quad1 = FindClosestPoints2(lowerleft,workspace.Plane:GetChildren())
				local quad2 = FindClosestPoints2(upperright,workspace.Plane:GetChildren())
				
				lasttable[LastTimes.." "..SubI].Quad1 = quad1
				lasttable[LastTimes.." "..SubI].Quad2 = quad2
			end
			RecursiveGridMake(LastTimes,Amount*2,pos,lasttable[LastTimes.." "..SubI])
		end
	end
end
local Anchor = Vector3.new(baseplate.Position.X,0,baseplate.Position.Z) - Vector3.new(baseplate.Size.X/2,0,baseplate.Size.X/2)
RecursiveGridMake(0,1,Anchor,Grid)

This is how my grid is setup.
The depth, and the formation.

Like this, and how much depth i want i can set using the recursive generator.
since my grid is setup like this im unsure if that would work

pug6_4 · July 23, 2022, 12:38am

uh the getpointinpolgyon function seems to be 100% at fault, it won’t even work at a simple enviroment.
i don’t know how i can finish my quadtree without one of these though…