CODEWITHSUNDEEP
algorithmgeometryintersection
Ilya
Ilya

Reputation: 301

Finding nearest free position for an object for any point [x,y] in a 2D space with primitives (circles, quads)

I have a 2D space with any number of objects (they are circles or quads - it does not matter) with various sizes and various positions in each time tick. I want to find an y-position for the any primitive (green circle in my sample picture) that will make it not intersect with any other objects.

Please, look at this picture to best understand:

enter image description here

I want to find a fast(!) algorithm that can deal with complex cases that have any number of objects in any arrangement.

I would be grateful for any algorithms, suggestions, ideas, etc.

update: The object's order is random, i.e. object N+1 is not always on top or to the right of object N. All objects have random sizes and positions - they are not in a strict grid.

Upvotes: 3

Views: 733

Answers (1)

Sorin
Sorin

Reputation: 11968

Run a scan-line algorithm along the x axis and keep track of the objects using an tree on the y axis.

The idea is that you generate a list of "events" for the x axis. Events are when you encounter an object or when you get rid of an object. If you use circles that will be centerX + radius and centerX - radius. You sort these events. The idea is that between these point you can assume nothing big changes. Yes the edges move a bit but you can easily adjust to it.

Now you'll keep an interval-tree of the edges along the y axis. When you encounter a new object you mark the interval in your tree (O(logN) operation). When you reach the end of an object you mark the interval as free. Then you try to find an interval large enough for your object (again O(logN)).

If you want more fine grained values (say you want your circle to have a circular path as it goes over another circle) you will need to do a bit of interpolation. Basically you know where the edge of what is marked, track it back to the object that marked it and compute the adjustment (basically the intersection point).

This works perfectly when your object is a line because you don't track free space before and after your object. To make that work correctly add a layer of fat around the obstacles. For example in your demo with the circles make the obstacle cricles to increase in radious with the radious of your fitting circle. If you do quads extend the quads with the dimensions of the quad or circle that you are trying to fit.

Upvotes: 2

Related Questions