CODEWITHSUNDEEP
c++algorithmgeometry
vaati
vaati

Reputation: 162

Detect extreme points of a convex polygon

How can i get the extreme points of a convex polygon looking from a determined point? I'm trying to make this by points angle, the smaller and bigger angles is the extreme points, but when observer is closer to points, this is not valid.

This is my code:

Vec2* bigger = &points[0]; // pointer to point with bigger angle
Vec2* smaller = &points[0]; // pointer to point with smaller angle

Vec2 observer = rayCenter;

// iterate through all points of polygon
for(unsigned u = 0 ; u < points.size() ; u++)
{
    Vec2 distance = observer - points[u];

    if(distance.angle() < (observer - *smaller).angle())
        smaller = &points[u];
    if(distance.angle() > (observer - *bigger).angle())
        bigger = &points[u];
}

The result:

enter image description here

Where blue lines is the excluded points and yellow desirable points. Is there a best way to resolve this?

Sorry for my english.

Upvotes: 0

Views: 1285

Answers (3)

user1196549
user1196549

Reputation:

You shouldn't compare angles directly as there is a 360° wraparound.

Prefer to test "this point is more to the left" or "to the right" by computing the signed area of the triangle formed by the observer and two points.

Upvotes: 0

AnT stands with Russia
AnT stands with Russia

Reputation: 320797

Polygon vertex A is extreme for the given location of the observer, iff all other points of the polygon lie on the same side of the observer-to-A line (or, possibly, lie on that line).

If the polygon is known to be convex, then the criterion is greatly simplified. There's no need to analyze all other points of the polygon. The extreme point can be easily recognized by analyzing the locations of its two immediate neighbors.

If A is our candidate point and P and N are its adjacent points in the polygon (previous and next), then A is an extreme point iff both P and N lie on the same side of observer-to-A line.

vec_of_A = A - observer; // observer-to-A vector
vec_of_P = P - observer;
vec_of_N = N - observer;

productP = vec_of_A.x * vec_of_P.y - vec_of_A.y * vec_of_P.x;
productN = vec_of_A.x * vec_of_N.y - vec_of_A.y * vec_of_N.x;

if (sign(productP) == sign(productN))
  // A is an extreme point
else
  // A is not an extreme point

Some extra decision making will be necessary if P and/or N lie exactly on the observer-to-A line (depends on what point you consider extreme in such cases).

Upvotes: 2

dpmcmlxxvi
dpmcmlxxvi

Reputation: 1302

Compute a new convex hull using the points from the existing convex hull plus the observer point. In the new convex hull, the points that are adjacent to the observer point are your "extreme" points.

Here is a matlab implementation. Below is a sample output where the blue point is the observer point and the green polygon is the convex hull of the red points. The implementation returns the points (0,0) and (2,0).

sample

Upvotes: 0

Related Questions