poly simplify

I wonder whats the best solution so simplify a set of verts by an angle. Say, I have a table with 90 verts and want only each vert, which is in range of a certain angle - say 8 degree! How would I approach?

For now, I’ve tried the below solution, which doesn’t work properly. Angles are positive/negative/positive/… and my function does only 3/4 of the job. Last 1/4 vertices are miraculously missing. It just stops there. Why? Or can you provide a better algorithm?


Thank you in advance :slight_smile:

-- Scans through non-transparent image pixels and creates a simplified bounding polygon for later use with physics!
local function vectorise(img)
    local verts = {}
    
    local function scan(opposite)
        local row = {
            of = 1,
            to = img.height,
            step = 1
        }
        
        local col = {
            of = 1,
            to = img.width,
            step = 1
        }
        
        if opposite then
            row.of, row.to, row.step = img.height, 1, -1
            col.of, col.to, col.step = img.width, 1, -1
        end
        
        -- scan through both halves of the image (right + left) and collect bounding vertices
        for v = row.of, row.to, row.step do --rows
            for h = col.of, col.to, col.step do --columns
                local curr = vec2(h, v)
                local r, g, b, a = img:get(curr.x, curr.y)
                
                if a > 0 then --ignore only transparent pixels!
                    table.insert(verts, curr - vec2(1,1))
                    break
                end
            end
        end
    end
    
    scan(true) --works anticlockwise
    scan()
    
    -- simplify the bounding shape
    local skipangle = 8
    local comparative = verts[1]
    local v = {comparative}
    
    for i = 2, #verts do
        local point = verts[i]
        local angle = math.deg(comparative:angleBetween(point))
        
        if angle > skipangle then
            table.insert(v, point)
            comparative = point
        end
    end
    
    --return verts
    return v
end

You’re computing the angle between two points but you should be computing it between two edges in your polygon. When doing the angle between two points, you actually compute the angle between them relative to the origin. So you actually need to store two vertices, not one.

You calculate the angle of the two sides you want to be the ‘barriers’ get their point angles, then get the angles of the 90 points and if they lie between these barriers you insert them into a table? You want to get all points in a field of view right?

This is not perfect, but should illustrate what I mean about computing the angles using edges rather than points. It goes through the vertices and computes the change in angle at each one. Then we choose some boundary angle and include all vertices whose change of angle is greater than the boundary. As you can see from what happens with the given image, it doesn’t work well when there is a gentle curve.

