We are about to switch to a new forum software. Until then we have removed the registration on this forum.
Near line 110,
I have output[i] = PVector(sx, sy)
If I change that too:
output[i].x = sx
output[i].y = sy
Then the algorithm breaks, I can't understand why. Can someone take a look?
vecs = []
points = []
buffer = [PVector()] * 5000
def setup():
size(500, 500)
print "okidoki"
print buffer
def draw():
background(0)
if len(vecs) > 3:
noFill()
stroke(255)
beginShape()
for v in vecs:
vertex(v.x, v.y)
endShape()
if len(points) > 3:
epsilon = map(mouseX, 0, width, 0, 100)
result = douglas_peucker(points, epsilon, buffer)
noFill()
stroke(0,255,0)
beginShape()
for v in result:
vertex(v.x, v.y)
endShape()
frame.setTitle(str(int(frameRate)))
def mouseDragged():
vecs.append(PVector(mouseX, mouseY))
def mouseReleased():
global vecs
del points[:]
for v in vecs:
points.append(v)
vecs = []
def douglas_peucker(points, epsilon, buffer):
douglas_peucker_algo(points, 0, len(points)-1, epsilon, buffer);
result = []
#
# copy from the buffer to the result
# skipping overlapping points
#
last_x = float("inf")
last_y = float("inf")
for i in range(len(points)):
v = buffer[i]
if (v.x != last_x or v.y != last_y):
result.append(PVector(v.x, v.y))
last_x = v.x;
last_y = v.y;
return result;
#
# returns the number of insert points made between the start and the end
#
def douglas_peucker_algo(points, start_index, end_index_inc, epsilon, output):
#
# find the point with the max distance
#
d_max = 0
index = -1
for i in range(start_index+1, end_index_inc):
d = dist_to_segment_squared(points[i].x, points[i].y, points[start_index].x, points[start_index].y, points[end_index_inc].x, points[end_index_inc].y)
if (d > d_max):
index = i
d_max = d
d_max = sqrt(d_max)
#
# recursively simplify
#
if (d_max > epsilon):
douglas_peucker_algo(points, start_index, index, epsilon, output) # front
douglas_peucker_algo(points, index, end_index_inc, epsilon, output) # back
else:
#
# Collapse all points to the start except the last.
# Only overlapping points will be ignored later.
#
sx = points[start_index].x
sy = points[start_index].y
for i in xrange(start_index, end_index_inc):
output[i] = PVector(sx, sy)
# why do the lines below break it?
# output[i].x = sx
# output[i].y = sy
# add the last point
output[end_index_inc] = PVector(points[end_index_inc].x, points[end_index_inc].y)
def dist_sq( x1, y1, x2, y2):
return sq(x1 - x2) + sq(y1 - y2)
def dist_to_segment( px, py, lx1, ly1, lx2, ly2):
return sqrt(dist_to_segment_squared(px, py, lx1, ly1, lx2, ly2))
# inspired by http://stackoverflow.com/a/1501725/1022707
def dist_to_segment_squared( px, py, lx1, ly1, lx2, ly2):
lineDist = dist_sq(lx1, ly1, lx2, ly2);
if (lineDist == 0):
return dist_sq(px, py, lx1, ly1)
t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1)) / lineDist
if (t < 0): return dist_sq(px, py, lx1, ly1)
if (t > 1): return dist_sq(px, py, lx2, ly2)
return dist_sq(px, py, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1))
Answers
The culprit is at your line #3:
buffer = [PVector()] * 5000
All of those 5000 indices are actually the very same PVector object reference! @-)
It means if you mutate the PVector from 1 of the indices, that's mirrored for the other 4999! :O)
At line #108:
output[i] = PVector(sx, sy)
, you're creating a new PVector object and re-assigning it back tolist
output[] (which is an alias to the global buffer[] btW), replacing 1 of the PVector clones at that current index i. ;;)Those reassignments are thus fixing 1 by 1 the cloning bug from line #3. :P
Therefore, if you wanna use
output[i].set(sx, sy)
in place ofoutput[i] = PVector(sx, sy)
, in order to avoid unnecessarily instantiating more PVector objects by re-using them, create global buffer[] this way:buffer = tuple(PVector() for i in range(5000))
*-:)I belive it's because of pointerlike behavior
Ah thanks @GoToLoop , I'm quite new to python.
I use this now:
buffer = [PVector() for i in range(5000)]
.