Is it in the polygon?

Question

The challenge

Given point and a path of points, say whether or not the point is in the polygon that is created by the path.

Also return true if the point is on an edge of the polygon.

Input

A list of pairs of integers.

The first 2 integers represent the point.

The remaining pairs (3rd and 4th, 5th and 6th etc.) represent the vertices of the polygon.

The edges are in the order of the input pairs.

The path is assumed to loop back to the first point of the path.

The input is assumed to be valid.

No three points in the path are collinear.

ex. 123 82 84 01 83 42

Output

A truthy/falsy value.

Test cases

Input -> Output

0 0 10 10 10 -1 -5 0 -> true

5 5 10 10 10 50 50 20 -> false

5 5 0 0 0 10 1 20 6 30 10 -40 -> true

This is code-golf. Shortest answer in bytes wins.

Answer 1

Charcoal, 52 50 bytes

≔⪪Ａ²θＦ⟦Ｅ³§θ⊖ιθ✂θ¹⟧⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰⁼⊟υΣυ

Try it online! Link is to verbose version of code. Explanation:

≔⪪Ａ²θ

Split the input into pairs of coordinates.

Ｆ⟦Ｅ³§θ⊖ιθ✂θ¹⟧

Calculate the area of three polygons: the one formed by taking the last, first and second points; the one formed from all of the points (including the test point); the one formed from all of the points except the test point.

⊞υ↔ΣＥι⁻קκ⁰§§ι⊕λ¹×§κ¹§§ι⊕λ⁰

Use the shoelace formula to calculate the area of that polygon.

⁼⊟υΣυ

Check whether the last area equals the sum of the first two. If this is the case, then the point lies within the polygon.

Answer 2

Wolfram Language (Mathematica), 26 bytes

Polygon@#2~RegionMember~#&

Try it online!

Answer 3

JavaScript (V8), 123 bytes

(x,y,...p)=>p.map((_,i)=>p.concat(p).slice(i,i+4)).reduce((n,[a,b,c,d],i)=>i%2<1&&a<x!=c<x&&y<b+(d-b)*(x-a)/(c-a)?!n:n,!1)

Ungolfed

(x, y, ...p)=>
  p.map((_, i) => p.concat(p).slice(i, i + 4)) // Group points into edges
  .reduce(
    (n, [a, b, c, d], i)=>                     // for every edge
      i % 2 < 1 &&                             // if it's actually an edge
      a < x != c < x &&                        // and x of point is within bounds
      y < b + (d - b) * (x - a) / (c - a) ?    // and point is below the line
      !n : n,                                  // then invert whether it's inside
    false
  )

TIO seems to be down for now, I'll add a link when I can (or if someone else happens to first)

Answer 4

PostgreSQL 12, 91 bytes

create function f(a polygon,b point,out o bool)as $$begin return a~b;end$$language plpgsql;

PostgreSQL has built-in polygon and point types, and a built-in operator @> (also spelt ~ to save a byte) to test containment.

...Is this too boring?

Answer 5

Java 10, 142 141 bytes

a->{var p=new java.awt.geom.Path2D.Float();p.moveTo(a[2],a[3]);for(int i=3;++i<a.length;)p.lineTo(a[i],a[++i]);return p.contains(a[0],a[1]);}

Try it online.

Explanation:

a->{                         // Method with integer-array parameter and boolean return-type
  var p=new java.awt.geom.Path2D.Float();
                             //  Create a Path2D object
  p.moveTo(a[2],a[3]);       //  Set the starting position to the third and fourth values in the list
  for(int i=3;++i<a.length;) //  Loop `i` in the range (3, length):
    p.lineTo(                //   Draw a line to:
             a[i],           //    x = the `i`'th value in the array
             a[++i]);        //    y = the `i+1`'th value in the array
                             //        (by first increasing `i` by 1 with `++i`)
  return p.contains(a[0],a[1]);}
                             //  Check if the polygon contains the first two values as x,y

Answer 6

Scala, 139 bytes

If the input is a (Int, Int) and a List[(Int, Int)] that doesn't have to be parsed, it's a bit easier

(x,p)=>(p.last->p.head::p.zip(p.tail)count{q=>(q._1._2<=x._2&x._2<=q._2._2|q._1._2>=x._2&x._2>=q._2._2)&(x._1<=q._1._1|x._1<=q._2._1)})%2>0

Try it online!

Using winding number, 140 bytes

x=>y=>_.sliding(2).map{case Seq((a,b),(c,d))=>val(e,f,l)=(b>y,d>y,(a-x)*(d-y)-(c-x)*(b-y))
if(!e&f&l>0)1 else if(e& !f&l<0)-1 else 0}.sum!=0

Try it online!

Uses the algorithm described here

With input as string, 186 bytes

