Jump to content


I spy a diagram

  • This topic is locked This topic is locked
3 replies to this topic

#1 Rani_sputnik


    GMC Member

  • GMC Member
  • 434 posts
  • Version:GM:Studio

Posted 01 November 2011 - 03:33 AM


Does anyone know what this diagram is called? It's a way of partitioning space in a way similar to a voronoi diagram except that it only uses rectangles. I want to do some research but I don't know what to search...
Also if anyone has tried implementing one it would be even more fantastic if you could give me some hints, but a name will suffice :D

Cheers in advance GMC

EDIT: MY tutor thought I was talking about quadtrees, similar but no.


I've had an idea for the algorithm that I also want to run by people. This is what it consists of

with obj_particles // With all the dots
   build_rectangle(x-d,y-d,x+d,y+d); // build a square around the particle
   resolve_any_particles_close(d); // d defines 'close together'

with obj_corners // With all the corners of these squares
   i = find_shortest_distance_to_intersection();
   build_line(x,y,  i.x,i.y);

I think that would solve it but I'm wondering how to make the find_shortest_distance_to_intersection fast?
I might build two lists that contain all the lines from both left to right and top to bottom. That way the algorithm can just work its way up/down the list.
What do you guys think? Is there something that isn't clear (it feels like a lot of this is just me ranting), can you think of a scenario that would break the algorithm? (It feels really naive) Any help is appreciated.

Edited by Rani_sputnik, 01 November 2011 - 07:53 AM.

  • 0

#2 Agamer


    GMC Member

  • GMC Member
  • 155 posts

Posted 09 April 2012 - 06:27 PM

I know you probably don't care for my response since you posted this a year ago.
Your diagram reminds me of a quadtree:

Posted Image


I know it's not exactly the same since they're squares, but I hope it helps. A quadtree is basically a method of fractioning cells such that points in a plane are separated into individual squares.

EDIT: of course, you do specify it's not a quadtree, so... ?

I really can't figure out what you're trying to say. What do you mean find_shortest_distance_to_intersection?

Edited by Agamer, 09 April 2012 - 06:35 PM.

  • 0

#3 Yal


    Daemon Detective

  • Global Moderators
  • 9758 posts
  • Version:GM:Studio

Posted 23 April 2012 - 11:25 AM

I've PM:ed Rani, since his last activity was yesterday he's still active on this forum.
  • 0

#4 Rani_sputnik


    GMC Member

  • GMC Member
  • 434 posts
  • Version:GM:Studio

Posted 24 April 2012 - 12:11 PM

Hey Agamer.

I ended up giving on this because it didn't end up being so efficient (and I still don't know what it's called), but in case you are interested I'll explain what it was. I can't remember what I was going to use it for but basically I wanted to divide up space into a bunch of rectangles defined by a set of random points. Here's a step by step of what I thought it would do.

> The 'diagram' takes in a set of random points.
> Each point builds a box of a set size around it.
> This leaves the remainder of the space as an odd shape around the points.
> I found if every square corner had 3 lines connected to them that ensured that the entire grid was divided into rectangles.
> So for every corner with 2 lines joined we add another line that extends out until it meets a line that crosses it's path -> note that this is what I originally had as find_shortest_distance_to_intersection().

Hopefully that clears it up a bit. Are you interested in the diagram too? Or was this just trying to help me out given the severe lack of replies :D hehe

And thanks for the pm Yal! Mucho Cudos
  • 0

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users