Shattering blocks with 2d physics and Voronoi.

[Jaketatsic]

This voronoi implementation is absolutely awesome and just what I
needed!

Using Voronoi.regions() I'm able to get the convex polygon point sets
I need to make blocks crumble elegantly in a 2d physics simulation. I
had to do a bit of wrangling to get all the point groups into
counterclockwise order and remove duplicated duplicated points, but
the results are neat!

Check it out at:
http://jaketastic.com/game/NewProject.swf
instructions:
click "play"
click "load test area"
WASD = movement keys
SPACEBAR = shoot the dark green blocks and watch them shatter.

The example is still primitive and some Voronoi regions get missed due
to bugs in my point reordering code.

It may be that it's possible to do something with NodeName's
EdgeReorderer to get points in the right order, more efficiently than
my beastly counterclockwise sorter. I'd like to see something like
Voronoi.regionsCounterClockwise() unless there is some reason that the
point order is what it is.

And I'm not sure that duplicating the point data in the region results
helps anything. Since there is no rendering capability built in that
relies on it, I might presume that it's included to make drawing the
regions easier with the flash drawing api? It just feels kind of
unexpected to get the duplicated points in the point sets of regions
().

I'd also be very excited to see plotBounds() take polygon data so that
"we can make the fractal voronois-within-voronois", but that seems
like a tricky task.

Just for chuckles; here is my embarrassing counter clockwise point
reorderer:
(The Vector2D Class is used by the physics sim and has lots of handy
math methods, but it should be easy enough to substitute
Vector.<Point>. )
<pre>
/*
* Takes an array of Vector2D's (a polygon) and shifts them to place
the centroid (center) at the origin (0,0).
*/
public function centroidEquals(p:Array):Vector2D {
var centre:Vector2D = new Vector2D();
var pl:uint = p.length;
for (var i:uint = 0; i < pl; i++) {
centre.y -= p[i].y;
centre.x -= p[i].x;
}
centre.y /= pl;
centre.x /= pl;
for (var j:uint = 0; j < pl; j++) {
p[j].y += centre.y;
p[j].x += centre.x;
}
centre.multEquals(-1);
return centre;
}
private function counterClockwiseEquals(v2dArray:Array):Array {
var ccArray:Array = [];
var a1:Array = [];
var a2:Array = [];
var a3:Array = [];
var a4:Array = [];
for each (var pt:Vector2D in v2dArray) {
if (pt.x < 0 && pt.y < 0) {
a1.push(pt);
} else if (pt.x < 0 && pt.y > 0) {
a2.push(pt);
} else if (pt.x > 0 && pt.y > 0) {
a3.push(pt);
} else {
a4.push(pt);
}
}
if (a1[0]){
sortBySlope(a1, "highest");// Sort by y/x highest to lowest
for each (var p1:Vector2D in a1) {
ccArray.push(p1);
}
}
if (a2[0]){
sortBySlope(a2, "lowest");// Sort by y/x highest to lowest
for each (var p2:Vector2D in a2) {
ccArray.push(p2);
}
}
if (a3[0]){
sortBySlope(a3, "highest");// Sort by y/x lowest to highest
for each (var p3:Vector2D in a3) {
ccArray.push(p3);
}
}
if (a4[0]){
sortBySlope(a4, "lowest");// Sort by y/x highest to lowest
for each (var p4:Vector2D in a4) {
ccArray.push(p4);
}
}
return ccArray;
}
//TODO: make work better!
private function sortBySlope(v2dArray:Array, order:String):void {
var slope:Number;
var p:Array = [];
for each (var v:Vector2D in v2dArray) {
slope = new Number(Math.abs(v.y/v.x));
p.push(slope);
}
//trace("unsorted: "+v2dArray);

//Prepare Insertion sort.
var pl:uint = p.length;
var w:Number = p[0];
var u:Vector2D = v2dArray[0];
var d:Number;
var e:Vector2D;
var temp:Number;
var temt:Vector2D;
var j:uint;
for (var i:uint = 1; i < pl; i++) {
d = p[i];
e = v2dArray[i];
// Insertion sort.
temp = d;
temt = e;
if ( temp < w ) {
j = i;
while ( ( j > 0 ) && ( p[int(j - 1) ] > temp ) ) {
p[j] = p[int(j - 1)];
v2dArray[j] = v2dArray[int(j - 1)];
j--;
}
p[j] = d;
v2dArray[j] = e;
} else {
w = temp;
u = temt;
}
}
if (order == "highest") {
v2dArray.reverse();
}
//trace("Sorted: "+v2dArray);
}

