So I thought I'd play with simplifying curves.
If a curve is sampled at a sequence of points, you can draw an
approximation to the curve by simply connecting consecutive points
with lines; it is often possible to greatly decrease the number of
points without greatly decreasing the accuracy of the curve.
This program demonstrates one way to decrease the number of points,
simply by removing some points without disturbing their neighbors. I
tried three methods of picking which points to remove: picking a point
at random, picking the point with the dullest angle, and picking the
point that, with its two neighbors, forms the triangle smallest in
area. A fourth method, picking the point nearest to the line between
its two neighbors, occurred to me but was not tried.
The random removal algorithm worked surprisingly well. The
smallest-triangle method appeared to perform better, but still had the
undesirable fault of removing sharp corners. The dullest-angle method
does not work particularly well, but perhaps the angle computation
could keep the smallest-triangle method from removing sharp corners.
I still need to analyze these more carefully, as well as look at the
existing literature. (My early CiteSeer searches haven't found
anything yet, but I know it's out there.)
#!/usr/local/bin/python
import Tkinter, sys, random, math
scrawls = []
class scrawl:
def __init__(self, canvas, point):
self.points = [point]
self.lines = []
self.canvas = canvas
self.tag = "scrawl%d" % id(self)
def addpoint(self, point):
oldx, oldy = self.points[-1]
newx, newy = point
line = self.canvas.create_line(oldx, oldy, newx, newy, fill='#996666')
self.canvas.addtag_withtag(self.tag, line)
self.points.append(point)
self.lines.append(line)
def move(self, dx, dy):
for ii in range(len(self.points)):
x, y = self.points[ii]
self.points[ii] = x + dx, y + dy
# quicker way than fixlines():
#self.canvas.move(self.tag, dx, dy)
self.fixlines()
def fixlines(self):
if self.points: oldx, oldy = self.points[0]
for ii in range(1, len(self.points)):
x, y = self.points[ii]
self.canvas.coords(self.lines[ii-1], oldx, oldy, x, y)
oldx, oldy = x, y
def twicepointarea(self, pointindex):
"Return twice the area of the triangle made by a point and its two neighbors."
x0, y0 = self.points[pointindex - 1]
x1, y1 = self.points[pointindex]
x2, y2 = self.points[pointindex + 1]
x1, y1 = x1 - x0, y1 - y0
x2, y2 = x2 - x0, y2 - y0
# I wonder if this would be numerically stable in floating-point.
return abs(x1 * y2 - x2 * y1)
def pointanglecos(self, pointindex):
"""Return the cosine of the angle at this point.
This is useful because when culling points, we want to cull
points whose angles are dullest (closest to being 180 degrees)
and furthest from being sharp (0 degrees).
"""
x1, y1 = self.points[pointindex - 1]
x0, y0 = self.points[pointindex]
x2, y2 = self.points[pointindex + 1]
x1, y1 = x1 - x0, y1 - y0
x2, y2 = x2 - x0, y2 - y0
if ((x1 == 0 and y1 == 0) or (x2 == 0 and y2 == 0)):
# no point in keeping a point with a zerolength edge
# so return dullest possible value
return -1
return ((x1 * x2 + y1 * y2)
/ math.sqrt(x1 * x1 + y1 * y1 + 0.0)
/ math.sqrt(x2 * x2 + y2 * y2 + 0.0))
def smallestpoint(self):
rv = 1
smallestarea = self.twicepointarea(rv)
for ii in range(2, len(self.points) - 1):
area = self.twicepointarea(ii)
if area < smallestarea: rv, smallestarea = ii, area
return rv, smallestarea
def dullestpoint(self):
rv = 1
dullestcos = self.pointanglecos(rv)
for ii in range(2, len(self.points) - 1):
cos = self.pointanglecos(ii)
if cos < dullestcos: rv, dullestcos = ii, cos
return rv, dullestcos
def delpoint(self, pointindex):
self.canvas.delete(self.lines[pointindex-1])
del self.lines[pointindex-1]
del self.points[pointindex]
self.fixlines()
def __len__(self):
return len(self.points)
class drawer:
def __init__(self, canvas):
self.canvas = canvas
def pendown(self, ev):
self.scrawl = scrawl(self.canvas, (ev.x, ev.y))
scrawls.append(self.scrawl)
def move(self, ev):
self.scrawl.addpoint((ev.x, ev.y))
def penup(self, ev):
self.move(ev)
del self.scrawl
def wiggle(canvas):
if scrawls:
dx = random.randrange(-1, 2)
dy = random.randrange(-1, 2)
scrawls[-1].move(dx, dy)
canvas.after(50, lambda canvas=canvas: wiggle(canvas))
def shorten(canvas):
if scrawls:
lastscrawl = scrawls[-1]
if len(lastscrawl) > 2:
lastscrawl.delpoint(random.randrange(1, len(lastscrawl)-1))
canvas.after(50, lambda canvas=canvas: shorten(canvas))
areathreshold = 100
def areashorten(canvas):
if scrawls:
lastscrawl = scrawls[-1]
if len(lastscrawl) > 2:
ii, area = lastscrawl.smallestpoint()
if area > areathreshold:
#print "%d too big" % area
pass
else:
#print "%d (%d < %s)" % (ii, area, `areathreshold`),
#sys.stdout.flush()
lastscrawl.delpoint(ii)
lab['text'] = str(len(lastscrawl))
canvas.after(50, lambda canvas=canvas: areashorten(canvas))
costhreshold = 0
def angleshorten(canvas):
if scrawls:
lastscrawl = scrawls[-1]
if len(lastscrawl) > 2:
ii, anglecos = lastscrawl.dullestpoint()
if anglecos > costhreshold:
#print "%d too big" % (math.acos(anglecos) * 180 / math.pi)
pass
else:
#print "%d (%s < %s)" % (ii, anglecos, `costhreshold`),
#sys.stdout.flush()
lastscrawl.delpoint(ii)
lab['text'] = str(len(lastscrawl))
canvas.after(50, lambda canvas=canvas: angleshorten(canvas))
costhreshold = -1 # disable
def setthreshold(newthreshold):
global areathreshold
areathreshold = int(newthreshold)
def setanglethreshold(newthreshold):
global costhreshold
#print "newthreshold is %s" % `newthreshold`
#print "in radians: %s" % (float(newthreshold) * math.pi/180)
costhreshold = math.cos(float(newthreshold) * math.pi / 180)
mainwin = Tkinter.Tk()
c = Tkinter.Canvas(mainwin, background="white")
# reportpoint = lambda ev: sys.stdout.write("%s, %s\n" % (ev.x, ev.y))
mydrawer = drawer(c)
c.bind("<ButtonPress-1>", mydrawer.pendown)
c.bind("<B1-Motion>", mydrawer.move)
c.bind("<ButtonRelease-1>", mydrawer.penup)
c.pack(side='top', expand='1', fill='both')
lab = Tkinter.Label(mainwin)
lab.pack(side='left')
angleframe = Tkinter.Frame(mainwin)
angleframe.pack(expand='1', fill='both', side='top')
sllabel = Tkinter.Label(angleframe, text='Max angle:')
sl = Tkinter.Scale(angleframe, orient='horizontal', command=setanglethreshold,
to='0')
sl['from'] = 180
sl.set(180)
sllabel.pack(side='left')
sl.pack(expand='1', fill='both', side='top')
areaframe = Tkinter.Frame(mainwin)
areaframe.pack(expand='1', fill='both', side='top')
arealabel = Tkinter.Label(areaframe, text='Max area:')
asl = Tkinter.Scale(areaframe, orient='horizontal', command=setthreshold,
to='1000')
arealabel.pack(side='left')
asl.pack(expand='1', fill='both', side='top')
#wiggle(c)
areashorten(c)
angleshorten(c)
Tkinter.mainloop()
--
<[EMAIL PROTECTED]> Kragen Sitaker <http://www.pobox.com/~kragen/>
We have always been quite clear that Win95 and Win98 are not the systems to
use if you are in a hostile security environment. -- Paul Leach
The Internet is hostile. -- Paul Leach <[EMAIL PROTECTED]>
