17
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ @LuisMendo The pairs of points are coordinates of the vertices. The order of the pairs determines the location of the edges. \$\endgroup\$ – nph Aug 23 '20 at 23:48
  • \$\begingroup\$ @LuisMendo I know, just clarifying that you should ALSO return true if the point is barely on the edge of the polygon. \$\endgroup\$ – nph Aug 23 '20 at 23:57
  • 7
    \$\begingroup\$ Can't I take two separate inputs for the point and the polygon, or x and y coordinates of each point paired already? \$\endgroup\$ – Bubbler Aug 24 '20 at 1:22
  • 1
    \$\begingroup\$ @Bubbler yes, you can. \$\endgroup\$ – nph Aug 24 '20 at 11:04
  • 2
    \$\begingroup\$ 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 \$\endgroup\$ – jk. Aug 25 '20 at 10:50

13 Answers 13

Active Oldest Votes
11
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Love the idea of using shoe lace here \$\endgroup\$ – Jonah Aug 24 '20 at 2:44
  • \$\begingroup\$ 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..) \$\endgroup\$ – Kevin Cruijssen Aug 24 '20 at 7:53
  • 2
    \$\begingroup\$ @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! \$\endgroup\$ – Neil Aug 24 '20 at 9:27
  • 1
    \$\begingroup\$ @Neil Hehe, when the cumbersome challenge I/O actually saves bytes over a more natural input format. Pretty funny and ironic, but nice!. :) \$\endgroup\$ – Kevin Cruijssen Aug 24 '20 at 9:28
10
\$\begingroup\$

Wolfram Language (Mathematica), 26 bytes

Polygon@#2~RegionMember~#&

Try it online!

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 100 bytes by merging the loops, discarding the 2nd parameter of .slice() and going bitwise (returns 0 or 1). \$\endgroup\$ – Arnauld Aug 24 '20 at 6:36
  • \$\begingroup\$ -2 bytes from @Arnauld's improvements. \$\endgroup\$ – Shaggy Aug 24 '20 at 8:38
4
\$\begingroup\$

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?

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ "Is this too boring?" Not at all. \$\endgroup\$ – user Aug 27 '20 at 1:07
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ @ceilingcat Nice - thanks! :D \$\endgroup\$ – Noodle9 Aug 24 '20 at 21:37
  • \$\begingroup\$ 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. \$\endgroup\$ – user Aug 27 '20 at 2:23
  • 1
    \$\begingroup\$ @ceilingcat Very nice - thanks! :D \$\endgroup\$ – Noodle9 Aug 27 '20 at 19:22
  • 1
    \$\begingroup\$ @user That's great - thanks! :D \$\endgroup\$ – Noodle9 Aug 27 '20 at 19:22
  • 1
    \$\begingroup\$ @user Oh yeah, that's done - thanks again! :-) \$\endgroup\$ – Noodle9 Aug 27 '20 at 20:07
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

><>, 92 bytes

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

Implements Neil's shoelace formula technique.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Would it be much longer without the package? \$\endgroup\$ – user9207 Aug 24 '20 at 15:48
  • 1
    \$\begingroup\$ Apparently not ;-) But I like the simplicity, even though it cannot rival Mathematica. \$\endgroup\$ – ojdo Sep 17 '20 at 8:45
1
\$\begingroup\$

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?
}
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Aug 24 '20 at 15:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Dominic van Essen Aug 24 '20 at 16:31
  • \$\begingroup\$ ah, must be the counterclockwise stipulation in the other challenge. \$\endgroup\$ – Giuseppe Aug 24 '20 at 16:37
  • \$\begingroup\$ I may not be the GOAT (greatest of all time), but I am happy to be the goad. \$\endgroup\$ – Giuseppe Aug 24 '20 at 16:52
  • \$\begingroup\$ @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. \$\endgroup\$ – Dominic van Essen Aug 24 '20 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.