Polygon outline / offset

[darkfrei]

Hi all!

Here is my first try to solve the polygon offset to other polygon. Actually, it can be easy modified to the offset line to other line.

Code: Select all

function get_offset (vertices, offset)
	local offset_polygon = {}
	print ( #vertices)
	for i = 1, #vertices-1, 2 do
		local x1, y1 = vertices[i], vertices[i+1]
		local x2, y2 = vertices[i+2], vertices[i+3]
		if not x2 then
			x2, y2 = vertices[1], vertices[2]
		end
		local dx = x2-x1
		local dy = y2-y1
		local vnormx, vnormy = normalization (dx, dy, offset)
		local nx = vnormy
		local ny = -vnormx
		if counter_clockwise or other_side then
			nx = -vnormy
			ny =  vnormx
		end
		local px1, py1 = x1+nx, y1+ny
		local px2, py2 = x2+nx, y2+ny
		table.insert (offset_polygon, px1)
		table.insert (offset_polygon, py1)
		table.insert (offset_polygon, px2)
		table.insert (offset_polygon, py2)
	end
--	print ( #offset_polygon)
	return offset_polygon
end

Here gray polygon with white outline becomes green offset polygon.

[darkfrei]

There is the second version: with respect to crossings:

Code: Select all

function get_intersection (ax, ay, bx, by, cx, cy, dx, dy, unlimited) -- start end start end
--	from line-following
	local d = (ax-bx)*(cy-dy)-(ay-by)*(cx-dx)
	if d == 0 then return end
	local a, b = ax*by-ay*bx, cx*dy-cy*dx
	local x = (a*(cx-dx) - b*(ax-bx))/d
	local y = (a*(cy-dy) - b*(ay-by))/d
	if unlimited then return x, y end
	if x <= math.max(ax, bx) and x >= math.min(ax, bx) and
		x <= math.max(cx, dx) and x >= math.min(cx, dx) then
		return x, y
	end
end

Code: Select all

function normul (x, y, offset) -- normalization and multiplication
	local d = (x*x+y*y)^0.5
	offset = offset or 1
	return offset*x/d, offset*y/d
end

Code: Select all

function get_parallel_line (x1, y1, x2, y2, offset)
	local dx, dy = x2-x1, y2-y1
	local vnormx, vnormy = normul (dx, dy, offset) -- normalization and multiplication
	local nx, ny = vnormy, -vnormx
	local px1, py1 = x1+nx, y1+ny
	local px2, py2 = x2+nx, y2+ny
	return px1, py1, px2, py2
end

Code: Select all

function get_offset (vertices, offset)
	local offset_polygon = {}
	print ( #vertices)
	for i = 1, #vertices-1, 2 do
		local x1, y1 = vertices[i], vertices[i+1]
		local x2, y2 = vertices[i+2], vertices[i+3]
		local x3, y3 = vertices[i+4], vertices[i+5]
		if not x2 then
			x2, y2 = vertices[1], vertices[2]
			x3, y3 = vertices[3], vertices[4]
		elseif not x3 then
			x3, y3 = vertices[1], vertices[2]
		end
		local px1, py1, px2, py2 = get_parallel_line (x1, y1, x2, y2, offset)
		local px3, py3, px4, py4 = get_parallel_line (x2, y2, x3, y3, offset)
		local x, y = get_intersection (px1, py1, px2, py2, px3, py3, px4, py4, true)
		table.insert (offset_polygon, x)
		table.insert (offset_polygon, y)
	end
	return offset_polygon
end

[GVovkiv]

Nice job!
(But it was better, if i understand anything from it)

[ivan]

I wrote a short tutorial about this a while ago, hopefully you might find it useful:
https://2dengine.com/?p=polygons#Polygon_offsetting

[monolifed]

Something I did naively
It doesn't handle self intersections
press W/S

[darkfrei]

Something I did naively
It doesn't handle self intersections
press W/S

Can you comment this function?

Code: Select all

local split = function(o, x, y, x0, y0, x1, y1, a)
	local len = #o
	local s = (1 - x0 * x1 - y0 * y1) / (x0 * y1 - y0 * x1)
	if s * a < 0 then
		o[len + 1], o[len + 2] =  x + a * (y0 + s * x0), y + a * (-x0 + s * y0)
		return
	end
	o[len + 1], o[len + 2] = x + a * (y0 + cap * s * x0), y + a * (-x0 + cap * s * y0)
	o[len + 3], o[len + 4] = x + a * (y1 - cap * s * x1), y + a * (-x1 - cap * s * y1)
end

[darkfrei]

And with rounded outer corners, for example at least one verticle every 30 degrees.

[monolifed]

o is the offset polygon
(x,y) is a corner of the polygon
(x0, y0) is the unit vector of the line to (x, y) (unit normal of this line is (y0, -x0))
(x1, y1) is the unit vector of the line from (x, y) (unit normal of this line is (y1, -x1))
a is offset amount
a is positive for outset, negative for inset
s is negative for wide(>pi) external angle, positive for narrow(<pi) external angle at (x, y)
so we add 2 points for outset+wide or inset+narrow for (x,y)
otherwise we add single point for (x, y)