Intereting Posts

limsup of average smaller than limsup
Difference between an isometric operator and a unitary operator on a Hilbert space
What is the probability that this harmonic series with randomly chosen signs will converge?
Deriving the Normalization formula for Associated Legendre functions: Stage $1$ of $4$
Solving a recurrence by using characteristic equation method
Convergence in measure of products
When is a flat morphism open?
Proving that every $2\times 2$ matrix $A$ with $A^2 = -I$ is similar to a given matrix
What are some examples of coolrings that cannot be expressed in the form $R$?
Complex number calculation
Factor ring by a regular ideal of a one-dimensional Noetherian domain
A vector space over $R$ is not a countable union of proper subspaces
Equivalent characterizations of ordinals of the form $\omega^\delta$
The Picard-Brauer short exact sequence
Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

Given the coordinates of a point $(x, y)$, what is a procedure for determining if it lies within a polygon whose vertices are $(x_1, y_1), (x_2, y_2), \ldots , (x_n,y_n)$?

- How many triangles in picture
- Line joining the orthocenter to the circumcenter of a triangle ABC is inclined to BC at an angle $\tan^{-1}(\frac{3-\tan B\tan C}{\tan B-\tan C})$
- Find the circle circumscribing a triangle related to a parabola
- What is a straight line?
- Fascinating Lampshade Geometry
- Is there a general formula for creating close approximations of regular polygons on a regular lattice?
- A Modern Alternative to Euclidean Geometry
- 3D coordinates of circle center given three point on the circle.
- The cow in the field problem (intersecting circular areas)
- If point is zero-dimensional, how can it form a finite one dimensional line?

I will assume the polygon has no intersections between the edges except at corners. Call the point $(x_0, y_0)$. First we determine whether we are on a line – this is simple using substitution and range checking. For the range checking, suppose we have a segment $(x_1, y_1)$, $(x_2, y_2)$. We check that $x_1\leq x_0\leq x_2$ or $x_2\leq x_0\leq x_1$ and do the same for $y$.

Now, if we aren’t on a line, we draw a ray from the point and count how many lines you intersect. If the line doesn’t intersect a corner or contain a non-degenerate segment of an edge, then an odd number of intersections should mean you are inside and an even number mean outside.

If we intersect with a corner, it is more difficult. Clearly, the ray could leave with it only intersecting a corner, but it could also pass through the corner without entering the polygon. One solution is to pick the ray so that it doesn’t intersect a corner or go along a line – this should always be possible. We can also use cross product to determine whether we are crossing the lines at their corner or not (just check if the adjacent vertices are on the same side of the line or not).

Representing a polygon by its edge path might not be the most useful, especially if you want to ask about inclusion for many points. Consider triangulating the polygon, which is trivial for convex polygons, and not difficult to find O(n log(n)) for hairier cases. Then determining whether the point is in the polygon reduces to whether it is in anyone of the triangles, which is easy.

If the polygon is: $A,B,C,D,E,F$

and the point is P.

($\text{(angle)}_1$ = angle between $PA$ and $PB$)

($\text{angle}_2$ = angle between $PB$ and $PC$)

($\text{(angle)}_3$ = angle between $PC$ and $PD$)

($\text{(angle)}_4$= angle between $PD$ and $PE$)

($\text{(angle)}_5$ = angle between $PE$ and $PF$)

($\text{(angle)}_6$ = angle between $PF$ and $PA$)

Clockwise are positive

counterclockwise are negative

If ( $\text{(angle)}_1+ …+ \text{(angle)}_1=2\pi\space \text{or}\space -2\pi$) is inside;

else (is zero then is outside;)

- Is there any matrix notation the summation of a vector?
- Graph-theory exercise
- Find if three points in 3-dimensional space are collinear
- fundamental group of $GL^{+}_n(\mathbb{R})$
- How would you explain why “e” is important? (And when it applies?)
- Prove that $e^x\ge x+1$ for all real $x$
- Asymptotics of $\prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) $
- How do you rebuild your Math skills after college?
- No subgroup of $S_5$ with order 40
- Please explain inequality $|x^{p}-y^{p}| \leq |x-y|^p$
- RSA: Fast factorization of N if d and e are known
- Closed sum of sets
- About the definition of Cech Cohomology
- Cubic trig equation
- What is the strategy-proofness of maximal lottery?