Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

poly simplify

edited October 2013 in Questions Posts: 505

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 :)

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

Comments

  • Posts: 2,161

    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.

  • Posts: 1,595

    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?

  • Posts: 2,161

    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
    
  • Posts: 505

    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!

    image

  • Posts: 2,161

    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.

  • Posts: 2,161

    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
    
  • IgnatzIgnatz Mod
    Posts: 5,396

    @Andrew_Stacey - great code, very useful B-)

  • edited November 2013 Posts: 505

    @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:)

Sign In or Register to comment.