GM:S 1.4 Voronoi Help needing to create polygons

Discussion in 'Programming' started by ragingdemonz, Oct 12, 2019 at 11:52 AM.

  1. ragingdemonz

    ragingdemonz Member

    Joined:
    Jun 28, 2016
    Posts:
    284
    Okay so i'm back again with voronoi issues. I wanted to make it more automatic so i can use it on different boundary boxes. I'm pretty inexperienced when it comes to complex algorithms and have almost 0 experience with voronoi diagrams.

    I converted an old ActionScript file to make a voronoi diagram but they seem to be separated individually and it makes it very hard to make up polygons for each cell. I do have the Points in a ds_grid which creates the look of it.
    upload_2019-10-12_6-45-32.png

    As you can see the lines are different colors which indicates the edges and creates the overall diagram. The circles inside the edges are seed objects which i want to map the surrounding points to that object so that way it can create the polygon.

    I've tried using a Delaunay script from here which returns the circumcenters of the x and y values from the seeds
    https://www.gmlscripts.com/forums/viewtopic.php?id=2156

    at first glance it seems to work (the yellow dots indicates the circumcenters)

    but it leaves out the points on the sides which you can tell because they are not marked yellow

    upload_2019-10-12_6-51-15.png


    I've spent the last week trying to figure out how to map the points to the seed objects... if anyone can help or provide some insight that would be great. I don't want to spend another day on this.
     
  2. Morendral

    Morendral Member

    Joined:
    Jun 27, 2016
    Posts:
    377
    If you part some relevant code we can try helping you. There isn't much to work with as of yet
     
  3. ragingdemonz

    ragingdemonz Member

    Joined:
    Jun 28, 2016
    Posts:
    284
    You can find the source code of the script on the gmlscripts page.

    I just generated random points around the room. With the Returned data i used the circumcenters x,y and radius to generate the voronoi diagram. As stated above it returns the center X center Y and the Circumradius. from there i use a for loop like so

    Code:
    ///Step Event
    for (var w=0;w<=ds_list_size(my_objs)-1;w++)
    {
        var cur_obj=my_objs[| w];
       
        for (var v=0;v<=ds_list_size(tri_list)-1;v+=9)
        {
               
                var _crx=tri_list[| v+6];  //CircumCenter X
                var _cry=tri_list[| v+7];  //CircumCenter Y
                var _crr=tri_list[| v+8];  //CircumCenter Radius
               
                seed_add_point(cur_obj,round(_crx),round(_cry),round(_crr));  
        }
       
    
    }
    
    }
    the seed_add_point script basically uses point_in_circle like so

    Code:
    if point_in_circle(circumx,circumy,seed.x,seed.y,circumradius)
    {
    add points to ds_grid of seed object
    }


    I'm assuming this script doesn't accommodate for anything outside of the main view and it likes to return 0,0 for some of the points. It's extremely frustrating because i'm almost there i'm not sure if its me or it's the script... theres so much i don't know like... why doesnt it triangulate the entire App surface? Do i need to put seeds on the edges?
     
    Last edited: Oct 13, 2019 at 8:22 AM
  4. Morendral

    Morendral Member

    Joined:
    Jun 27, 2016
    Posts:
    377
    Well like i said it's hard to see without what your code is. The one real script you posted up looks fine, it's pretty straightforward. Are you sure the problem isn't worth your random points? Why not try a few preprogrammed triangles that you know the solutions to already on screen and see where the code is diverging from there. The randomness makes it harder to debug.
     
  5. ragingdemonz

    ragingdemonz Member

    Joined:
    Jun 28, 2016
    Posts:
    284
    I've posted Everything i can The only thing i didn't post is the voronoi stuff, but that's because i have absolutely no clue what is going on in it... it was converted from AS3 and it's extremely robust... If you look at the below example The Triangulation script works well (The lines in White, the circumcenters are the blue dots)

    it triangulates all the points of the seeds(The points with numbers)

    and returns the voronoi vertexes in blue. The problem is the Outer part beyond the triangles... aka the Red and Yellow Dots outside of the white triangles area. In order to make a polygon i need those Points as well, Those points are computed from the voronoi script.

    The issue is, although i have those points (the Red and yellow points) i have no way to connect them back into the Blue points.

    upload_2019-10-13_19-44-2.png

    Now...
    Code:
    ////Create Event
    
     appW = room_width;
     appH = room_height;
     dotNum = 25;
     MAX_VALUE = 9999999;
     storage = dotNum + 4;
     
     for (var i = 0; i < dotNum; i+=1;)
     {
      dots[i,1] = random(appW) ;//1
      dots[i,2] = random(appH) ; //2
    }
    
    
     
    There is a voronoi script called setVoronoi which basically just gets all the point values and adds them into an array called Which basically draws the lines.
    px[]
    py[]
    ex[]
    ey[]

    In the draw event, to draw the voronoi diagram...

    Code:
     for (i=0; i<dotNum; i+=1;)
     {
      n = i * storage + i + 1;
    
     
      for (j=i+1; j<dotNum; j+=1;)
      {
       if sx[n] > -MAX_VALUE then
       {
         draw_line(sx[n], sy[n], ex[n], ey[n]); //Draw Edges
    
         draw_set_color(c_red);
         draw_circle(sx[n], sy[n],6,false); //Draw First set of coordinates
    
         draw_set_color(c_yellow); //Draw End pair coordinates
         draw_circle(ex[n], ey[n],6,false);
       
       }
    
       n += 1;
      }
     }
    }
    
    I have 0 clue what is going on here and why the author decided to do it like this.... But in the picture the Red dots are the PX and PY Values where as the Yellow Ones are EX and EY values

    The problem with this generation is that it splits up the points to different areas... making it extremely harder to connect all the polygons together... in a sense the PX and PY EX and EY values are just voronoi edges and they all make up the giant diagram.
     
  6. Morendral

    Morendral Member

    Joined:
    Jun 27, 2016
    Posts:
    377
    Interesting approach this is using. I understand that the voronoi scripts you are using are robust, but inside them are where the issue lies. As you already know, it's separating the start and end points from the middles, so the blues are interconnected only. The px py and ex ey need to be in the same way to complete the polygons. Take a look through the scripts and see what the difference is in edge generation is for the blue ones and then how to apply it.

    I used the one from red blob games. I'm not sure if your script came from another example someone did that's linked there, but this approach uses the random points generated as the edges of the polygons, not the circumcenters and generating edges around them as your script seems to.
     
  7. ragingdemonz

    ragingdemonz Member

    Joined:
    Jun 28, 2016
    Posts:
    284
    I did read that article you posted and was trying to find a way to link them all up. There is another script i didn't post called SetVoronoi. Which has 2 separate loops. Again the code is insanely robust, It uses 2 loops and the variable inside are not commented so i have absolutely no clue what goes on in there. In fact i'm not sure why he starts the dots array like so..... and skips over [0]
    completely.
    dots[i,1];
    dots[i,2];

    My assumptions are the First loop are meant to setup the borders for the voronoi. Since it uses

    Code:
     for (i=0; i<dotNum; i+=1;)
     {
      x0 = dots[i,1]; 
      y0 = dots[i,2]; 
     
      n = i * storage + i + 1; //EX: 0 * (29-storage Number) + 0 + 1 = 1
    
      //I'm Assuming this is to gain the next Pair of Dot Coords
      for (j=i+1; j<dotNum; j+=1;)
      {
           x1 = dots[j,1]; 
           y1 = dots[j,2]; 
    

    Where as the Second Loop does this

    Code:
    for (i=0; i<dotNum; i+=1;)
     {
      x0 = dots[i,1];
      y0 = dots[i,2];
    
      for (j=0; j<dotNum+4; j+=1;)
      {
       if j != i then
       {
        if j > i then
        { n = i * storage + j; } else
        { n = j * storage + i; }
    ]

    What i think the storage bits are, are the 4 vertices that make up the bounding box. and the second loop is where the points of inside the boundaries are.. Im not currently at my computer and writing this all through remote desktop. When i come back i'll probably just post the setVoronoi code, mayb you'll understand what's actually going on in there better than i will , and possibly find a way to connect all the Px,PY,EX,EY points together.

    Here is a picture with no delunauy triangulation to find the points. And just using the SetVoronoi , I created a Seed object at the random locations that were setup at the dots array and dump the px,py,ex,ey variables into a ds grid to draw it out.
    you'll see they are segmented, and it seems like it follows no order. Here is an Example of what is going on.





    upload_2019-10-14_14-6-45.png



    upload_2019-10-14_14-5-6.png
    upload_2019-10-14_14-5-21.png


    some polygons are connected while the others are not. it is split up into multiple vertices among each object.
     

    Attached Files:

  8. ragingdemonz

    ragingdemonz Member

    Joined:
    Jun 28, 2016
    Posts:
    284
    Okay i think i'm finally getting somewhere... I rememeber reading up about something like this when doing research about voronoi.... i'm still not 100% positive what the method the script use... mayb some sort of other way to triangulate and get points??

    Basically i Removed the second Loop from the SetVoronoi Script and only generated a few nodes to see what the hell is going on. Maybe its detecting if it has 3 or more points that intersect, to add that as part of an edge

    My memorys a bit fuzzy but i think that the Voronoi is made up of perpendicular bisectors, aka the circumcenters aka what delaunay calculates... everytime i work on this i feel like im 1 step closer to something but then another greater mystery is unsolved.

    like why does it skip certain points on here by using

    n = i * storage + i + 1;

    i'm assuming that Storage is probably used for the Bounding box aas in the VoronoiSet Script it adds 4 extra vertices to it so maybe it's skipping over these ones?

    I'm assuming that they are skipping over Points that dont' have an edge perhaps?


    upload_2019-10-14_18-27-39.png


    Now if i add back in the second loop

    upload_2019-10-14_18-30-35.png
     
    Last edited: Oct 15, 2019 at 4:42 AM

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice