Check if line intersects a polygon

Processing Coding Questions
1

Hi

How do I find out if a line between two points are intersecting a polygon?

To give a bit of context I am trying to build a small tool that draws perspective lines between a flat polygon and a vanishing point. It is sorta almost working, but I have trouble making sure that perspective lines intersecting the front of the polygon are visible. I think what is missing is to check whether each line between two points are intersecting my front polygon, and then only draw lines that DO NOT intersect.

My somewhat messy in-progress code is pasted below. Try moving the mouse around, and hopefully you will see where my problem is at.

PVector vanishingPoint = new PVector (300, 50);
boolean transparencyMode = false;
PVector[] vectors = new PVector[5];
PVector[] moreVectors = new PVector[3];

void setup() {
  size(600, 400);
  fill(0);
  
  vectors[0] = new PVector(100, 200);
  vectors[1] = new PVector(200, 220);
  vectors[2] = new PVector(200, 300);
  vectors[3] = new PVector(100, 300);
  vectors[4] = new PVector(50, 250);
  
  moreVectors[0] = new PVector(300+100, 200);
  moreVectors[1] = new PVector(300+200, 220);
  moreVectors[2] = new PVector(300+200, 300);
}

void draw() {
  background(255);
  
  drawInitialShape(vectors);
  drawPerspective(vectors);
  
  drawInitialShape(moreVectors);
  drawPerspective(moreVectors);
  
  vanishingPoint.set(mouseX, mouseY);
  ellipse(vanishingPoint.x, vanishingPoint.y, 5, 5);  
  
  text("transparency: " + str(transparencyMode), 10, 15);
}

void mousePressed() {
  transparencyMode = !transparencyMode;
}

void drawInitialShape(PVector[] vecs) {
  for (int i = 0; i<vecs.length; i++) {
    if (i<vecs.length-1)line(vecs[i].x, vecs[i].y, vecs[i+1].x, vecs[i+1].y);
    if (i==vecs.length-1) line(vecs[i].x, vecs[i].y, vecs[0].x, vecs[0].y); //Close it
  }
}

void drawPerspective (PVector[] vecs) {
  PVector[] target = new PVector[vecs.length];
  for (int i = 0; i<vecs.length; i++) {
    target[i] = vecs[i].copy();
    target[i].lerp(vanishingPoint, 0.2);
    if (outsidePolyCheck(target[i], vecs)) line(vecs[i].x, vecs[i].y, target[i].x, target[i].y);
  }
  connectPerspectiveLines(vecs, target);
}

void connectPerspectiveLines(PVector[] vecs, PVector[] target) {
  for (int i = 0; i<target.length; i++) {
    if (i<target.length-1 && outsidePolyCheck(target[i+1], vecs) && outsidePolyCheck(target[i], vecs)) line(target[i].x, target[i].y, target[i+1].x, target[i+1].y);
    if (i==target.length-1 && outsidePolyCheck(target[0], vecs) && outsidePolyCheck(target[i], vecs)) line(target[i].x, target[i].y, target[0].x, target[0].y); //close it
  }  
}

boolean outsidePolyCheck(PVector v, PVector [] p) {
  if (transparencyMode) return true; //Skip all the checks of we want to draw transparent shapes
  
  float a = 0;
  for (int i =0; i<p.length-1; ++i) {
    PVector v1 = p[i].copy();
    PVector v2 = p[i+1].copy();
    a += vAtan2cent180(v, v1, v2);
  }
  PVector v1 = p[p.length-1].copy();
  PVector v2 = p[0].copy();
  a += vAtan2cent180(v, v1, v2);

  if (abs(abs(a) - TWO_PI) < 0.001) return false;
  else return true;
}

float vAtan2cent180(PVector cent, PVector v2, PVector v1) {
  PVector vA = v1.copy();
  PVector vB = v2.copy();
  vA.sub(cent);
  vB.sub(cent);
  vB.mult(-1);
  float ang = atan2(vB.x, vB.y) - atan2(vA.x, vA.y);
  if (ang < 0) ang = TWO_PI + ang;
  ang-=PI;
  return ang;
}
1 Like
2

I did not spend to much time on this. I marked with a fain red X the lines that I think you don’t want to see when transparency is set to false.

The big fat arrow shows the mouse position.

The issue is that the first line in your function outsidePolyCheck() - which is returning true right away - does not cover all the cases.

I do not understand your algorithm and it would help if you add some comments and basic details. From what I observe, the algorithm is not working for all the cases where the generated lines are crossing the main flat (initial) shape. This needs to be addresses as it is the trivial case aka. the algorithm should be checking the line crossing the polygon and it should indeed return false.

For the left figure, I have the impression you need to check the generated lines inside the generated shape (check the 4 little circles in blue - these lines makes a shape as well).

Kf

image
image1170×430 17.5 KB

2 Likes
3

Hi @kfrajer

