Check if line is lying inside of polygon

Question

In my problem I have an conveyor belt on which a piece of luggage is moving in counterclockwise direction (so left is inside every time when moving alongside the luggage). I know have a line that is possibly lying inside of the conveyor belt. The conveyor belt is modelled by lines with their start and end point as well as the line to check is. The starting point of the line to check is equal to the starting point of one of the conveyor belt's lines (conveyor belt is a simple polygon). My approach was to check if the clockwise angle around this point (starting from the line being part of the conveyor belt) is greater than 180 degrees (than it would be inside) but that doesn't work for all cases. I can minimize the number of failures by laying the line alongside the previous starting point (of the previous line of the conveyor belt) but there are still some cases where this doesn't work.

Thanks for your help, I'll provide any further information needed if I can.

EDIT: It would work for the following with alpha being 333 degrees but beta only 171; the blue line is thus outside of the (black) conveyor belt:

However it wouldn't work for other examples. Imagine the upper part of this image on the right side, too (would look like a castle then ;), a line starting from the blue right point to the then upper right hand corner (would be coordinate (3,2)), would have an alpha value less than 180 (145) and thus it would be considered lying outside though it is actually inside.

Answer 1

If I understand, you want to check whether a line segment lies entirely inside an arbitrary polygon.

First transform the line segment to make it (0, 0)-(L, 0); this takes a translation and rotation (you can also scale to (0, 0)-(1, 0)); apply the same transform to the polygon.

Find all intersections of the polygon edges with the X axis (they are detected by the condition Yi > 0 != Yi+1 > 0). If there's any intersection such that 0 < X < L, report false. Otherwise, report true if the number of intersections such that X < 0 is odd.

There are degenerate cases with Yi=0, X=0 or X=L. It is up to you to decide if "inside" holds or not in such cases before you can adjust the algorithm to handle them correctly.

Answer 2

I recommend having a look at the Determining if a point lies on the interior of a polygon on Paul Bourke's amazing website.

I imagine determining if a line is inside a polygons is the same checking if both points lie within the polying (so for example if the first point isn't inside the polying, no point in the checking the second).

Update Based on your updated question, here are some images to explain the naive algorithm explained in the comments:

1. find the angle of the line
2. rotate the coordinate system so the line is horizontal
3. check if the shape points (marked green) are above or bellow this (now horizontal) line: above means line is outside, bellow means line is inside

I say naive approach because you would check every single shape point in between your line coordinates and I'm not sure how efficient this would be.

A similar approach might be something like this:

1. calculate the angle of the line
2. for each shape point in between your line's start/end points
3. check the angle of the line between the start and current shape point
4. if the angle is smaller the line is outside the shape, exit loop, otherwise, continue testing

Off topic but fun, here's snippet of the idea at the top: testing a line inside poly:

var numPts = 32;
var pts = [];
var hlh = 30;//half line height

function setup(){
  createCanvas(400,400);
  var ai = TWO_PI/numPts;
  for(var i = 0 ; i < numPts ; i++) pts.push(createVector(200+cos(ai*i)*random(100,150),200+sin(ai*i)*random(100,150)));  
}
function draw(){
  background(255);
  fill(0,(lineInPoly(mouseX,mouseY-hlh,mouseX,mouseY-hlh,pts) ? 192 : 0),0);
  beginShape();
  for(var i = 0 ; i < numPts ; i++) vertex(pts[i].x,pts[i].y);
  endShape(CLOSE);
  line(mouseX,mouseY-hlh,mouseX,mouseY+hlh);
}
function pointInPoly(x, y,pts)
{
  var i, j,npol = pts.length;
  var c = false; 
  for (i = 0, j = npol-1; i < npol; j = i++) {
    var p0 = pts[i];
    var p1 = pts[j];
    if ((((p0.y <= y) && (y < p1.y)) ||
         ((p1.y <= y) && (y < p0.y))) &&
        (x < (p1.x - p0.x) * (y - p0.y) / (p1.y - p0.y) + p0.x))
      c = !c;
  }
  return c;
}
function lineInPoly(x1,y1,x2,y2,pts){
  var isFirstInPoly = pointInPoly(x1,y1,pts);
  if(isFirstInPoly){
    return (isFirstInPoly && pointInPoly(x2,y2,pts));
  }else return false;
}
/*
based on Paul Bourke's solution http://paulbourke.net/geometry/polygonmesh/
int pnpoly(int npol, float *xp, float *yp, float x, float y)
    {
      int i, j, c = 0;
      for (i = 0, j = npol-1; i < npol; j = i++) {
        if ((((yp[i] <= y) && (y < yp[j])) ||
             ((yp[j] <= y) && (y < yp[i]))) &&
            (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
          c = !c;
      }
      return c;
    }
*/

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.4.7/p5.min.js"></script>