Get Interior Angle of Polygon Java

[PrisonLove]

Hey so I'm trying to find the interior angle between 2 edges of a polygon to determine if the polygon is concave or not. I have all of the edges stored in an ArrayList and just want to loop through it, calculate the angle for each pair of edges, and if one is above 180? then I know the polygon is concave. The problem is I can't figure out how to calculate this interior angle. The two edges are next to one another so there's 3 points to work with. Any help?

Thanks!

 

[GetTriggerUnit-]

View attachment 39838

40 = 30² + 25² - 2(30)(25) * sin(x)
40 = 1525 - 1500(sin(x))
-1485 = -1500(sin(x)))
0.99 = sin(x)
x = asin(0.99)
x = 81.9

there you go.

 

[Slapshot136]

so you have 3 (x,y) points? lets call them a,b,c

I would visualize a triangle (A,B,C), where A is the side opposite a, etc.

then use the cosine rule (b^2 = a^2 + c^2 - 2ac cosB)
(this is to solve for the angle b, there are other variations of it)

you get cos b = (a^2+c^2-b^2/2ac) -> b = cos^-1 (a^2+c^2-b^2/2ac)

then you would want to find the center of the triangle and check if it lies inside your polygon or not, if it lies inside of it then the angle is as-is, if it lies outside your polygon, you want to take 360 - your angle to find out what it is

(or you can skip the angle and just take the average x/y of the 3 points, see if it lies inside the polygon or not)

 

[PrisonLove]

I'm having trouble putting this into Java code. Could someone help me out.

Assume you have an [ljass]ArrayList<edges>[/ljass]
and Edge is comprised of two [ljass]Point[/ljass] objects and thats it.

The algorithm would work as follows:

public boolean isConcave() {
    for (int i = 0; i < edgeList.size() i++) {
        edge edge1 = first edge;
        edge edge2 = second edge;
        float angle = angleBetweenEdges(edge1, edge2);
        if (angle > 180)
            return true;
    }
    return false;
}

Can someone help me turn the [ljass]angleBetweenEdges()[/ljass] into code?

Note that it has to find the interior angle of any polygon, both regular or irregular.

 

[GetTriggerUnit-]

You need at least 3 edges and their lengths in order to apply the Sine/Cosine/Tan formula.
Or 2 lengths and the angle, depending on what you're looking for.

In this case 3 edges and the polygon has to be a triangle. :<

 

[PrisonLove]

I can easily get the length of both edges, as I have the points, I just have to the distance formula (correct me if I am wrong here): d = sqrt((x2-x1)^2 + (y2-y1)^2)

  A_____E
   \    |
  B \ a |
    /   |
 C /____|D

If I wanted to find interior angle a of this polygon, which would no doubt be over 180 degrees, given sides A-B and B-C, how do I do that?

 

[GetTriggerUnit-]

I wasn't getting your question well. Basically, you want to get "a"'s value?

 

[PrisonLove]

Yes, exactly, where 'a' can be ANY of the interior angles for an irregular polygon with any amount of sides

 

[saw792]

So we've established that you can work out the angle between 3 consecutive points using the cosine rule. What hasn't been cleared up completely is how to determine if this angle is inside the polygon or outside the polygon.

Unfortunately, the angle between the 3 points (2 edges) is irrelevant because every single angle you produce using the cosine rule as above will be less than 180 degrees. Thus working out the angle between the edges is useless in finding whether the polygon is obtuse. You cannot solve this problem by separating the edges without taking it in context to the rest of the shape.

Really I am just repeating what Slapshot said above in his final comment as it seems nobody has taken notice yet

The key is finding whether the center point of each triangle is within the polygon or not. This is actually quite difficult to do as once again you can't separate the triangle from the rest of the polygon or you won't be solving the problem and we're back to the angle problem. Really what you need to do is take 3 edges at a time instead of 2.

Given your three consecutive edges you can then solve the problem by adding a fourth line connecting the first and last points. If this line intersects with the second edge (i.e. the middle edge of the three) then the shape is concave. If it doesn't then you check the next combination of three edges.

Example:
Shape 1 has 5 edges.
First edges to check: 1, 2 and 3.
If line connecting first point of 1 and last point of 3 intersects with edge 2, concave (exit).
Otherwise check edges 2, 3 and 4.
Etc.

I would advise first checking if there are only 3 edges on the shape first as then you can immediately know it's not concave, and your algorithm may have problems when dealing with three sided polygons due to the fourth edge being the same as the first edge.

Hope this helps!

 

[PrisonLove]

Thanks for the help but I don't think that would work and here's why. Suppose the first three edges in the polygon I drew above are ordered D-E, E-A, A-B. The first point if D-E and the last point of A-B form a triangle that doesn't intersect the second edge (E-A), however the polygon is still concave.

