I could operate with the angles, but I do not have the angles calculated yet (and would like to avoid having to do that). It would be possible to calculate and cache the local-coordinate-frame angles, though.

This is a routine that is run on every vertex of every convex polygon within the convex decomposition of every physically simulated object, so it should be as fast as possible.

I've got a corner of a convex polygon, so I have a vector from vertex to vertex-1 and another vector from vertex to vertex+1. It is easy to see that for a convex polygon, the interior of the polygon lies in the direction of the average of these two vectors.

I want to determine given any vector whether it points into that region or outside of it. Can I accomplish this using only cross products and dot products and similar fast operations? I am thinking about eventually offloading these calculations to a vertex shader, but as it changes the number of vertices required depending on an object's velocity, I imagine the logic could get dicey. Either way, before I attempt a vertex or geometry shader implementation I had better get a CPU solution working correctly first.

Here's an example: I want to find if N is between A and B. A points right at -10 (=350) degrees, B is at 15 degrees. So it looks somewhat like the < symbol. Function should return true only if N is between -10 and 15, between 350 and 375, etc. This was just to paint a mental picture, the input to the function are vectors: I want to avoid operating on angles because I do not want to call atan2.

It may help if it is known that A cross B is always positive. This is the case because my polygon is CCW winded and convex.

  • \$\begingroup\$ You hit the nail on the head with your update there. \$\endgroup\$ – Steve H Jan 14 '12 at 15:33
  • \$\begingroup\$ You should at least make your "update" an answer. \$\endgroup\$ – Josh Jan 16 '12 at 18:16

I think the best way to solve this, given A x B > 0, is to simply check A x N and N x B are also both positive. It seems to be working well.

  • 1
    \$\begingroup\$ the cross product produces a vector. how do you determine if it's "positive"? \$\endgroup\$ – TravisG Jan 16 '12 at 20:10
  • 2
    \$\begingroup\$ Sorry I'm working in 2D, it's a scalar in that case. The entire problem only really makes sense inside of a plane anyhow, because the 3 vectors need to be coplanar for "in between" to make any sense. Not that this concept can't be extended to 3D, but I'm not dealing with that. \$\endgroup\$ – Steven Lu Jan 16 '12 at 21:12
  • \$\begingroup\$ edit: nevermind, some research showed that there actually is a cross product between two vectors in 2D . weird. \$\endgroup\$ – TravisG Jan 16 '12 at 23:15
  • 1
    \$\begingroup\$ @TravisG In essence, the 'cross product' in 2d is the dot product between one of the two vectors and a vector orthogonal to the other - it's an immensely useful operation for this sort of 'side' information (and is at the core of the solution to the classic 'steer this 2d car' game programming interview question). \$\endgroup\$ – Steven Stadnicki Jun 19 '13 at 1:10
  • 3
    \$\begingroup\$ You can get even easier, when both cross AxN and NxB have the same sign you are done, no matter if AxB is positive or not \$\endgroup\$ – Martin Dec 15 '13 at 23:10

Endpoint vectors A and B, in 2d space. Third vector, C, might be somewhere between them. This is what we are checking for:

if (A + (B - A) * (Distance(A, C) / Distance(A, B)) = C) 
    // line segments intersect.
  • \$\begingroup\$ Hey Ryan, welcome to the site! If you could expand your answer a bit more by explaining the steps of your question and the reasoning behind it you'd get some votes for sure. Thanks. \$\endgroup\$ – MichaelHouse Jun 19 '13 at 0:23
  • \$\begingroup\$ Shouldn't it be == C not = C? Also, the question wasn't asking if they intersect. \$\endgroup\$ – AustinWBryan Aug 21 '18 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.