convex polygon detection algorithm
Posted: Sat Nov 18, 2017 4:49 pm
I have acquired one from the Hadron Collider library, and refactored it for my framework. It works okay, but some shapes that should be convex are detected as concave.
The case where this occurs is when you draw a rectangle as a polygon for example, does anyone have a better concave detection method?
More might be witnessed on my github:
https://github.com/DarkShroom/EntityEngine
but this is very messy code at the moment!
Also here's the refactored HC code (mainly it was taken from an object, and the polygon is now fed in {x1,y1,x2,y2...}
The case where this occurs is when you draw a rectangle as a polygon for example, does anyone have a better concave detection method?
More might be witnessed on my github:
https://github.com/DarkShroom/EntityEngine
but this is very messy code at the moment!
Also here's the refactored HC code (mainly it was taken from an object, and the polygon is now fed in {x1,y1,x2,y2...}
Code: Select all
function array_to_chuncks(array, chunk_size)
--split an array into chucks
-- ie {1,2,3,4,5,6} => {{1,2},{3,4},{5,6}} if the chunk size is 2
--used to split coordinates out
local chunk_array = {}
local chunk = {}
for i, v in ipairs(array) do
table.insert(chunk, v)
if #chunk == chunk_size then
table.insert(chunk_array, chunk)
chunk = {}
end
end
if #chunk > 0 then
print('WARNING, CHUNKING ERROR')
end
return chunk_array
end
--all ripped from HC
--ripped from it's vector package
local function det(x1, y1, x2, y2)
return x1 * y2 - y1 * x2
end
-- returns true if three points make a counter clockwise turn
local function ccw(p, q, r)
-- return det(q.x - p.x, q.y - p.y, r.x - p.x, r.y - p.y) >= 0 --OLD USD XY
return det(q[1] - p[1], q[2] - p[2], r[1] - p[1], r[2] - p[2]) >= 0
end
function polygon_is_convex(vertices)
--determine if a polygon is convex
--taken from the HC library
local v = vertices
v = array_to_chuncks(v,2) --this algorithm requires coors in chunks like {{1,2},{3,4},{5,6}}
if #v == 3 then return true end
if not ccw(v[#v], v[1], v[2]) then
return false
end
for i = 2,#v-1 do
if not ccw(v[i-1], v[i], v[i+1]) then
return false
end
end
if not ccw(v[#v-1], v[#v], v[1]) then
return false
end
return true
end