CODEWITHSUNDEEP
algorithm
Vikas Acharya
Vikas Acharya

Reputation: 4152

How to find the intersect points in a polygon object

I have two polygons with points on the plane as shown below

enter image description here

The coordinates are as below (it's an array(x-axis,y-axis) i.e [x-val,y-val])

peppa:
0: (2) [0.24509992094864, 0.1669636438338341]
1: (2) [0.17643184493644434, 0.21545930801793528]
2: (2) [0.24810728194187487, 0.26326217699940646]
3: (2) [0.2821907065318698, 0.2119953320047852]

pig:
0: (2) [0.2877042016861337, 0.16904202944172414]
1: (2) [0.23607783796893547, 0.21753769362582534]
2: (2) [0.29171401634378014, 0.24594229693365605]
3: (2) [0.32429376043715763, 0.20991694639689515]
4: (2) [0.3037434603167195, 0.1912114759258847]

Now, I figured out where might the intersect happens like below.

peppa : Xmin = 0.17, Xmax = 0.28
pig   : Xmin = 0.23, Xmax = 0.32

peppa : Ymin = 0.17, Ymax = 0.28
pig   : Ymin = 0.23, Ymax = 0.32

Intersection happens if it satisfies,
      min(Xmax) > max(Xmin) && min(Ymax) > max(Ymin)
i.e     0.28        0.23        0.28        0.17

But, how to find the two intersection points as shown in the image?

I have gone through some algorithms but didn't understand anything. So, kindly help me with this.

Upvotes: 1

Views: 1328

Answers (1)

Adam Meyer
Adam Meyer

Reputation: 1525

The difficult part here is checking for an intersection point between 2 line segments as the polygons are just a collection of many line segments. So then to solve this you just need iterate through all of your line segments on one polygon, and then see if it intersects with any of the line segments on the second polygon

The intersection detection is all based on the work shown in this answer https://stackoverflow.com/a/1968345 - I remade it in javascript so it would be easier to read and easily checkable on my side.

I took the points you had and put them in an array for easy reading. I also assume that any language you do this in would store the polygon points in an array.

I then take that and make an array of line segments. Each line segment is made of 2 points. The end result is something like this [p0, p1], [p1, p2], [p2,p0]. I stored all that in an array for easy use.

Then I loop through every line segment on peppa, and compare it to every line segment on pig. If there is an intersection I log it out. This found 2 colisions when I ran it at { x: 0.2677543532697923, y: 0.2337098836931087 } and { x: 0.2646494979562556, y: 0.1906986616243169 }

var peppa = [
    [0.24509992094864, 0.1669636438338341],
    [0.17643184493644434, 0.21545930801793528],
    [0.24810728194187487, 0.26326217699940646],
    [0.2821907065318698, 0.2119953320047852],
];

var pig = [
    [0.2877042016861337, 0.16904202944172414],
    [0.23607783796893547, 0.21753769362582534],
    [0.29171401634378014, 0.24594229693365605],
    [0.32429376043715763, 0.20991694639689515],
    [0.3037434603167195, 0.1912114759258847]
];


//I highly recommend you automate this, but this will show you what data I am using for the loops
var peppaLineSegments = [
    [peppa[0], peppa[1]],
    [peppa[1], peppa[2]],
    [peppa[2], peppa[3]],
    [peppa[3], peppa[0]]
];

var pigLineSegments = [
    [pig[0], pig[1]],
    [pig[1], pig[2]],
    [pig[2], pig[3]],
    [pig[3], pig[4]],
    [pig[4], pig[0]]
];

//all points are a simple array of x,y

//line segment 1 is defined by 2 points
//point0, point1

//line segment 2 is defined by 2 different points
//point2, point3
function findLineIntersection(point0, point1, point2, point3){
    var s1_x = point1[0] - point0[0];
    var s1_y = point1[1] - point0[1];
    var s2_x = point3[0] - point2[0];
    var s2_y = point3[1] - point2[1];

    var s = (-s1_y * (point0[0] - point2[0]) + s1_x * (point0[1] - point2[1])) / (-s2_x * s1_y + s1_x * s2_y);
    var t = ( s2_x * (point0[1] - point2[1]) - s2_y * (point0[0] - point2[0])) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1){
        var intersectionX = point0[0] + (t * s1_x);
        var intersectionY = point0[1] + (t * s1_y);
        return {x: intersectionX, y: intersectionY};
    }

    return false;
}


for(var peppaLS of peppaLineSegments){
    for(var pigLS of pigLineSegments){
        //line segment 1 points
        var point0 = peppaLS[0];
        var point1 = peppaLS[1];
    
        //line segment 2 points
        var point2 = pigLS[0];
        var point3 = pigLS[1];
    
        var intersection = findLineIntersection(point0, point1, point2, point3);
        if(intersection){
            console.log("intersection at:", intersection);
        }
    }
}

Upvotes: 1

Related Questions