0

Check if a line drawn intersects or inside the existing polygon on html canvas.

I have a html canvas and there is polygon (mainly quadrilateral) which is already drawn. Now if a straight line is drawn on the canvas I have to check if it intersects the polygon's any side or it is inside the polygon. If any of these is true (intersects or inside) I have to return true.

I am writing code on Angular.

Surya
  • 604
  • 1
  • 6
  • 25

2 Answers2

0

I assume that you mean line segment rather than infinite line.

You can check whether segment intersects any polygon edge (check them all) with intersection detection algorithm (arbitrary found example)

In case of false result also check one segment end with point in polygon test

If you expect that "inside" case is more frequent - do "point in polygon" first.

Perhaps similar functions already exist in your framework.

Also note that there are simpler methods for axis-aligned rectangle (box)

MBo
  • 77,366
  • 5
  • 53
  • 86
0

Obtain the implicit equation of the line of support of your segment (as you say that "inside" is possible, your "line" must be a segment). It has the form

s(x, y) = a x + b y + c = 0

and S is positive on one side of the line and negative on the other side.

Now take every polygon side in turn and plug the coordinates of the two vertices. If the S changes sign between the vertices, the side intersects the line.

Now the trick is to use the parametric equation of the line from one endpoint to the other and find the intersection with the line in terms of the parameter t along the line. Note that the segment will correspond to the t interval [0, 1].

After scanning the whole polygon, you will have a list of t values. If the list is empty, no intersection. If all values in the list are <0 or >1, no intersection. Otherwise, there is an intersection (one subsegment or more).