[Alan Shaw]

Hi Jake,

How do I get those balls out of the way so I can shoot the blocks?

Voronoi:regions() returns a Vector.<Vector.<Point>>, and each individual region
is a Vector.<Point> containing all the vertices of that region in
order without duplication.
I don't know if the order is clockwise or counterclockwise, but it is
certainly the same for
all regions.

There is no rendering capability in the library itself, but of course
I did want to support rendering.
I have written a few demos with the library.

I'm not really happy with the EdgeReorderer and do plan to change it
by making better use
of the Halfedge data which should have the orientations built in.

I don't quite get what the desired behavior of
Voronoi.regionsCounterClockwise() is.
Maybe if I can get those balls out of the way I'll see what you mean!

-A

[Jaketatsic]

Sorry about the shoddy instructions, you'll have to press "W" to
thrust upwards and fly over them.
http://jaketastic.com/game/NewProject.swf
click "play",
then click "load test area".
Keyboard Controls:
w= go up
a= go left
s= go down
d= go right
SPACEBAR = shoot bullets and destroy some blocks.

> Voronoi:regions() returns a Vector.<Vector.<Point>>, and  each individual region
> is a Vector.<Point> containing all the vertices of that region in
> order without duplication.

That has not been my experience.
I'm getting results with occasional duplicates like this:
"
Next Region Point set:
(x=359.5059910290404, y=440.89154639756947)<--A
(x=335.3276523392142, y=551.1135757532248)<--B
(x=192.07577872077528, y=397.0352799177426)
(x=222.00611688213468, y=362.7966371832706)
(x=323.9652964008417, y=391.59915806712115)
(x=359.5059910290405, y=440.89154639756947)<--a
(x=335.3276523392142, y=551.1135757532248)<--b
"
The last 2 points are duplicates, but in proper order.
You can find the exact code I used to test at:
http://jaketastic.com/game/VoronoiDraw.as

> I don't know if the order is clockwise or counterclockwise, but it is
> certainly the same for
> all regions.

I've done some testing, and I'm pretty sure that the regions are
almost always clockwise, but usually the upper left most Voronoi
region that includes the top left corner of the_plotBounds rectangle
is counter clockwise. Having not yet done thorough testing yet, this
led me to believe that the point order was arbitrary and I would need
to expect anything.

I needed my point data in counter clockwise order because the physics
sim I use: Glaze requires them in that order to build convex polygon
shapes. If regions() does return point data without duplicates and
allways in clockwise order, all I have to do is use Array.reverse().

Thanks again for releasing this splendid implementation.
-Jake

[Alan Shaw]

Looks like I have a bug!
Time to write a test case!

Thanks,

-A

[Jaketatsic]

So it seems that it is not the top-left region but the first region
reported from regions() (with the highest y coordinate site) that is
counter clockwise.
My general lack of computational geometry and other programming
knowledge make me lean on qualitative testing a lot. I'll use the
drawing api or a TextField to test things, even though it often
obscures some bugs. I really need to work on my test writing...

-Jake

[Alan Shaw]

Interesting. I'm starting to look into this but I want to get ASUnit in place
before I deal with the specifics.

Thanks for being the first sucker, uh, user. May you find all the bugs (;->*

-A

[nodename]

I have updated the repository with a fix for the redundant points in
regions().

Next up: making them all go round the same way.

-A

[Jaketatsic]

It works great. I now get no duplicates from regions()!
It looks to me like only the first point set returned is counter
clockwise, and the rest seem to be clockwise, so it's not a big deal.
I've got the blocks breaking pretty well now.
http://jaketastic.com/game/NewProject.swf

[Alan Shaw]

The blocks are breaking pretty well!

-A