1
\$\begingroup\$

Given four points (a,b,c and d) how do I find the extreme points (b,d) from the perspective of the player (p).

I was trying to do it by finding the angle to the centre of the quadrilateral then checking for the furthest point either side but that obviously wouldn't work when the player is parallel to a point.

Any nudges in the right direction would be welcome.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Basically I'm trying to create a sight cone using lines drawn to each point of a wall. If the line ends at an extreme point it should carry on until it intersects with another wall. If it is not an extreme point it should just terminate at it's intersecting point of a wall. \$\endgroup\$ – fatnic Oct 5 '15 at 15:40
1
\$\begingroup\$

I would pick any point on the shape* as starting value of extremes and iterate over all other points on shape testing whether they lie on left/right side of line from P to left/right extreme respectively, reassigning value if new extreme is found:

void extreme_points(Point& left, Point& right, Point& p, std::vector<Point> polygon)
{
  left = right = polygon[0];
  for(auto v : polygon)
  {
    if(isLeft(p, left, v) > 0.0)
    {
       if(abs(isLeft(p, right, v)) > Epsilon)       
         left = p;
       else { /*handle special case where P is parallel,*/}
    }
    if(isLeft(p, right, v) < 0.0)
    {
       if(abs(isLeft(p, right, v)) > Epsilon)       
         right = p;
       else { /*handle special case where P is parallel,*/}
    }
  }
}

where isLeft is well-known "sign test". Example of implementation:

float isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y)
           - (P2.x - P0.x) * (P1.y - P0.y) );
}

You may also want to handle cases for almost zero values(all three points are on the same line) picking, for example, the closer one. You can also find a library with more accurate isLeft implementation.
*this should work for any convex and star-shaped polygons.

| improve this answer | |
\$\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.