i=>{val x::p=i split " "map(_.toInt)grouped 2 toList;(p.last->p.head::p.zip(p.tail)count{q=>(q._1(1)<=x(1)&x(1)<=q._2(1)|q._1(1)>=x(1)&x(1)>=q._2(1))&(x(0)<=q._1(0)|x(0)<=q._2(0))})%2>0}

Try it online!

Answer 7

C (gcc), ^{171 \$\cdots\$ 129} 126 bytes

Saved a whopping 13 19 35 bytes thanks to ceilingcat!!!
Saved 2 5 bytes thanks to user!!!

W,i,l;f(x,y,V,n)int*V;{for(W=i=0;i<n-2;W+=V[i-2]>y^V[i]>y?(l>0)-(l<0):0)l=(V[i++]-x)*(V[i+2]-y)-(V[i++]-y)*(V[i]-x);return W;}

Try it online!

Uses the winding number algorithm: if the winding number is truthy, the point lies inside the polygon, otherwise its falsey.

Answer 8

Python 3.8 (pre-release), 134 bytes

lambda x,y,p:sum((p[i+3]>y)^(p[i+1]>y)and(0<(l:=(p[i+2]-p[i])*(y-p[i+1])-(x-p[i])*(p[i+3]-p[i+1])))-(l<0)for i in range(0,len(p)-2,2))

Try it online!

Answer 9

R, 105 bytes

function(P,m=matrix(c(P,P[3:4]),,2,T))!sd(sapply(3:nrow(m)-1,function(k)sign(det(diff(m[c(1,k+0:1),])))))

Try it online!

Assumes no three points are collinear. Extends the algorithm described, e.g., here.

If we call the query point \$Q\$ and the ordered points of the polygon \$P_1\dots P_n\$, this traverses the points of the polygon, checking to see which side of the segment it's on by computing the signed area of the triangle (using the shoelace method) formed by \$Q,P_{i},P_{i+1}\$: A positive sign means to the left, and negative to the right if you're going counterclockwise, otherwise it's reversed. If all the signs are the same (i.e., the standard deviation of the signs is 0), then the point is within the polygon.

^{My computational geometry professor would be somewhat ashamed it took me four days for me to remember this point-in-polygon method. If I can find my textbook/notes, I'll post its description of the algorithm...}

Answer 10

APL (Dyalog Unicode), 63 bytes

{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}

Try it online!

Taken directly from an APLcart snippet. I'm not awfully sure of what's going on it it, and would be glad if someone could give a better explanation.

Input is taken as complex points.

Takes polygon on the left and point on the right.

Explanation

{⍵∊⍺:1⋄(¯1∊×d)∨1<|+/⍟d←(⊢÷1∘⌽)⍺-⍵}
{⍵∊⍺:1                           } return 1 if point is in list, otherwise:
      ⋄                       ⍺-⍵  subtract the point from each edge
                                   (gives all lines to from vertices to the point)
                       (⊢÷1∘⌽)     divide it by itself rotated by 1
                     d←            save it in d
                    ⍟              take the natural logarithm of each point
                  +/               and sum the vectors
                 |                 take the modulus
                                   (I think this gets the sum of angles)
               1<                  check if 1 is lesser than it
              ∨                    or
       (¯1∊×d)                     any of the points' signums equal (-1,0)

Answer 11

><>, 92 bytes

l[l0$21.>&-0=n;
{$&:2-&?!v{:{:{:@*{:}@@}@@}@@*-@@+
:0$0(?$-v>]
3pl2-00.>&08
{{{{600.>&-&084p

Implements Neil's shoelace formula technique.

Answer 12

Python 3, 133 bytes

Spatial packages to the rescue:

from shapely.geometry import*
def f(s):
 c=list(map(int,s.split()))
 o,*p=zip(c[::2],c[1::2])
 return Point(o).intersects(Polygon(p))

The geometric operation to use was a small gotcha. Polygon.contains(Point) does not cover the edge cases.

Answer 13

R, 139 127 118 116 bytes

Edit: -23 bytes by improving shoelace calculations thanks to goading by Giuseppe

function(i,S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])))S(P<-matrix(i,2))==S(P[,-1])-S(P[,c(1:2,ncol(P))])

Try it online!

Implements Neils beautiful approach of testing whether the 'slice of cake' formed by the triangle with the test-point + two perimeter points as vertices is equal in area to the area of the whole 'cake' (the test polygon) minus the area of the 'cake' with the 'slice' removed (the polygon using all points including the test point).

inside=
function(i)
    {                                           # S is helper function to calculate 2x the cake area using 
                                                # the 'shoelace' formula:
    S=function(m)abs(sum(m*c(1,-1)*m[2:1,c(2:ncol(m),1)])/2)            
    P=matrix(i,2)                               # 'cake with missing slice' = polygon including test point
    T=P[,c(1:2,ncol(P))]                        # 'slice of cake' = triangle of test point + adjacent polygon vertices
    O=P[,-1]                                    # 'the cake' = outer polygon excluding test point
    S(P)==S(O)-S(T)                             # do the areas add-up?
}