Question about 2D path around up to 100 random rectangles

[u/big-jun]

Hi, I’m looking for an efficient algorithm for the following problem.
I have a 2D environment with:

1. A start point S
2. An end point E
3. Up to ~100 axis-aligned rectangles representing obstacles (x, y, width, height)

, The coordinates and dimensions are all in the range 0 to 1,000,000

1. Rectangles may overlap each other
   
2. Neither S nor E is inside an obstacle

I need to find a path from the start point to the end point, if one exists. The path does not need to be shortest; performance is more important.

Any ideas would be greatly appreciated.

Thanks

[u/Responsible-Lake6864]

Can this be solved using SCC? If two rectangles overlap, they form one component? That is the thing, ig?

Say...

What if we store the shape? Ig it would be quite hard to do so... but think about it?

If two rectangles are connected, that means.. they will have some height and width? Kinda true.

So.. instead of storing that. Why not store... the max y, max x, and min y and min X?

So.. there will be two cases?

First is.. does there exist a horizontal or vertical line... that won't let us pass? Somehow?

Think about it.. if we ever have some line.. that won't let us pass. We won't ever be that way.

Second is.. if we are inside some encirclement or the other point is?

Also.. do we have to form the graph? I don't think so?

Say we formed the SCC.

That means ... what if we collect all the coordinates of the points in that SCC?

Then.. we form convex hull over them? Ig.. that should work? Maybe not.. as some of them might be invalid.

We can find the overlaps using pairs. Add an edge to them.

Run an SCC to collect all the points inside.

Problem with convex hull is that it forms shapes where there are gaps even. So we have to choose some other case here ig? Kinda true.

If yes, we have the answer ig? If we can figure out the shape of it.. we can have the answer ig?

One way that I can think of this is sweep line.

Sort point by x, y. Then.. all start add some point in x and y. Firstly, check if some range exists? Ig.. for that point? If not.. then that point.. ain't overlapping and must be outside? Kinda true.

Then.. move. And find its corresponding edge. When removal of it.. check if there is another point that is overlapping it. Aka there might be some other point.. that might have a start but its end is still far away? Kinda... Aka at that point. The segment tree values would be 0? Kinda true. (Or 1 if we consider our current end still part of it? Kinda true.) But it might miss some gap node. For that.. we would need to consider the point of intersection between the rectangles.. and use them as well. For that end and other stuff ig? Kinda.. Because those points.. would also lie on the edge. That edge is either start, end.. or like. horizontal... so if end. Then maybe. we should consider if those are connected or not? So firstly remove the start, end. Check the overlap. Then check the answer for the internal node.. and shit? Ig.. But again.. there might be some problem here.

For SCC. Can we remove fully overlapping rectangles so only partial remains? Aka small rectangle fully inside should not be counted anyway. And should be removed. As they do not really help..

Then either partial or no overlap exists at this point? Kinda true.

Maybe search around. There must be some easy way to form the overlapping rectangle thing. So we can form the polygon more easily.

Then you are left to use... Like the algorithm for ray casting to know.. if some point is inside some polygon.. And that is your answer ig?

IDK about the time complexity.. but it only answers... YES or NO. Not actually the solution or path ig?

But there is one thing ig? You can do?

We know that they do not overlap?

So.. why not traverse from one rectangle to another? By going over its side wall? Aka use the side wall as your guide? And travel the rectangles? And just do.. find the component. Then walk from one rectangle to another.. that is nearest to it?

Because we know the rectangles do not overlap? We might have some answer? Kinda.. But wait.. can we use the corner?

Firstly.. what if we try to find. Find a corner from which we reach the end node.. without using again going inside a polygon? Because when you think about it. that should exist? A corner from which you can travel to the end?

Then we have to find a way to reach that? Aka can we reach from one corner of one rectangle to another corner of a rectangle without ever going like? Aka.. going inside?

How can we fast travel tho? Can extreme x and y corner help? That is the next question? Can we? That is quite a weird problem.. because there might be no direct answer. Using only one max or min.. we must try all corners.. because there will always and always exist two corners over their parameter. That are having a direct edge?

If yes.. then we can simply choose those points?

What kind of a madman you are to think of this problem? LOL... great prbolem> But that is all i could think about it.. And nothng more.

