2

I'm a high school student and I went to a coding competition recently and got this problem that I had no idea how to solve:

Given a maze enclosed in a 100x100 area, determine if a circle with a given radius could fit through the maze given the locations of all the walls. Walls will be defined as lines connecting two points within the space, and you will be given start and destination points for the circle. The circle must start with its center at the start point and touch the destination point for it to successfully fit through the maze. There will be a maximum of 20 walls. The radius of the circle and the locations of the walls can be "arbitrarily" precise. ("arbitrarily" for this case just means within far limits - let's say, up to a max of 10 digits after the decimal).

Here is an example. If this were the input:

Radius = 2.8
Start = (5,5), Destination = (95,95)
Walls (a wall connects each pair of points):
(20,0) to (27.5,22.6)
(27.5,22.6) to (55.1,35.5)
(55.1,35.5) to (80.3,80,4)
(80.3,80,4) to (95,63.9)
(1.7,25.8) to (17.5,53.2)
(17.5,53.2) to (56.4,69)
(56.4,69) to (67.9,90.6)
(85.6,98.94512) to (87.3,92.5)

then this (made on desmos) is what the maze would look like (the blue circle is just to show how big the circle is):

this

I would know how to solve the problem if it were in a quantized grid, but the exact locations of the walls and the radius of the circle can be arbitrarily precise. I've thought about using the "right-hand rule" to find a path, but I don't know how to implement that in a non-quantized space (nor am I very familiar with the method).

How would I go about solving this? Can someone point me to an algorithm, a link, some pseudocode, or just an intuition that could help me get an understanding of how I might solve this? Any help is appreciated. Thanks!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Sam Hooper
  • 187
  • 8

2 Answers2

2

It's quite a task and not easy to code, but here's a way that works:

Let r be the radius of the circle. That means that the center of the circle can't get within r of any obstacle.

Move the walls of your maze area in by r on each side.

Replace every wall endpoint with a circle of radius r.

Replace every wall with a rectangle of width 2r.

Now you don't need to worry about the circle -- only its center point, which must remain within the new boundaries and outside of any of the circles or rectangles you made from the walls.

Now, there is a path from the start to the end if they are in the same enclosed area. To find that out...

Cut the scene horizontally at every intersection and vertical maximum or minimum to create strips, with each strip divided into regions by a line or circular arc that passes all the way through it. A region does not connect direction to the regions to its left and right, but may connect to zero or more regions in the strips above and below it. The connections between regions form a graph.

Starting at the region containing the start point, run a BFS or DFS on this graph to see if you can reach the region containing the end point.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
2

Thickennig/moving walls by r in each side like in the other answer (+1 btw) sounds simple but to code it its not trivial to do. For more info see

The direction of normal in 2D is easy if dx,dy is line direction then (-dy,dx) and (dy,-dx) are normals to it ...

However I would encourage to do slower but safe and easier approach by computing the closest distance to wall for each vertex of the maze and close paths that are closer than 2r ...

Something like this:

preview

So:

  1. for each vertex
  2. check all lines that does not belong to vertex path

  3. compute perpendicular and min distance d to line and its vertexes use the smallest d the distance can be computed easily see:

    just look there for Perpendicular distance of any point P to AB so:

    d = min
      (
      perpendicular_distance(line,vertex), 
      |line_vertex1-vertex|, 
      |line_vertex2-vertex| 
      )

    if d<2r close the path. For example by adding a line that joins the wall its too close to tested vertex

    ideally by joining tested vertex and the found closest point. Do not forget in such case to split the opposing wall line to two by the closest point so your graph algorithms still work...

    split

As you can see this is O(n^2) instead of O(n) like in the other answer but its foul proof... enlarging polygons is not and in matters of fact its one of the hardest things in 2D geometry to code (IIRC even still open problem)...

Spektre
  • 49,595
  • 11
  • 110
  • 380