2
$\begingroup$

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it?

An example to clarify what I mean:

Assume that we know the coordinates of the points a,b,c,d,e in the pentagon below. How can I calculate if the point α is actually inside the shape?

Image of a pentagon

I can calculate if a point is wrapped inside a square (nodes: a,b,c,d) by creating a boolean expression:

enter image description here

(α.x >= a.x AND α.x <= b.x AND α.y >= a.y AND α.y <= c.y)

$\endgroup$
2
  • $\begingroup$ If the rectangle's sides weren't parallel to the coordinate axes, you'd need pretty much the same algorithm for that as for the pentagon. $\endgroup$ Commented May 31, 2014 at 21:29
  • $\begingroup$ You could try Cauchy's integral formula.... $\endgroup$
    – abnry
    Commented Jun 1, 2014 at 0:03

2 Answers 2

1
$\begingroup$

Let $\alpha$ be located at $(x_\alpha,y_\alpha)$. Let $AB(x)$ be a function denoting the line connecting the points $A$ and $B$. Then we know that $\alpha$ is below the line if $AB(x_\alpha)>y_\alpha$. Use this for the other $4$ lines and see if you can create another boolean expression.

$\endgroup$
0
$\begingroup$

Choose an arbitrary point in the pentagon (say point $a$) and an arbitrary direction $\hat{u}$ not parallel to any of the five sides nor to any of the five lines from $\alpha$ to a vertex. Calculate the distances from A to each of the other points in the pentagon; let the maximum of those four distances be $\mu$. Choose point $\Omega$ be starting at $a$ and moving by $2 \times 5 \mu \hat{u}$; it is easy to show that $\Omega$ must lie outside the pentagon.

Now draw line the segment from $\alpha$ to $\Omega$ and test it against each line segment making up a side of the pentagon: The test, involving two line segments whose extended lines meet in a point $P$, is to determine if $P$ lies on both line segments (pass) or outside at least one of the segments (fail). Having tested against each of the 5 sides, there are five results. $\alpha$ is in the interior of the pentagon if and only if an odd number of the tests have passed.

This method works for any polygon.

$\endgroup$

You must log in to answer this question.

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