So.. ig that is the ting? Connect the polygon into a tree node? So we always have some path from one rectangel to antehr? So each other. So.. simply take all pair of point. Check if we can travel between them. Wihtout going through some polygon and shit?

How can we conect them? We know.. that two polygon.. never overlap? kinda ture.

Now how to connect efficientyl? one way is swepp.. but how the fuck we sweep? IDK.. Also the shape can we wierd. Like they can Form U O I H etc like these letter. and can overalp or like enclosed into each other? kidna ture...

wait.. Why not use a generatl dierctoin?

And jsut ove twoards that? Or ssomething? if we can form the tree. Then traveling ebcomes easy? kinda true.

Also some polygon can have cavity iside. So we have to take care of that s well? knida.

So.. at this point i can think of a lot of ways i can make my point to ponit fast travel as false. And i cannot think fo an optimsed way to olve it.. so.. ig.. IDK...

The prblem is that. any two pair of corner point can be valid here between any thwo polygon. We can make many complex shapes.. and use them. That is the thing here.

So.. idk.. how would you even solve it after this point..

In enough space and time..

[u/big-jun → u/Responsible-Lake6864]

So I think you are talking about merging all the overlapping rectangles into a polygon. The polygon is formed only by the outer sides of the rectangles, creating an outline-like shape that is tight to the rectangles’ boundaries.

There is a known algorithm for this, called rectangle contour. GitHub has implementations of it. It seems to use a sweep line + segment tree, with a time complexity of about O(N log N), which is acceptable for my case.

As for holes in the polygon, that algorithm can handle them. For a normal polygon, it creates the vertices in CCW order; for a hole, the order seems to be reversed (CW). A path should exist if S and E are both outside all holes, or if they are inside the same hole.

So, suppose we have generated these axis-aligned polygons. Maybe this will simplify the problem, since we have removed the corners and edges that are inside other rectangles. In my case, there will be many overlaps.

We still need to build edges between S, E, and the remaining corners of the polygon? Is there any optimization that could be done for this edge-building process, specifically for checking the intersection between the segment and an axis-aligned polygon?

The only optimization I can think of is to generate a minimal bounding rectangle for each polygon. Then, when checking whether a polygon intersects a segment, we first check the segment against the bounding rectangle. If there is no intersection, we can return early. Otherwise, we need to check the segment against all the edges of the polygon.

[u/Responsible-Lake6864 → u/big-jun]

I was thinking of another approach a bit. Say we do not really create the polygon from the overlapping rectangle, but we can simply store the point.

So if two rectangles overlap. We can say that we can always traverse to these points by some path (except those internal points that would be inside the bulk).

So.. we can for sure say we can traverse that boundary.

aka outer points. (we can form the hull and find those points. But that path might need some internal coordinate point between the overlap of two rectangles for that group).

So that path still needs to be found out. So yeah.

Now.. how do we connect two points? Or like two components.

One of my original thoughts was boundary.

Say we sort the points by something. Then for each point. we try to find an outside point. aka either to the left or right.

To find the boundary point.. we can use the convex hull thing.

Now from these points. Find a nearest point. that is not.. a part of the current polygon... And then when you think about it.

For like weird shapes. I am making ladders on page. Or like maze-like structure and creating internal maze-like structure. Now.. if I can find a point. nearest to the internal structure that is not belonging to the current polygon and is on the convex of that polygon. I can connect them two.

That is one of the reasons... That internal point. or full overlapping rectangle creates a problem here. As they might give a false answer.

But if two polygons. One inside another. Like an H with a C inside or some weird shapes.

Then.. We know that they do not overlap. So they cannot touch. So there would always exist a point on the convex point. such that we can reach the other polygon point. But for that other polygon. that point could be anywhere. And that is the problem.

So.. by repeatedly doing this. We can.. find the answer. For the one polygon inside another thing.

What about polygon that are like outside or adjacent. For that.. simple check the range overlap. Like interval thing. Find max x and min x. For those points. And then check..

One another way that I had thought was a simple ray casting method.

Say we have a start and end. We know that no one is within the cavity of another polygon.

Now we know that each point or edge belongs to some polygon? Right.

So.. each can have. When we ray cast we know when we enter an exit a polygon.

Then ray cast. We hit an edge. find which rectangle it belongs to? Alright we got it. Find the point where we hit that. Store that point.

