[SOLVED] Random Shape Generator

Game Mechanics
#1

Hi,

My objective is to generate completely random shape and not randomly choose a shape.

[list] - [b]First [/b] I thought of creating a grid divided into [i]x[/i] parts. Then add random points on the grid then fill that polygon. [b]But[/b] the issue with that is that i should get the enclosing polygon, and by that i mean if i add a point that would force the polygon to draw the next line over itself then it shouldn't add this point. [b]And[/b] to fix this issue, i have no idea left.
- [b]Then[/b] I somehow found a topic on geometry suggesting that you could create shapes with [i]Delaunay's triangulation[/i] performed on random points. [i]So now the issue is how to extract a shape out of this ?[/i] Now that i have something like this : https://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/Delaunay_Triangulation_%28100_Points%29.svg/360px-Delaunay_Triangulation_%28100_Points%29.svg.png

Source: Wikipedia
How do i get the shape ? I mean how do i remove the segments that are inside the edges ?
[EDIT]Solution : [list]
[li]An edge is a line segmnet that is part of only one triangle.
[/li][/list]

- [b]Or[/b] Is there any other way to generate random shapes ?
Thank you for reading.[/list]
#2

I believe that a simple way to check if a line in the polygon is an edge line is to make planes out of all the lines and determine whether or not they have any vertices on both sides. If it does have vertices on both sides, then it’s not an edge, if it only has vertices on one side of the plane, it’s an edge.

#3

Thanks that’s really simple and what i needed, though i now remmbered that there is an algorithm given a set of points return the points that would constitute the summits of the smallest polygon enclosing this set of points but I can’t remember how it worked nor its name, any idea ?

#4

This: https://en.wikipedia.org/wiki/Graham_scan ?

#5

Thank you, that was exactly what i was looking for.

#6

[quote=“leSpace,post:1,topic:57531”]
Another way would be kick off a dot to crawl across the plane which turns randomly but with a general preference for turning right. So eventually it’d cross its own tail like the snake game. Various tweakable parameters there to get different kinds of shapes.

Or tile a plane with some shape, either regular or e.g. voronoi tiles or something, then start with one tile and flood-fill a random number of tiles out from that based on some randomized way of selecting the next tile to fill. Actually I guess you could do that with just the pixels as a square “tiling” too and skip a step.

Or capture an image from the device’s camera, posterize it somehow and pick out an edge. That’s real-world input so arguably truly random, but maybe would always be a thumb shape.

What’s the application? Do they have to look like something in particular? Clouds or caves or something?

#7

[quote=“richierich,post:6,topic:57531”]

The issue that frightens me with the dot is that, moving randomly would lean towards oscillating movements or so i predict, and never ever result in a shape that you would get by asking the first stranger you meet to draw a shape.

I might try something like flood fill and use pixels.

I do not have a camera but if i had the issue would be what if the input is almost the same from each generaton ?

The application, originally was to create a random leaf shape based on a seed ( integer).

And with the plane implementation suggested by Archive, you still run into an issue that it is not complete.

http://img15.hostingpics.net/pics/989698test.png

Source: my implementation
In blue the segments that are considered edges.
In black all my segments are drawn.
In red, the points the algorithm build the shape from. These points are based on the blue segments.
So what i shall consider to select a segment as an edge ?

#8

So you’re saying that the algorithm only recognizes the blue lines as “edges” where all the points in the polygon are on one side? (I think i just realized the issue, this algorithm only works in convex polygon generation :/). Now, to think of a solution… Ah, how about not only checking for the side of the line’s plane that each point is on, but if it is in the volume of it as well. Here is an illustration:

So in this illustration, the green line is the line that we are trying to determine if it is an edge or not. The orange lines are the volume of the line. The pink squares are the points within the volume. (I just noticed I missed labelling a point in the volume, but you understand… :slight_smile: )This volume is essentially the normal line of the plane shifted over to the vertices of the edge. In order to test if a point is within the volume, all you need to do is treat the sides of the volume as planes themselves and then use the plane equation to test if it’s within the volume or not. If all the points within the volume are on one side of the edge plane, then the edge is… well, an edge!

#9

Well, i do still see a potential issue.

http://img15.hostingpics.net/pics/508704test.png

It is only a potential issue, because the case of Fig. 1 might only happen to edges, if that’s the case then we know it’s an edge, but oif that not’s the case…

#10

This type of polygon wouldn’t work either.

This is a tougher problem than I originally thought… However I dont think that the polygon that I drew could exist in your instance because you’re doing a convex hull, which by definition doesnt allow these types of jagged edges, for example, this polygon would have a line going across the crests of the spikes rather than a line going down into it.

#11

Hopefully I didn’t miss something but, for what it’s worth, assuming solid geometry, each point must have exactly two line segments that are edges. Once you’ve found a single edge you can find all other edges.

#12

[quote=thedanisaur]Hopefully I didn’t miss something but, for what it’s worth, assuming solid geometry, each point must have exactly two line segments that are edges. Once you’ve found a single edge you can find all other edges.
[/quote]
Well then how would you do that ? I mean that’s true, but once i have an edge, the two points are linked to other line segments ( more than one ) so how would you select the next edge among them ?

[quote=Archive]This is a tougher problem than I originally thought… However I dont think that the polygon that I drew could exist in your instance because you’re doing a convex hull, which by definition doesnt allow these types of jagged edges, for example, this polygon would have a line going across the crests of the spikes rather than a line going down into it.
[/quote]
You are wrong, as you said earlier, your first idea with the planes would have worked with a convex hull. But the polygon you drew is actually possible, this is why it is a tough problem.

#13

You are wrong, as you said earlier, your first idea with the planes would have worked with a convex hull. But the polygon you drew is actually possible, this is why it is a tough problem.
[/quote]
But the Graham Scan generates a convex hull, so unless you aren’t using the Graham Scan, it should work.

#14

No it doesn’t work for the polygon you drew, some edges are left out.

And i found a simpler way : An edge is a line segment that is only part of one triangle.

[EDIT] : the algorithm works and generate random shapes but that’s not the kind of random that i wanted.