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

``````-- 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
``````
Tagged:

• 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()
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!

• 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()
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
``````
• 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:)