Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (799)
Games in Android Showcase (237)
games submitted by our members
Games in WIP (865)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  [SOLVED] Random Shape Generator  (Read 15083 times)
0 Members and 1 Guest are viewing this topic.
Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Posted 2016-08-23 17:26:05 »

    Hi,

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


  • First I thought of creating a grid divided into x parts. Then add random points on the grid then fill that polygon.
    But 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.
    And to fix this issue, i have no idea left.

  • Then I somehow found a topic on geometry suggesting that you could create shapes with Delaunay's triangulation performed on random points.
    So now the issue is how to extract a shape out of this ?
    Now that i have something like this :
    Source: Wikipedia
    How do i get the shape ? I mean how do i remove the segments that are inside the edges ?
    [EDIT]Solution :
    • An edge is a line segmnet that is part of only one triangle.

  • Or Is there any other way to generate random shapes ?

Thank you for reading.[/list]
Offline Archive
« Reply #1 - Posted 2016-08-23 17:48:54 »

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.

Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #2 - Posted 2016-08-23 17:53:53 »

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 ?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Archive
« Reply #3 - Posted 2016-08-23 17:55:37 »

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

Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #4 - Posted 2016-08-23 18:29:44 »

Thank you, that was exactly what i was looking for.
Offline richierich
« Reply #5 - Posted 2016-08-23 19:51:26 »

Is there any other way to generate random shapes ?
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?

Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #6 - Posted 2016-08-24 01:10:31 »

Is there any other way to generate random shapes ?
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?


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.
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 ?
Offline Archive
« Reply #7 - Posted 2016-08-24 03:09:27 »

So what i shall consider to select a segment as an edge ?

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... Smiley )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!

Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #8 - Posted 2016-08-24 10:10:37 »

Well, i do still see a potential issue.
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...
Offline Archive
« Reply #9 - Posted 2016-08-24 14:42:07 »

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...

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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline thedanisaur

JGO Knight


Medals: 59



« Reply #10 - Posted 2016-08-24 16:17:22 »

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.

Every village needs an idiot Cool
Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #11 - Posted 2016-08-25 06:55:47 »

Quote from: 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.
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 from: 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.
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.
Offline Archive
« Reply #12 - Posted 2016-08-25 16:34:36 »

Quote from: 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.
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.
But the Graham Scan generates a convex hull, so unless you aren't using the Graham Scan, it should work.

Offline leSpace

Senior Devvie


Medals: 14
Exp: 1 year



« Reply #13 - Posted 2016-08-26 06:38:58 »

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.
Pages: [1]
  ignore  |  Print  
 
 

 
Riven (203 views)
2019-09-04 15:33:17

hadezbladez (4941 views)
2018-11-16 13:46:03

hadezbladez (1820 views)
2018-11-16 13:41:33

hadezbladez (5217 views)
2018-11-16 13:35:35

hadezbladez (1028 views)
2018-11-16 13:32:03

EgonOlsen (4402 views)
2018-06-10 19:43:48

EgonOlsen (5235 views)
2018-06-10 19:43:44

EgonOlsen (2976 views)
2018-06-10 19:43:20

DesertCoockie (3878 views)
2018-05-13 18:23:11

nelsongames (4311 views)
2018-04-24 18:15:36
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!