# 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 . Shortest answer in bytes wins.

• @LuisMendo The pairs of points are coordinates of the vertices. The order of the pairs determines the location of the edges.
– nph
Commented Aug 23, 2020 at 23:48
• @LuisMendo I know, just clarifying that you should ALSO return true if the point is barely on the edge of the polygon.
– nph
Commented Aug 23, 2020 at 23:57
• Can't I take two separate inputs for the point and the polygon, or x and y coordinates of each point paired already? Commented Aug 24, 2020 at 1:22
• @Bubbler yes, you can.
– nph
Commented Aug 24, 2020 at 11:04
• assuming the polygon needs 3 points and :. you need at least 4 points the example of valid input in the input section is not valid
– jk.
Commented Aug 25, 2020 at 10:50

# 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.

• Love the idea of using shoe lace here Commented Aug 24, 2020 at 2:44
• The input should be a single list of values. Not that it adds anything to the challenge, but all other answers comply to this rule, and would be able to save bytes by taking input in a more convenient input-format as well. Jus an FYI (although I hope OP loosens the input-rules instead..) Commented Aug 24, 2020 at 7:53
• @KevinCruijssen It turns out that taking the test point as part of the list actually saves me 7 bytes, so even with the 5 byte cost of splitting the points into pairs I'm still 2 bytes ahead!
– Neil
Commented Aug 24, 2020 at 9:27
• @Neil Hehe, when the cumbersome challenge I/O actually saves bytes over a more natural input format. Pretty funny and ironic, but nice!. :) Commented Aug 24, 2020 at 9:28

# Wolfram Language (Mathematica), 26 bytes

Polygon@#2~RegionMember~#&


Try it online!

# 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)

• 100 bytes by merging the loops, discarding the 2nd parameter of .slice() and going bitwise (returns 0 or 1). Commented Aug 24, 2020 at 6:36
• -2 bytes from @Arnauld's improvements. Commented Aug 24, 2020 at 8:38

# 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?

• "Is this too boring?" Not at all.
– user
Commented Aug 27, 2020 at 1:07

# 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


# 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!

# 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.

• @ceilingcat Nice - thanks! :D Commented Aug 24, 2020 at 21:37
• Try wn,i,l,a,b;f(x,y,V,n)int*V;{for(wn=i=0;i<n-2;a=V[++i]>y,l=(V[i-1]-x)*(V[i+2]-y)-(V[i++]-y)*(V[i]-x),b=V[i+1]>y,wn+=a^b?(l>0)-(l<0):0);return wn;} (couldn't post the link here). It's 145 bytes, but it uses the winding number algorithm, so I don't know if you'll want to use it for your answer. I'm a C newbie, so I'm sure you can golf it even more.
– user
Commented Aug 27, 2020 at 2:23
• @ceilingcat Very nice - thanks! :D Commented Aug 27, 2020 at 19:22
• @user That's great - thanks! :D Commented Aug 27, 2020 at 19:22
• @user Oh yeah, that's done - thanks again! :-) Commented Aug 27, 2020 at 20:07

# 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!

# 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...

# 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)


# ><>, 92 bytes

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


Implements Neil's shoelace formula technique.

# 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.

• Would it be much longer without the package?
– user9207
Commented Aug 24, 2020 at 15:48
• Apparently not ;-) But I like the simplicity, even though it cannot rival Mathematica.
– ojdo
Commented Sep 17, 2020 at 8:45

# R, 139127118 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?
}

• this is the shortest R implementation of the shoelace formula on the site, or at least the easiest to find, not sure if it'll help. Commented Aug 24, 2020 at 15:30
• Thanks Giuseppe. I'll see if I can use some of the tricks there. It has a couple of drawbacks here, though: (1) it requires that the last vertex equals the first, and, more importantly (2) it doesn't actually work, and can report negative areas: try it. Commented Aug 24, 2020 at 16:31
• ah, must be the counterclockwise stipulation in the other challenge. Commented Aug 24, 2020 at 16:37
• I may not be the GOAT (greatest of all time), but I am happy to be the goad. Commented Aug 24, 2020 at 16:52
• @Giuseppe Thanks a lot for the goading! It's really driven me to improve this answer. The new shoelace implementation used here is now not only as short as the 'shortest on the site', but also works for 'open' loops and never returns a negative area. Commented Aug 24, 2020 at 17:10