5
\$\begingroup\$

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.

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

2 Answers 2

5
\$\begingroup\$

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.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ the cross product produces a vector. how do you determine if it's "positive"? \$\endgroup\$
    – TravisG
    Jan 16, 2012 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, 2012 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, 2012 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\$ Jun 19, 2013 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, 2013 at 23:10
0
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\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\$
    – House
    Jun 19, 2013 at 0:23
  • \$\begingroup\$ Shouldn't it be == C not = C? Also, the question wasn't asking if they intersect. \$\endgroup\$ Aug 21, 2018 at 3:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .