Finding out how much a concave polygon can be deflated before it self intersects

Help and Feedback Scripting Support
#1

For reference, this is the algorithm that I have implemented:

TLDR: you shift each edge along its direction’s perpendicular by n units.

Then to fill in the gaps/fix the overlap, I just used a line-line intersection algorithm to find where the new polygon’s vertices should be.

Here’s the implementation:

function polygon:Deflate(offset: number)
	local self = self:Clone()

	local verts = clone(self.Vertices)
	removeCollinear(verts)

	local segments = {}

	for i = 1, #verts do -- offset edges
		local vert = verts[i]

		local previousVertex = verts[i - 1] or verts[#verts]

		local dir = (previousVertex - vert).Unit

		local dirPerpendicular = vector3(-dir.Z, 0, dir.X)

		local shiftDirection = dirPerpendicular * offset

		local segmentStart = vert + shiftDirection
		local segmentEnd = previousVertex + shiftDirection

		insert(segments, { segmentStart; segmentEnd })
	end

	local newVerts = {}

	local yVec = vector3(0, verts[1].Y)

	for i = 1, #segments do -- find new intersection point for each vertex
		local thisSegment = segments[i]
		local nextSegment =  segments[i + 1] or segments[1]

		local intersect = intersection(thisSegment[1], thisSegment[2], nextSegment[1], nextSegment[2]) * VECTOR_1_0_1 + yVec 

		insert(newVerts, intersect)
	end

	self.Vertices = newVerts

	return self :: Polygon
end

My question is, if it’s possible, how would one find out how much a concave polygon can be deflated before it self intersects so offset can be clamped?

I was thinking I could simply find the shortest edge and then half of that edge’s length would be the max that offset could be, however I realized that will only work for convex polygons. The reason this is the case is because with a concave polygon (especially one with an extreme angle), such as this one (with an offset of 0.5):

image
image675×512 55.2 KB

the shortest edge is 3.427 studs long (half is 1.713 studs), however the max possible deflation amount should be closer to 0.5 because it’s about to self intersect where the orange x is.

Any ideas?