2D polygon vertex normal facing inward/outward?

Question

I want to test if a vector (a polygon vertex normal actually) is facing outward or inward. The polygon winds CW, edges goes from A (filled circle) to B (stroked circle). I have these normals a a result of preliminary calculations, now I want to test their facing.

enter image description here

Like this. Gray normals should be invalid while green normals should be validated. Probably I could do it by calculating angles, then simply compare them, but I really want to spare trigonometric calls here.

Is there any cheap method that compare only the "slopes" somehow? Something like this Bryce Boe CCW algorithm in this http://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/

score 1 · Answer 1 · 2014-10-24T16:37:34.830

1

The sign of the cross product of an edge vector with a normal vector will tell you on what side of the edge the normal vector points.

Compute (Xb - Xa).Ny - (Yb - Ya).Nx.

This will work for convex polygons.

For general polygons, you will have to intersect the supporting line of the normal with the polygon outline; you will find an even number of intersections (some possibly double); by linking them even-to-odd, you will know what portions of the line are inside or outside.

enter image description here

edited Oct 24 '14 at 16:37

answered Oct 24 '14 at 16:24

Thanks. Raycasting would be a huge overhead. I think of test the normal against both neighbouring edges, so it can work for concave stuff, isn't? – Geri Borbás Oct 24 '14 at 16:37
@YvesDaoust: Is it not possible to take advantage of the fact that the winding direction of the vertices is known? – rici Oct 24 '14 at 17:26
@rici That's my guess as well. – Geri Borbás Oct 24 '14 at 17:36

mrk · Accepted Answer · 2014-10-24T16:32:34.453

1

If you take the normal vector together with the vector formed by the two points of the segment (tail to head is clockwise), then to get from the segment vector to the normal you have to move counter clockwise. Call the normal N and the segment vector S, the counter-clockwise check becomes:

if(cross(S, N) > 0)
   // Bad
else
   // Good

The cross product is computed this way:

int cross(Vector p, Vector q)
{   return (p.x*q.y - p.y*q.x);
}

So if the normal is N = (0, 1) and S = (1, 0), the cross product gives 1*1 - 0*0 = 1 > 0 and this tells you that the normal is pointing out.

edited Oct 24 '14 at 16:32

answered Oct 24 '14 at 16:25

mrk

3,061
1
29
34

Thanks, it seems something like http://stackoverflow.com/a/1560510/215282... I'll implement some testbed. – Geri Borbás Oct 24 '14 at 16:41

score 1 · Answer 3 · answered Oct 25 '14 at 03:13

Cross product sign test suggested by the others is the solution.

public static bool PointIsLeftOfSegment(Vector2 point, Vector2 a, Vector2 b)
{
    float crossProduct = (b.x - a.x) * (point.y - a.y) - (b.y - a.y) * (point.x - a.x);
    return (crossProduct > 0.0f);
}

For the original question, I composed tests for both segments (considering acute angles as well).

bool acute = segmentA.IsPointLeft(segmentB.b);
bool leftA = segmentA.IsPointLeft(point);
bool leftB = segmentB.IsPointLeft(point);
bool outward = (acute) ? leftA && leftB : leftA || leftB;
bool inward = !outward;

Testbed just fine: https://vine.co/u/1137617915458592768

2D polygon vertex normal facing inward/outward?

3 Answers3