How can I check if a line intersects with any polygons

Question

Say I have an array of Polygons expressed as an array of an array [x,y] values, for example:

var polygons = [
  [
     [8, 57],
     [15, 57],
     [15, 71],
     [8, 71],
     [8, 57]
  ], [
    [77, 36],
    [85, 36],
    [85, 50],
    [77, 50],
    [77, 36]
  ]
]

And I have a line like so:

var line = [[8,5], [92, 78]]

How can I get a list of the indexes of polygons that intersect with the line, if there are none, then return 0?

Here is an illustration. This does not match the polygons and the line, but should give you an understanding of the environment. With this example, it should return [0] (assuming the polygon that it intersects with is the first in the polygon list):

I am not sure how to approach this problem, and have searched elsewhere on the internet but could only find a function that works with squares. These are polygons, so it doesn't really work.

Have you noticed that a line intersecting a polygon will often intersect some of its edges? Then there are literal corner cases to handle (when the line enters and leaves the polygon through 1-1 corner), but you could proceed one step at a time. — tevemadar, Mar 24 '23 at 17:26
Some intersection checkers - https://github.com/davidfig/intersects — James, Mar 24 '23 at 17:40
@tevemadar what is the "1-1" corner thing you're talking about? Are you saying that if a line merely touches a corner, then that should count as an intersection of the polygon? — Andrew Parks, Mar 24 '23 at 19:40
@AndrewParks "1-1" as in 1 where it enters and 1 where it leaves, different corners. — tevemadar, Mar 24 '23 at 23:46

score 0 · Answer 1 · answered Mar 24 '23 at 17:24

0

Suggested strategy

Loop over each polygon. For each polygon:
Make a list consisting of pairs of successive nodes: node 0 & node 1; node 1 & node 2; etc, then the final node and node 0.
Now test each pair of nodes for whether the line segment between them crosses the line segment you have defined in var line. If it does, then that polygon is crossed by the line, and you don't need to consider any more points on that polygon.

How to tell if 2 line segments intersect?

Nice answers given here:

https://stackoverflow.com/a/563275/7549483

answered Mar 24 '23 at 17:24

ProfDFrancis

8,816
1
17
26

1

by the way, the final node is always equal to the first node, so I won't need to check if the final node and first node intersect. – Rus Mar 24 '23 at 17:28
Fab - even easier, then! – ProfDFrancis Mar 24 '23 at 17:32

Mr. Polywhirl · Answer 2 · 2023-03-24T18:11:01.067

I ported the following code over to JavaScript:

Collision Detection - Polygon/Line ~ Jeffrey Thompson

And adapted it to your data structures.

const
  ctx = document.querySelector('#scene').getContext('2d'),
  polygons = [
    [ [8, 57], [15, 57], [15, 71], [8, 71], [8, 57] ],    // no
    [ [20, 25], [35, 25], [35, 50], [20, 50], [20, 25] ], // yes
    [ [77, 36], [85, 36], [85, 50], [77, 50], [77, 36] ], // no
    [ [80, 70], [86, 70], [86, 80], [80, 80], [80, 70] ], // yes
  ],
  line = [ [8, 5], [92, 78] ];
  
const main = () => {
  ctx.translate(0.5, 0.5);
  polygons.forEach(polygon => {
    const collided = isCollision(polygon, line);
    ctx.strokeStyle = collided ? 'red' : 'blue';
    ctx.fillStyle = collided ? 'pink' : 'lightblue';
    drawPolygon(ctx, polygon);
    ctx.fill();
  });
  ctx.strokeStyle = 'red';
  drawLine(ctx, line);
};

const lineLine = (x1, y1, x2, y2, x3, y3, x4, y4) => {
  let uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  let uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  return (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1);
}

const polyLine = (vertices, x1, y1, x2, y2) => {
  let next = 0;
  for (let current = 0; current < vertices.length; current++) {
    next = current+1;
    if (next == vertices.length) next = 0;
    let x3 = vertices[current][0];
    let y3 = vertices[current][1];
    let x4 = vertices[next][0];
    let y4 = vertices[next][1];
    let hit = lineLine(x1, y1, x2, y2, x3, y3, x4, y4);
    if (hit) return true;
  }
  return false;
}

const isCollision = (polygon, line) =>
  polyLine(polygon, line[0][0], line[0][1], line[1][0], line[1][1]);

const drawPolygon = (ctx, points) => {
  ctx.beginPath();
  ctx.moveTo(points[0][0], points[0][1]);
  for (let i = 1; i < points.length - 1; i++) {
    ctx.lineTo(points[i][0], points[i][1]);
  }
  ctx.closePath();
  ctx.stroke();
};

const drawLine = (ctx, points) => {
  ctx.beginPath();
  ctx.moveTo(points[0][0], points[0][1]);
  ctx.lineTo(points[1][0], points[1][1]);
  ctx.stroke();
};

main();

<canvas id="scene"></canvas>

How can I check if a line intersects with any polygons

2 Answers2

Suggested strategy

How to tell if 2 line segments intersect?