Question 53472 in Javascript Question posted in
A very good W3school tutorial can be found here.

How can I check if a line intersects with any polygons – Javascript

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):
Illustration

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.

Tags:

2

Answers


  1. 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

    Login or Signup to reply.
  2. 0

    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>
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search