Take a polygon on N points and take the middle of every edge. Connect these points and we have a new polygon. Repeat the process ad infinitum.
They get smaller and smaller, but if you rescale them then you get a nice movie of points that slowly move towards the shape of an ellips. See this movie for a random start with 100 points. It starts in slower motion because the first changes are very rapid and otherwise diffcult to see.
Some mathematic. The polygon is r[1] … r[N]. Think of the points as vectors. The middle of a side is (r[i]+r[i+1])/2, If we repeat that, r[i] gets mapped to (r[i-1]+2*r[i]+r[i+1])/4 – as in the figure where the red point is moved to the blue point.
So what we really do here is to map a point to a (weighted) average of the point and its neighbours. If we rescale using the mean distance of all the points to the origin in some way, our algorithm is complete.
We can generalise this idea by using a different average, f.i. the standard average of the point with its neighbours :
(r[i-1]+r[i]+r[i+1])/3.
Another generalisation is not to use a polygon but to use a wire model of a three dimensional shape, randomize the points and use a similar algorithm. That’s for some next post.
There is something strange in the original paper that did cost me quite some time to understand: it says that the ellipses tilt (-)45 degrees, and mine don’t. Why? It turns out that the paper normalizes the distances to the origin in a different way than I do, and those 45 degrees are an artifact of the normalization process – the paper normalizes the x- and y-coordinates separately. I normalize on the average distance to the origin, which I feel is more natural.
Inspiration: @ionicasmeets. Paper: polygon smoothing by A. Elmachtoub and C.F. van Loan
– 0 –
This was the R code to make the movie. It needs the ffmpeg software to make the movie from the single frames in the tmp directory.
set.seed(1984)
N <- 100
H <- 450
## -----------------------------------------------------------
Trans <- function(r, N){
left.r<- rbind(r[2:N, ], r[1,])
right.r <- rbind(r[N,], r[1:(N-1),])
s<-(left.r + 2*r + right.r)/4
return(s)
}
Normal <- function(r, N){
sapply(1:N, function(i) return (sqrt(r[i,1]^2 + r[i,2]^2)))
}
## -----------------------------------------------------------
r<-matrix(rnorm(2*N,0,15),N,2)
r[,1] <- r[,1]-mean(r[,1])
r[,2] <- r[,2]-mean(r[,2]) # centered around (0,0)
r <- r / mean(Normal(r, N)) # avg distance is 1
## -----------------------------------------------------------
junk <- do.call(file.remove,list(list.files("./tmp", full.names=TRUE)))
jpeg("tmp/fr%06d.jpg", width = H, height = H, type="cairo")
for (i in 1:(18*N)){
J = 1
if( i <80) J =round(9-(i/10), 0)
B<-max(c(max(abs(r[,1])), max(abs(r[,2]))))
for(j in 1:J){
plot(rbind(r, r[1,]), type="l"
, xaxt="n", yaxt="n", bty="n", xlab="", ylab=""
, xlim=c(-B,B), ylim=c(-B,B)
, asp=1
)
lines(x=cos(2*pi*(1:101)/100), y=sin(2*pi*(1:101)/100), type="l", col="darkgrey")
abline(0,1, col="darkgrey")
points(r, pch=c(1,19))
}
r<- Trans(r, N)
r[,1] <- r[,1]-mean(r[,1])
r[,2] <- r[,2]-mean(r[,2]) # centered around (0,0)
r <- r / mean(Normal(r, N)) # avg distance is 1
#
}
dev.off()
unlink("output2.mp4")
system("C:/software/ffmpeg/bin/ffmpeg -r 25 -i tmp/fr%06d.jpg -qscale 2 output2.mp4")