-- Scans through non-transparent image pixels and creates a simplified bounding polygon for later use with physics!
local function vectorise(img)
    local verts = {}

    local function scan(opposite)
        local row = {
            of = 1,
            to = img.height,
            step = 1
        }

        local col = {
            of = 1,
            to = img.width,
            step = 1
        }

        if opposite then
            row.of, row.to, row.step = img.height, 1, -1
            col.of, col.to, col.step = img.width, 1, -1
        end

        -- scan through both halves of the image (right + left) and collect bounding vertices
        for v = row.of, row.to, row.step do --rows
            for h = col.of, col.to, col.step do --columns
                local curr = vec2(h, v)
                local r, g, b, a = img:get(curr.x, curr.y)

                if a > 0 then --ignore only transparent pixels!
                    table.insert(verts, curr - vec2(1,1))
                    break
                end
            end
        end
    end

    scan(true) --works anticlockwise
    scan()

    -- simplify the bounding shape
    local angles = {}
    local sangles = {}
    local apt = verts[1] - verts[#verts],verts[1]
    local bpt,ang
    for k=1,#verts do
        bpt = verts[k%#verts + 1] - verts[k]
        ang = math.abs(bpt:angleBetween(apt))
        table.insert(angles,ang)
        table.insert(sangles,ang)
        apt = bpt
    end
    table.sort(sangles)
    local v = {}
    local m = sangles[#sangles - 50]
    print(sangles[1],sangles[#sangles],m)
    for k=1,#verts do
        if angles[k] >= m then
            table.insert(v,verts[k])
        end
    end
    
    --[[
        
    local skipangle = 8/180*math.pi
    local start = verts[1]
    local last = verts[2]
    local v = {start}

    for i = 3, #verts do
        local point = verts[i]
        local angle = (last - start):angleBetween(point - start)
        if math.abs(angle) > skipangle then
            table.insert(v, verts[i-1])
            start = verts[i-1]
            last = point
        end
    end
    --]]
    return verts,v
    --return v
end

function setup()
    local i =readImage("Planet Cute:Gem Blue")
    u,v = vectorise(i)
    print(#u,#v)
end

function draw()
    background(40,40,50)
    translate(200,200)
    scale(4)
    spriteMode(CORNER)
    sprite("Planet Cute:Gem Blue",0,0)
    strokeWidth(1)
    stroke(255, 0, 0, 255)
    for i=1,#u do
        line(u[i].x,u[i].y,u[i%#u+1].x,u[i%#u+1].y)
    end
    stroke(0, 255, 13, 255)
    for i=1,#v do
        line(v[i].x,v[i].y,v[i%#v+1].x,v[i%#v+1].y)
    end
end

I’m puzzled now… First of all, which angle gets computed when calling point1:angleBetween(point2)? Please, explain, I’m willing to understand, instead of just copy your code.


I’ve attached a sample picture. Can you explain all that to me on this one? Please, be so kind!

You can only compute an angle between two half-lines, not between two points. So when you do p:angleBetween(q) then p and q need to be interpreted as half-lines, not points. To do this, we think of p and q as half-lines in the direction of p and q going through the origin. Then we measure the angle there (it ought to be anticlockwise, but you can experiment with that). So in your picture, you get the angle between the yellow lines.

But what you want is the angle subtended at the vertex. From that vertex you have a line segment going out and a line segment going in and you want to measure the deflection of the line segment going out from the line segment going in. Since we can only measure angles at the origin, the way to do this is to translate everything to the origin so that the vertex you are looking at is at the origin. So we start with {v_-, v, v_+} and translate to {v_- - v, 0, v_+ - v}. So the angle at the vertex is the angle from v_- - v to v_+ - v.

This actually measures the internal angle, whereas we want the deflection angle. That is, we want to imagine that the line segment from v_- to v is continued beyond v and measure the angle between this continuation and the line segment from v to v_+. This continuation is the segment v - v_-. So actually we measure the angle from v - v_- to v_+ - v.

I found an algorithm for this: the Ramer-Douglas-Peuker algorithm. Here’s an implementation.

(Also on Codea Community)

--Project: Polygon Reducer
--Version: 1.0
--Dependencies:
--Tabs: PolyScanner
--Comments: The vectorise function is due to se24vad, the reduction algorithm is the Ramer-Douglas-Peucker algorithm

if localise then localise("PolyScanner") end

-- Scans through non-transparent image pixels and creates a simplified bounding polygon for later use with physics!
local function vectorise(img)
    local verts = {}

    local function scan(opposite)
        local row = {
            of = 1,
            to = img.height,
            step = 1
        }

        local col = {
            of = 1,
            to = img.width,
            step = 1
        }

        if opposite then
            row.of, row.to, row.step = img.height, 1, -1
            col.of, col.to, col.step = img.width, 1, -1
        end

        -- scan through both halves of the image (right + left) and collect bounding vertices
        for v = row.of, row.to, row.step do --rows
            for h = col.of, col.to, col.step do --columns
                local curr = vec2(h, v)
                local r, g, b, a = img:get(curr.x, curr.y)

                if a > 0 then --ignore only transparent pixels!
                    table.insert(verts, curr - vec2(1,1))
                    break
                end
            end
        end
    end

    scan(true) --works anticlockwise
    scan()

    -- simplify the bounding shape
    -- Find the optimal starting point as one of the two vertices furthest apart.  For speed, this could be omitted by setting n=1.
    local a,n = 0,0
    for k=1,#verts-1 do
        for l=k+1,#verts do
            if verts[k]:dist(verts[l]) > a then
                a,n = verts[k]:dist(verts[l]),k
            end
        end
    end
    local kp = {}
    -- Keep this point
    kp[n] = 1
    -- Iterate through the rest
    simplifyPolyline(verts,kp,n,#verts+n,1)
    -- Save the marked points, discard the rest
    local v = {}
    for k=1,#verts do
        if kp[k] == 1 then
            table.insert(v,verts[k])
        end
    end

    return verts,v
end

function simplifyPolyline(v,t,k,l,e)
    --[[
    Parameters:
    v: full table of vertices
    t: table of markings
    k: initial vertex
    l: final vertex
    e: error
    --]]
    -- Initialise distance and marked point
    local d,n = 0,0
    -- Store the total number of vertices, whenever we look up a vertex then we work modulo nv to allow for "wrap around".  This means we can start anywhere in the table of vertices.
    local nv = #v
    -- Now compute the vector from initial vertex to final vertex
    local m = v[(l-1)%nv+1] - v[(k-1)%nv+1]
    -- This will define the distance of a vertex from "true"
    local dist
    if m == vec2(0,0) then
        -- If the initial and final vertices are the same we compute the distance from that vertex
        dist = function (vv)
            return v[(l-1)%nv+1]:dist(vv)
        end
    else
        -- If the initial and final vertices are different then we compute the distance to the line segment between them.
        m = m:normalize()
        local mn = m:rotate90()
        local md = mn:dot(v[(k-1)%nv+1])
        local mk = m:dot(v[(k-1)%nv+1])
        local ml = m:dot(v[(l-1)%nv+1])
        dist = function (vv)
            if m:dot(vv) > ml then
                -- If we're beyond the endpoints then it's the distance to the relevant endpoint
                return v[(l-1)%nv+1]:dist(vv)
            elseif m:dot(vv) < mk then
                return v[(k-1)%nv+1]:dist(vv)
            else
                -- Otherwise it's the distance to the line
                return math.abs(mn:dot(vv) - md)
            end
        end
    end
    -- Now we go through the intermediate vertices to find the furthest one away.
    for i=k+1,l-1 do
        if dist(v[(i-1)%nv+1]) > d then
            n = i
            d = dist(v[(i-1)%nv+1])
        end
    end
    -- We test to see if the furthest is within the error
    if d <= e then
        -- If so then we mark all intermediate points for discard
        for i=k+1,l-1 do
            t[(i-1)%nv+1] = 0
        end
    else
        -- If not then we mark the furthest for keeping and split the current family of vertices into two families at the marked point
        t[(n-1)%nv+1] = 1
        -- So long as there are intermediate vertices in the two new segments, we continue the iteration.
        if n > k+1 then
            simplifyPolyline(v,t,k,n,e)
        end
        if n < l-1 then
            simplifyPolyline(v,t,n,l,e)
        end
    end
end
        
    

function setup()
    local i =readImage("Planet Cute:Gem Blue")
    u,v = vectorise(i)
    print(#u,#v)
end

function draw()
    background(40,40,50)
    translate(200,200)
    scale(4)
    spriteMode(CORNER)
    sprite("Planet Cute:Gem Blue",0,0)
    strokeWidth(4)
    stroke(255, 0, 0, 255)
    for i=1,#u do
        line(u[i].x,u[i].y,u[i%#u+1].x,u[i%#u+1].y)
    end
    strokeWidth(1)
    stroke(0, 255, 13, 255)
    for i=1,#v do
        line(v[i].x,v[i].y,v[i%#v+1].x,v[i%#v+1].y)
    end
end

@Andrew_Stacey - great code, very useful B-)

@Andrew_Stacey (I can’t test right now, but…) Thank you so much for your engagement!=D> This is a really great community! Proud to be a part of it. It’s so pleasant to learn here:)