Raycasting in a 2D plane

429 Views Asked by At

Given a 2-dimensional plane with a finite number of line segments scattered across it, and a point P somewhere on the plane.

How would i: 1. Find if a ray casted in an arbitrary direction a from the point, will hit a line segment or not. 2. Find if all angles are covered by line segments, assuming we were ray casting from P. i.e. whether we're surrounded. 3. Find the minimum, maximum and average distance our rays would travel from our point until it hits a line segment.

I believe 1 is easy, given the angle a and the point P, I can simple check all the line segments and check if I can find an intersection with any of them.

I believe 2 is similarly easy, if I do it in a discrete way, and only check even angles, alike a=1°, a=2°, etc. I can't however seem to find a way to make it continous, but I included it as a subgoal as I believe it's required for 3.

Alike with 2, I can easily solve this in the discrete case, and similarly I can't seem to find a continuous solution.

I believe 2 and 3 will involve constructing the smallest possible polygon, that will encapsulate P, and the applying integration on it, but I can't seem to find the method for it.

1

There are 1 best solutions below

3
On

For a practical implementation, your idea of discretizing the angles seems fine.

Fill an array with the distance from the origin to the closest segment, with an angular step as small as you like.

You can fill the array in two ways:

  • cast every ray and find the intersections with every segment. For S segments and R rays, the computational effort is proportional to NSxNR.

  • for every segment in turn, find the range of angles where rays will hit it (they are integer multiples of the angle step), and compute all intersections. Update the array to keep the closest for every angle. The effort is now proportional to NI, the total number of ray/segments intersections.

From this array, you can easily solve all three problems. The finer the step, the more accurate the results.