Thanks so much for having a look at my problem. You are correct that my current code is a bit unclear, but your interpretation is spot on:

the algorithm should be checking the line crossing the polygon and it should indeed return false

How do I do that? How do I find out if a line between two points is intersecting a polygon?
That is my main question.

4

Anybody has an idea for how to solve this?

5

Hi @AndreasRef,

Sorry if that doesn’t answer your question but have you tried with a simple line-line intersection algorithm ?

You could iterate over the edges of your polygon and check if the line intersects at least one of them.

edit: Not sure about this other suggestion either but you could also use the cast() function from this Ray-Casting coding challenge.

2 Likes
6

Yes, iterating over the lines of a polygon and checking line-line is one standard way of detecting line-polygon. For better performance, be sure to return true as soon as you detect the hit rather than completing the loop.

Jeffrey Thompson has a nice online demo of poly-line collision here:

4 Likes
7

Jeffrey Thompsons example is perfect, thanks for the link :slight_smile:

Any ideas how I could change his example so there is no detection if the line has its one end in one of the vertices of the polygons? Otherwise I will get detections all the time, since my perspective lines origin from the edges of the polygon…

1 Like
8

You could check if the point at mouse position is inside the polygon. If not, look for intersections.

Annotation 2020-01-14 150618
Annotation 2020-01-14 1506181072×646 42.1 KB

An example sketch in Python mode

ngones = 20 
theta = radians(360) / ngones
startPnt = PVector(750, 100)

def setup():
    size(1000, 700, P2D)
    strokeWeight(2)
    smooth(8)
    
    global polygon, edges
    
    #Create vertices of a random polygon
    vertices = []
    for i in xrange(ngones):
        r = random(140, 200)
        x = width/2 + cos(theta*i) * r
        y = height/2 + sin(theta*i) * r
        vertices.append(PVector(x, y))
       
    #Creates a polygon from a list of vertices
    polygon = createPolygon(vertices) 
    
    #Store edges of the polygon in a list
    edges = [] 
    for i in xrange(ngones):
        v1 = vertices[i]
        v2 = vertices[(i+1)%ngones]
        edges.append((v1, v2))
        
    
        
    
def draw():
    background("#FFFFFF")
    
    #Draw Polygon
    shape(polygon)
    
    #Draw line from start-point to mouse position
    line(startPnt.x, startPnt.y, mouseX, mouseY)
    
    #As long as the end-point of the line (mouse position) is NOT inside the polygon
    if not contains(polygon, mouseX, mouseY):
        
        #Look for intersections
        isCrossed = False
        for edge in edges:
            if intersect(startPnt, PVector(mouseX, mouseY), edge[0], edge[1]):
                isCrossed = True
                break
            
        #If polygon is crossed by line --> do something
        if isCrossed:
            stroke(255, 30, 40)
            
        #Else, keep things as they are
        else:
            stroke(30, 100, 255)
    else:
        stroke(30, 100, 255)
                

    

        
    
    
    
    
def createPolygon(verts):
    
    '''Create a PShape from a list of vertices'''
    
    poly = createShape()
    poly.beginShape()
    poly.stroke(20)
    poly.strokeWeight(3)
    for v in verts:
        poly.vertex(v.x, v.y)
    poly.endShape(CLOSE)
    
    return poly
    
    
def contains(poly, x, y):
    
    '''Returns a boolean.
       Determine whether a point lies inside a shape/polygon or not.'''
    
    N = poly.getVertexCount()
    isInside = 0
    
    for i in xrange(N):
        v1 = poly.getVertex((i+1)%ngones)
        v2 = poly.getVertex(i)
        
        if (v2.y > y) != (v1.y > y):
            if x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x:
                isInside = not isInside
                
    return isInside




def intersect(p1, p2, p3, p4):
    
    '''Returns a boolean.
       Check if 2 lines are intersecting. Option: returns location of intersection point'''
    
    uA = ((p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x)) / ((p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y)) 
    uB = ((p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x)) / ((p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y))
    
    if uA >= 0 and uA <= 1 and uB >= 0 and uB <= 1:
        return 1 
                 
        ### Option, returns location of intersection point ###
                       
        # secX = p1.x + (uA * (p2.x-p1.x))
        # secY = p1.y + (uA * (p2.y-p1.y))
        
        # return PVector(secX, secY)

The contains function in Processing Java:

//Function to determine whether a point is inside a shape/polygon or not
boolean contains(PShape shp, float x, float y){
    int N = shp.getVertexCount();
    boolean isInside = false;
    for (int i = 0; i < N; i++){
        PVector v1 = shp.getVertex((i+1)%N);
        PVector v2 = shp.getVertex(i);
        if ((v2.y > y) != (v1.y > y)){
            if (x < (v1.x - v2.x) * (y - v2.y) / (v1.y - v2.y) + v2.x){
                isInside = !isInside;
             }
         }
    }
    return isInside;
}
5 Likes