3 replies to this topic

[Rani_sputnik]

Spoiler

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.

EDIT2:

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.

[Agamer]

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




http://en.wikipedia.org/wiki/Quadtree

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.

[Yal]

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

[Rani_sputnik]

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 hehe

And thanks for the pm Yal! Mucho Cudos