convex polygon detection algorithm

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

convex polygon detection algorithm

Post by DarkShroom »

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...}

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



User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: convex polygon detection algorithm

Post by ivan »

The case where this occurs is when you draw a rectangle as a polygon for example,
Do you have a test script?

I have worked on a polygon library in the past although it's needs work.

First we need the following two utilities for finding the area:

Code: Select all

-- Finds twice the signed area
function poly.area2(p)
  local s = 0
  local v1 = p[#p]
  local x1, y1 = v1.x, v1.y
  for i = 1, #p do
    local v2 = p[i]
    local x2, y2 = v2.x, v2.y
    s = s + (x2 + x1)*(y2 - y1)
    x1, y1 = x2, y2
  end
  return s
end

-- Finds the area
function poly.area(p)
  local s = poly.area2(p)/2
  if s < 0 then
    s = -s
  end
  return s
end
Next, we need to determine the winding of the polygon (CW or CCW).
This can be tricky since in math we expect the Y-axis to point North whereas Love2D renders the Y-axis pointing South:

Code: Select all

--- Checks if the polygon winding is counter-clockwise
--- Range:
-- Assuming the y-axis points up and the x-axis points right
--- Parameters:
-- @p polygon
-- @return true if the polygon is counter-clockwise
function poly.ccw(p)
  return poly.area2(p) > 0
end
Here is the function you are looking for:

Code: Select all

function poly.convex2(p, ccw)
  if #p < 3 then
    return false
  end
  local v3 = p[2]
  local v2 = p[1]
  local x3, y3 = v3.x, v3.y
  local x2, y2 = v2.x, v2.y
  for i = #p, 1, -1 do
    local v1 = p[i]
    local x1, y1 = v1.x, v1.y
    -- signed triangle area
    local s = (x1 - x3)*(y2 - y3) - (y1 - y3)*(x2 - x3)
    if ccw then
      -- ccw polygons: if we make a cw (right) turn we know it's not convex
      if s < 0 then
        return false
      end
    else
      -- cw polygons: if we make a ccw (left) turn we know it's not convex
      if s > 0 then
        return false
      end
    end
    x3, y3 = x2, y2
    x2, y2 = x1, y1
  end
  return true
end

function poly.convex(p)
  local ccw = poly.ccw(p)
  return poly.convex2(p, ccw)
end
Additionally, you'll need to check if the polygon is "simple" and not self-intersecting (and the area must be > 0).

Overall, this is possibly slightly faster (fewer function calls) than your version although my code is more verbose and difficult to read.
User avatar
slime
Solid Snayke
Posts: 3131
Joined: Mon Aug 23, 2010 6:45 am
Location: Nova Scotia, Canada
Contact:

Re: convex polygon detection algorithm

Post by slime »

What about love.math.isConvex?
DarkShroom
Citizen
Posts: 86
Joined: Mon Jul 17, 2017 2:07 pm

Re: convex polygon detection algorithm

Post by DarkShroom »

sorry my code was a bit messy i appreciate i didn't really put the work into a great question there just sorta hoping for a simple answer (sorry no test script provided)

thanks for both answers, actually yeah how it works is educational, but i have to give myself another facepalm after slimes answer :) cheers guys as ever, possibly the best support forum on the internet!
Post Reply

Who is online

Users browsing this forum: No registered users and 48 guests