Suppose there is a polygon of N (and most importantly) vertices. And there is a point in an arbitrary place. It is necessary to determine whether it belongs to him or not. Points are represented as a structure:

struct point{ unsigned int x; unsigned int y;};

All solutions and algorithms that I found were written for quadrilaterals and for triangles. The main refinement polygon can be convex and not convex.

I stopped at the idea to calculate how many sides the beam emitted from the point passes. if an even number is not in a polygon. if not even - in a polygon. That is, we need to point vertices in a clockwise direction. Make the structure of the parties. But how to check? How to calculate these sides and make the intersection?

    2 answers 2

    Bad looking.

     bool result = false; int j = size - 1; for (int i = 0; i < size; i++) { if ( (p[i].Y < point.Y && p[j].Y >= point.Y || p[j].Y < point.Y && p[i].Y >= point.Y) && (p[i].X + (point.Y - p[i].Y) / (p[j].Y - p[i].Y) * (p[j].X - p[i].X) < point.X) ) result = !result; j = i; }
    • p - list of points
    • size - the number of points
    • result - whether the point is in the polygon

    The first line of the condition checks that point.Y hits between the values ​​of p[i].Y and p[j].Y , controls the direction of passage of the vertex, and provides a nonzero denominator of the basic formula.

    The second line checks whether the side p[i]p[j] left of the point .

    The third line forms a negative answer with an even number of sides on the left and a positive one with an odd number.

    • Is there any other way? - ParanoidPanda
    • @ParanoidPanda It seems they always use this one. It can be optimized by calculating the shape (rectangle) in advance, then most of the checks will be fast. - Athari
    • This method is not based on the "release of the beam" as I understand it - ParanoidPanda
    • one
      @ParanoidPanda The horizontal ray is the same, if my vision does not change. - Athari
    • ru.wikibooks.org/wiki/… - vovkas

    Let the beam be directed horizontally to the right.

    For each pair of adjacent points:

    1. First, check whether a pair of points (edges of a segment) lies on one side of the beam. If on one side - then the beam does not cross the side.
    2. If on different sides - you need to find the point of intersection of the beam and the line passing through the two data points. This is analytical geometry, in fact, I will not give a solution. If the intersection point is to the right of the point where the ray is coming from, then there is an intersection.

    It is necessary to take into account the special case when the beam passes through the top of the polygon:

    1. If the second points of both segments to which this vertex belongs are on the same side of the ray, then consider this as two intersections (or no intersection - the parity will be the same)
    2. If the second points on different sides of the beam - be considered one intersection.

    You can avoid having to check the passage through the points if the points of the polygon are at the grid nodes (for example, if the coordinates are always integers, or given with fixed accuracy): just move the point from where the beam comes up or down by a small amount (for example, machine epsilon) the beam is almost guaranteed not to pass through any of the points of the polygon.

    • Another special occasion is the side lying on the beam - sercxjo