aniervs's blog

Finding Extreme Points on Convex Polygons
By aniervs, history, 6 years ago, In English

Recently I've been studying some geometry, and now I want to know the different ways of computing the extremal Points on a set of points for a fixed direction, please leave it in the comments.

Thanks in advance.

  • Vote: I like it
  • +30
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

How?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +3 Vote: I do not like it

    I know one way to do it. We want the point with maximal projection over a fixed vector. Let's treat points as vectors starting at $$$(0,0)$$$. We know that $$$A \cdot B = |A|\cdot|B|\cdot \cos{\theta}$$$, where $$$\theta$$$ is the angle between $$$A$$$ and $$$B$$$. Well, if $$$B$$$ was the $$$X$$$-axis, then $$$|A|\cdot \cos \theta$$$ is the $$$X$$$-component in this new system, so $$$A \cdot B$$$ is the projection of $$$A$$$ over $$$B$$$, scaled by $$$|B|$$$. Therefore, the point with maximal projection over $$$B$$$ is the point with maximal dot product with $$$B$$$, since all projection are scaled by some constant amount -$$$|B|$$$. To find that point we can maintain the upper hull of the points increasingly sorted by $$$X$$$ and do binary search. To find the point with minimal projection over a fixed vector we can do the same but maintaining the Lower hull

    But I've read in some article that there are a few ways to do it, so I want to know those ways.

    → Reply