CODEWITHSUNDEEP
algorithmmathpolygon
Himadri
Himadri

Reputation: 3012

Diagonal of polygon is inside or outside?

I have three consecutive points of polygon, say p1,p2,p3. Now I wanted to know whether the orthogonal between p1 and p3 is inside the polygon or outside the polygon.

I am doing it by taking three vectors v1,v2 and v3. And the point before the point p1 in polygon say p0.
v1 = (p0 - p1)
v2 = (p2 - p1)
v3 = (p3 - p1)

With reference to this question, I am using the method shown in the accepted answer of that question. It is only for counterclockwise. What if my points are clockwise.

I am also knowing my whole polygon is clockwise or counterclockwise. And accordingly I select the vectors v1 and v2. But still I am getting some problem. I am showing one case where I am getting problem.

alt text

This polygon is counterclockwise. and It is starting from the origin of v1 and v2.

Upvotes: 2

Views: 2162

Answers (3)

Michael Ulm
Michael Ulm

Reputation: 802

Since your points are cnosecutive, you can solve this problem by checking the orientation of the triangle p1 p2 p3. If the orientation is the same as the one of the polygon, then the diagonal is in the inside, else on the outside.

To determine the orientation of the triangle, the simplest way is to compute the signed area and check the sign. Compute

p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y

If the sign of this value is positive, the orientation is counterclockwise. If the sign is negative, the orientation is clockwise.

To be precise, the above method only gives you information on which side of the polygon the diagonal lies. Obviously, the polygon can still intersect the diagonal at later points.

Upvotes: 2

MSalters
MSalters

Reputation: 180303

Basically, a diagonal can be fully inside, fully outside, both inside and outside, and possibly overlapping one or more edges in all three cases. This makes it not entirely trivial to determine what you need.

From a mathematical side, there is actually not that much difference between the inside and the outside, except for such small details as the outside having infinite area. (At least for a 2D plane; on a sphere the inside and outside of a plygon are not sharply distinguished.)

You also have a subquestion about the ordering of your polygon edges. The easiest way is to sum all angles between adjacent edges in order. This will add up to N*(pi/2). For CCW polygons, N is positive.

[edit] Once you know the direction, and if you have none of the hard cases listed above, the question is easy. The angle p0-p1-p2 is smaller than the angle p0-p1-p3. Hence, the edge p1-p3 lies at least partially outside the polygon. And if it crosses no other edge, it obviously lies fully outside the polygon.

Upvotes: 2

TautrimasPajarskas
TautrimasPajarskas

Reputation: 2796

Angle between any two vectors is

alpha = acos(v1.x * v2.x + v1.y * v2.y)

Since you now can have the angle between 

v1 and v3 = alpha1; v1 and v2 = alpha2;

You can check if alpha2 is inside alpha1:

function normalize(a):
    if a > 2 * pi then a - 2 * pi
    else if a < 2 * pi then a + 2 * pi
    else a

alpha1 = normalize(alpha1)
alpha2 = normalize(alpha2)

if (alpha2 < alpha1) then is_between
else is_not_between

This is not very complete, but you should get the idea.

EDIT: it won't work if the polygon is overlapping as MSalters noted.

Upvotes: 0

Related Questions