On a side note, what is the formula to find out if two line segments intersect anyway?

Isn't there some mathematical formula to find the interior angle of an irregular polygon? The information you have to work with is the length of all the sides and the number of sides.

 

[Slapshot136]

On a side note, what is the formula to find out if two line segments intersect anyway?

I think that this is what we need (i.e. for the intended purpose, the actual angle dosen't matter)

first check that the slopes are not equal
if the slopes are equal, that means that they are either the same line, or don't intersect -> test a point and see if it's the same

if they are not equal, then you can find where they intersect via

x_inter = (y_inter_1 - y_inter_2)/(slope_2 - slope_1)

- this will give you the x location of where they intercept, you can find the y value as well by substututing the answer into one of the line equations, - then checking that the point of intercept is within the square created by your 4 boundary points (you have 2 lines, 2 points on each line, make a square with them, etc.)

now for the formula to check if a polygon is concave or not

create a 2nd polygon by looping through all the points of the first, with the points of the new polygon being the average of 3 points in the old polygon, then checking for any intersecting lines between the new polygon and the old polygon

edit: image

the red poly is your original, the black one is the new one you compare against, and the small blue lines show which 3 points you averaged to find the corner of the new polygon from - basically if you find any intersections between the new one and the old one (i.e. some points of the new one lie outside of the old one), then your old one was concave

edit: I missed a point on the bottom, but it's not essential to solving this problem

 

[PrisonLove]

x_inter = (y_inter_1 - y_inter_2)/(slope_2 - slope_1)


So for this in order to get y_inter would the formula be: y_inter = y - slope*x ?

Also, is there really no way to just calculate an interior angle of a polygon given the length of all its sides, the number of sides, and the locations of the points? I just need that one calculation to make my algorithm work. Thanks for the help by the way.

 

[Slapshot136]

x_inter = (y_inter_1 - y_inter_2)/(slope_2 - slope_1)

So for this in order to get y_inter would the formula be: y_inter = y - slope*x ?

y_inter is what you get when you substitue 0 as x in the equation
actually I worded that badly, at the left x_inter is the x value of where the 2 lines meet, y_inter_1 is the y-intercept of the first line


it's easy to calculate the angle, but the hard part is determining if it's interior or not, since you need to look at the entire rest of the polygon for that... but go with what I have above, look at the entire polygon, and then you can get the angle, but you will always get the smaller angle, to find the greater angle you need to know if the point is convex/concave or not already, which is what you get if you apply the above

 

[PrisonLove]

Okay, but in order to get the y-intercepts to plug ito the x_inter formula you would need to calculate y = mx+b ==> b = y - mx, where m is obviously the slope, correct?

Please let me know if I am wrong.

Edit: I also just had a thought. If I sum up all the angles of the polygon and find that it is not equal to what should be the sum of the interior angles ((n-2)*180)/n, then would that mean one of the angles must be concave, or am I sorely mistaken.

 

[Slapshot136]

Edit: I also just had a thought. If I sum up all the angles of the polygon and find that it is not equal to what should be the sum of the interior angles ((n-2)*180)/n, then would that mean one of the angles must be concave, or am I sorely mistaken.

you are partially correct, but it would not work 100% of the time

first, how would you get all the angles? just like above and then assume that they are all < 180 is what I am assuming
then if there is 1 that should have been > 180, you will catch it, BUT if there are 2, or something odd like that, you wouln't be able to tell which one/etc. without some more analysis (and you won't be able to tell which angle is wrong if they are the same angle)


and yes, to get the y-intercepts you would go y=mx+b, solve for m=(y1-y2)/(x1-x2), then solve for b (insert x1 and y1 as x,y), then set x=0 and solve for y

 

[PrisonLove]

I really do appreciate the help, but I have another idea, which may be wayy easier. If the cross product (a magnitude in this case since we're working with 2D objects) of any of the vertices in the polygon is negative, would that mean the polygon is concave? I read this and what to confirm whether or not it is true.

Edit: This method worked! Thanks guys!

 

[Slapshot136]

I don't quite get that method, but I am interested (now that I spend some time thinking how to do this I hear that there is a better way.. im curious), can you explain it?

 

[PrisonLove]

Basically what you do is create a list of all the edges of the polygon and then compare the cross products between each pair of consecutive edges. If they are all of the same sign, your polygon is convex, otherwise it is concave.

I don't know what the exact mathematical details of it are, but I was rifling through an OpenGL textbook and found this method. Surely enough it works. I have a couple of bugs to work out, but I think that's just an error in my coding.

 

[Slapshot136]

ah I think I get how it works - thanks