2
\$\begingroup\$

In order to improve the performance of my visibility graph generator I am trying to figure out the following.

Given the image below; is there a way to find out if a point is 'behind' the polygon? For example, from the blue points perspective green and pink would be behind the polygon so there is no need to do expensive visibility checks. Is there an easy way to figure this out?

Example
Basically, what I need to know is, when drawing a line from Blue to Green, does it start in or outside the polygon? There must be some simple math for this.

So green and pink are 'behind' and purple and red are in front.

\$\endgroup\$
  • \$\begingroup\$ is this in 2D ? , what do you mean exactly by "behind" ? Do you want to know if a point is to the left of a vector or to the right ? or do you want to test if between two points there is a poligon ? \$\endgroup\$ – Raxvan Mar 27 '14 at 13:09
  • \$\begingroup\$ It's 2D. I tried to explain a little better. \$\endgroup\$ – SaphuA Mar 27 '14 at 13:23
1
\$\begingroup\$

You can create an algorithm based of edge intersection.

The idea is to draw a line between the two points called a ray. This then acts as a line to test whether the polygons lines intersect.

You can do this in pseudo-code:

// Method in point:
bool IsPointBehindPolygon( testPoint, polygon)
{
    originPoint = this;
    ray = new Line(originPoint, testPoint);
    foreach(line in polygon.lines)
    {
        if ( LinesIntersect(line, ray) )
        {
            return true;
        }
    }
    return false;
}

You can then use this to find if it is "visible" according to a selected polygon and point:

void PolyFun()
{
    bool greenCheck = Blue.IsPointBehindPolygon(Green, polygon);
    bool redCheck = Blue.IsPointBehindPolygon(Red, polygon);

    Console.WriteLine( greenCheck ?
        "Blue says: Green is behind the shape" :
        "Blue says: Green is not behind the shape" );

    Console.WriteLine(redCheck ?
        "Blue says: Red is behind the shape" :
        "Blue says: Red is not behind the shape" );

        // Output: 
        //     "Blue says: Green is behind the shape
        //     "Blue says: Red is not behind the shape
}

Hope this helps.

\$\endgroup\$
0
\$\begingroup\$

I would not call this a that simple but here is now you can do it: Let's first have some notations (given the picture you provided):

A = green dot; B = pink; C = Purple; D = Red

Q = blue;

P = the polygon defined by a set of segments or lines.

So basically you want to know if any line QA , QB , QC , or QD intersects your polygon P The naive way to do this is to define the polygon with a a set of segments you can use line-line intersection to test this:

bool intersect(Polygon P, Line l)
{
   for_each(Line pl in P.segments)
        if(intersects(pl,l)) //line-line intersection
             return true;//line intersects polygon
   return false;
} 

if(intersect(P,QA)) -> point A is in front of the polygon relative to Q

To simplify the problem i think you want to check if any point A,B,C is visible from the players's perspective D and in this case you don't have to take a reference point Q you can just do intersect(P,AD), 'BD' and CD.

You would basically have to do this for each polygon in your scene which is not that efficient in the end (if you have a big scene). The best approach is to use spacial partitioning like a BSP tree (best for your case) but this is not that trivial to implement.

If you scene is small or relatively small you can use the approach described above and you can even improve this by adding a 2d Grid to store references to polygons that you want to test.

\$\endgroup\$

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.