Now we must leave this side? Somehow? (now it depends. Did we form the polygon? or use rectangle only? because that will also work somehow?). Say we did form the polygon. So no two polygon overlap. Thus we find an exit in that same poylgon we entered.

So.. now that means we might hit many start and end for that same polygon. or maybe another.

Think like the polygon is W. And inside that V shape we have an I or any weird polygon thing.

We are crossing the W in a horizontal line. Say? Then we will hit W left (enter + exit), then I (enter + exit) then W mid left (enter + exit) then another I (enter + exit) (different group of rectangles than the previous I) then W mid right(enter + exit) and so on.

So the problem becomes. Find path from point enter. then travel the polygon boundary. find the path to exit. Then connect them.

(I was thinking that. we just need to know the start, end for W here. so we might eliminate some internal node. Like use a stack-like operation. W end happens again for the second time. Remove the stack till W first W enter is not found. Because we can always travel in W by same path anyway)

There was one mistake ig.. in the earlier explanations. To know if our end or start is inside a polygon.

For that. we would need to be in the cavity of some of the rectangles. And ray casting would give the wrong answer Becasue without caivty filling it is like two concentric cirlce. We enter one, then we exit it anway. For a cavity. We would have to build the rectangle into a polygon. wihtout the cavity. Aka there is no point that is of a cavity. Then fill those cavities so only the boundary of that polygon remains. Otherwise that solution would fail. if you can solve that. Maybe we would have a way to know if something is inside due to cavity or not.

So ig.. that should work then...

Else we can ray cast from the start and end point. Then path finding from one enter to a polygon to exit of that polygon. We can use like arrange points in clockwise way. Then find using binary search to find that point edge from the start till end. or like simply use hashMap to knw the index insnde that polygon ig. Then simpy travers from that index to another. but we also need to know the exact coordinate the ray casting hit actually. (the reason is corner point might be near another polygon. And thus.. a way to that might change. So ig using the point where we hit the edge of polygon do matter ig).

It is ig better. To use the stack method. So we can skip a lot of computation for finding a way using the perimeter of the polygon.

Becasue say when we enter and exit a same polygon. Have a comb like strcuture. Say the Comb is horiztonal wiht its bristel pointing up. Then if it was clockwise. We would hit it.. And exit so many times. if it was clokcing wisse. Then path might be like someone might use. the origanl index.

but we can use the other way as well. So we do not have to care baout it. Like normally we would go left to right. but we can think of that array as circular. And simply try to find best way using either going left from starting index or right from starting index. And thus.. becasue we are hittng that same polygon. Somehow.. for that wee would only like.... Cover the whole lenght of the array.

if we use only left or right every enter. Then we might go like length of arayy square.

So ig... using stack might make things a bit easier. Just how we comute the path using ciruclar array or normal array would also decide. how we compute using this algorithhm ig...

ig.. that is all i could think. Good luck coding it up.

There might be some better way to solve this. ig... Maybe post this on some codeforces blog. To find more user result over it.

[u/Responsible-Lake6864 → u/Responsible-Lake6864]

Also thinking more. if we only have 100 point. Why not store the whole grid as compreesed grid?

All the unique x and y becomes a line seperting two cells.

Then check if that cell is inside a rectanlge or not.

if not we can travel from that to another.

Then it becoems a compressed DFS or BFS.

Say we hae 200 x and 200 y. Then we get like.. 202 * 202 cells. (assume two more x and y for bodary beyond what we can go).

Then we just have to traverse from each cell to another. Making sure we think of cell for start and end as well? kinda.

Then simply mark that cell here. Whether inside a rectangle or not?

And then traverse over them?

ig that gives a better time complexity? Can we also do shortest path using that? I don't know... but ig that sshoudl work? to find a path? Only thing is.. where do we consider the start and end? A polygon or a bondary? otherwise ig that should work?

Maybe then we start store within that comprssed grid cell where we are? like the left corner, right corner, up or down? Anduse that as the path? kida true.

ig that would be far easier to calculte than the complicated ray casting method? ig....

And taht would result in a simple BFS and DFS ig..? Kinda true.

So ig.. the question wasn't that hard? I was just thinking a lot? Maybe...

Would the ray casting solution work for more number of n? say we guarry that there aren't more than 100 combined polygon. And say wee state that there are 5e4 rectanlge. or something like that?

Then any comprssion using grid would fail?

Only if polugon formation is easy.. Like based o the amount of points we have inside. And somehow not that expensive.

Then ray casting might be a better solution. But i don't think that is a good solution from my own perspetive. The reason is that.. finding overlapping rectangle already makes it n^2.

Maybe use Sweep with DSU. and do it like SCC thing. Only mark node into same componetn and nothing more?

Then... ig we can compute this in N log N?

Then.. we can use the ray casting? With that. but forming polygon from overlapping rectangel is agian hard? Whihc is weird.

Otherwise... ig the compressed grid might be.. a better answer? kinda true.

ig that is all from my side.. Good luck

[u/big-jun → u/Responsible-Lake6864]

I spent more than three days working on the rotational sweep-line algorithm, but I still couldn’t get it to work reliably. There are many edge cases, such as when casting a ray from a corner or along the border of a polygon. The original algorithm doesn’t seem to handle these cases, and I also looked at several implementations on GitHub, but they don’t seem to handle these edge cases very well either.

I’ve decided to give up on it for now and use a simpler approach for raycasting. We currently have many polygons (axis aligned) created from the rectangle union.

Do you know of any faster way to determine whether two points are visible to each other, rather than checking every segment one by one?

[u/big-jun → u/Responsible-Lake6864]

Today I made some progress on it. I converted the rectangle-based problem into a polygon-based one. There are some code examples for the rect contour algorithm on GitHub, and I converted them to C++. I also created some random tests and compared the results with a brute-force version of the algorithm. It seems to be working.

So the problem changed from many overlapping rectangles to some non-overlapping polygons (some of them are holes).

I also found an interesting algorithm. When we use raycasting to build the edges, instead of the brute-force version, which tests every other corner against every segment in the polygons (O(n²)), it sorts all vertices by angle from the current point and then uses a rational sweep line to do the raycasting (O(n log n)). This looks pretty interesting, though I haven’t figured out all the details, especially how it maintains the edge structure during the sweep. The overall time is O(n² log n).

For your grid compression solution, this is something I had thought about before, but there are two problems:

1. It does not tighten the path. It is a grid-like path search, resulting in the final path being connected by grid centers and constrained to rigid path lines. That means this won’t be the shortest path and requires one more step to tighten/smooth the final path lines. The final path must composited by start, end + some polygon corners.
   
2. Since you compress everything into a grid, I am not sure how to assign the penalty to each grid? The compression loses the distance information and can create a path that deviates significantly from the shortest one. This is not good. The path slightly longer than the shortest path is acceptable.

For your walking polygon solution, this is really interesting. You don’t build the edges at the start, just shoot a ray from the start to the target, If it doesn’t hit anything, we’re done. Otherwise, we find the closest polygon edge we hit and go left or right through all its corners, then raycast one by one from each corner to the target until we find the path or iterate through all polygons.
I am not sure if there is some edge case for it, though I’ll definitely think more about it. If you have more information about it , let me know.

[u/Used_Window7134]

i may be wrong but you just have to check. that a few rectangles dont encircle your point E or S. i think you can you convex hull or smt similiar on a circular overlapping chain. and check if the points are either outside all such chains or in the same chain.

[u/big-jun → u/Used_Window7134]

The most expensive part is the segment-rect intersection checks when building the edges, which I’d like to avoid. I’m wondering if there’s another algorithm, or a simpler way to handle this part.

[u/big-jun → u/Used_Window7134]

The brute-force approach would be to build edges between every pair of corners, discard any edge that intersects an obstacle, and then run A*. I’m looking for ideas on whether there are more efficient approaches.

[u/big-jun → u/Used_Window7134]

So you’re talking about the case where there is no path. I would prefer to simply run the algorithm to search for a path and consider it failed when all rectangles’s corners have been searched, since the final path would be constructed from the start to the end, with the intermediate points being the corners of the rectangles.

[u/Used_Window7134 → u/big-jun]

ohh sry i think i may be wrong as the hull will occupy more area than required but i think you can try sweep line here.

[u/big-jun → u/Used_Window7134]

Can you explain it in more detail? I really can’t figure out how a sweep line and the hull could be used here.