An intersection: inside, outside or on the border
A city service assigns crossings to districts: each crossing is served by the district it stands inside. But district boundaries are often drawn right along streets, and a crossing may turn out to be exactly on a boundary; the service divides those separately, and they must be found without errors. Given a district, a polygon, and a list of crossings. For each say whether it is inside the district, outside or on the boundary.
The second and third tests are the Almaly and Bostandyk districts of Almaty and the crossings around them from OpenStreetMap, in integer metres on the grid of this catalogue’s road map.
Input
The first line holds the number of vertices n (3 ≤ n ≤ 2000), then n lines with vertex coordinates x y in order of traversal, clockwise or anticlockwise. The polygon is simple: sides do not intersect or touch, except neighbouring ones at a shared vertex; vertices do not repeat, and three consecutive vertices may lie on one line. Then the number of crossings q (1 ≤ q ≤ 1000) and q lines with their coordinates. All coordinates are integers, |x|, |y| ≤ 10⁹.
Output
For each crossing on a line of its own: inside if it is strictly inside the polygon, outside if strictly outside, and border if on a side or at a vertex.
Examples
Example 1
11 0 0 12 0 13 3 12 6 10 3 8 6 6 3 4 6 2 3 0 6 -1 3 10 1 3 5 3 11 3 3 1 9 5 6 3 14 3 -1 3 -2 3 12 6
inside inside inside inside outside border outside border outside border
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Draw a ray east from the crossing and count how many times it crosses the boundary. An odd number means inside. Now draw a ray that passes exactly through a vertex of the polygon. How many crossings will you count if the boundary passes through the ray right across? And if it only touches it from below?
2Hint 2
The rule that settles all vertex cases at once: a side counts as crossed if exactly one of its ends lies strictly above the ray. Horizontal sides are then never counted. Check this rule on a vertex through which the boundary passes right across and on a dip vertex.
3The idea
First the boundary: a point lies on side AB if the cross product cross(A, B, P) is zero and the point is inside the rectangle spanned by A and B. If it is on no side, count the crossings of the eastward ray by the half-open rule. Everything in integers: no division, no fractions.
4Walkthrough
For each side A → B and point P compute s = cross(A, B, P). If s = 0 and P is in the rectangle of the ends, the answer is border. Otherwise, if exactly one of Ay > Py, By > Py holds, the side crosses the ray’s line. The crossing is east of the point when the point is to the left of a side going up (s > 0) or to the right of one going down (s < 0): that is the single condition (s > 0) = (By > Ay). Each such crossing toggles “inside/outside”.
Why the rule is right at vertices. It treats a vertex on the ray as lying slightly below it. If the boundary passes through the ray right across, one of the two sides at the vertex goes up and the other down, and exactly one is counted: one crossing, as it should be. If the boundary touches the ray from below or above, both sides are on one side: both are counted or neither, and the parity does not change. A horizontal side on the ray has no ends strictly above and strictly below at once and is not counted: its neighbours settle everything themselves.
There is no overflow: coordinate differences are up to 2·10⁹, products up to 4·10¹⁸, their difference up to 8·10¹⁸, which fits in int64.
4+Solution
5Complexity
O(n) per crossing, O(nq) in all: up to two million side checks. If there were millions of crossings, the sides would be worth laying out by horizontal strips, as in the article: then each ray looks only at the sides of its strip.
6Common mistakes
- Side ends included. A side is counted if the point’s y is in the segment [min, max] of its ends. A ray through a vertex where the boundary passes right across touches both sides at it, and the crossing is counted twice. This is the wrong solution of the problem. On Almaly district from the second test it errs on 46 crossings of a thousand: district boundaries are drawn through crossings, and rays keep hitting vertices.
- The crossing by division. Computing the x of the crossing as a fraction and comparing it with the point’s x in
double: with coordinates around 10⁹ rounding decides which side the point is on, and points on the side itself become now inside, now outside. - The boundary by crossings. Trying to notice “on the boundary” while counting crossings rather than by a separate check: points on horizontal sides and at dip vertices are not caught this way.
Algorithms behind it
O(n) per point
2 problems
GEO
Technique
Vectors and orientation
The sign of the cross product is a left or right turn; almost all of computational geometry stands on it.
O(1) per turn
2 problems