9
\$\begingroup\$

Background

The convex hull of a finite number of points is the smallest convex polygon that contains all of the points, either as vertices or on the interior. For more information, see this question on PGM which defines it very well.

Input

N+1 2-D coordinates (N >= 3) passed through STDIN (with other usual golf inputs allowed too) in the following format (the number of decimals can vary but you can assume it remains "reasonable" and each number can be represented as a float):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Output

A truthy value printed to STDOUT (or equivalent) if the first point in the list ((0.00;0.00000) in the example above) is in the convex hull of the other N points, and a falsy value otherwise.

This is , so the shortest solution in bytes wins.

  • Border cases: you can return any value (but don't crash) if the point lies on the border of the convex hull (i.e. on a side or on a vertex on the outer frontier of the hull), since it is a zero probability event (under any reasonable probability).

  • Forbidden: anything (language, operator, data structure, built-in or package) that exists only to solve geometric problems (e.g. Mathematica's ConvexHull). General purpose mathematical tools (vectors, matrices, complex numbers etc.) are allowed.

Tests

\$\endgroup\$
13
  • 3
    \$\begingroup\$ What is an "ad hoc data structure"? \$\endgroup\$
    – DavidC
    Commented Dec 11, 2015 at 18:25
  • \$\begingroup\$ "elementary functions/operators" is much too vague. \$\endgroup\$
    – xnor
    Commented Dec 11, 2015 at 18:27
  • \$\begingroup\$ @DavidCarraher: something like a Polygon, or a Triangle, or a Segment (anything that exists only to solve geometric problems). \$\endgroup\$ Commented Dec 11, 2015 at 18:28
  • 2
    \$\begingroup\$ @AlexandreHalm Your edit helped a lot. I think "elementary" isn't the right word. I thought it would eliminate general-purpose built-ins like sort or round. I think it's clearer to just say nothing specifically made for geometry is allowed. What, though, about a function to add two lists as vectors? Or a function to find the argument (angle) of a complex number? \$\endgroup\$
    – xnor
    Commented Dec 11, 2015 at 18:42
  • 1
    \$\begingroup\$ This is why the Diamonds request people please use the Sandbox before posting new challenges. \$\endgroup\$
    – cat
    Commented Dec 11, 2015 at 20:15

4 Answers 4

9
\$\begingroup\$

J, 40 39 34 bytes

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

An anonymous dyadic function, taking a point, p, as one of its arguments, and a list of points, P, as the other argument (it doesn't matter which argument is which), and returning 0 or 1, if p is outside or inside the convex hull of P, respectively. The point p, and the points in P, are taken as complex numbers.

Example

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

or...

Python 2, function, 121 103, full program, 162

Python 3, 149 bytes

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Takes input, in the same format as the original post, through STDIN, and prints a boolean value indicating whether p is in the convex hull of P


Explanation

The program tests whether the difference between the maximum and minimum (signed) angles between any point r in P, p, and a fixed arbitrary point q in P (we just use the first point in P), is less than 180°. In other words, it tests whether all the points in P are contained in an angle of 180° or less, around p. p is in the convex hull of P if and only if this condition is false.


At the cost of a few more bytes, we can use a similar method that doesn't require us to explicitly calculate angles: Note that the above condition is equivalent to saying that p is outside the convex hull of P if and only if there exists a line l through p, such that all the points in P are on the same side of l. If such a line exists, then there's also such a line that is incident to one (or more) of the points in P (we can rotate l until it touches one of the points in P.)

To (tentatively) find this line, we start by letting l be the line through p and the first point in P. We then iterate over the rest of the points in P; if one of the points is to the left of l (we assume some directionality throughout, left or right doesn't really matter,) we replace l with the line passing through p and that point, and continue. After we iterated over all of P, if (and only if) p is outside the convex hull, then all the points in P should be to the right of (or on) l. We check that using a second pass over the points in P.

Python 2, 172 bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)


Alternatively, to do the same thing in a single pass, let to-the-left-of be a realtion between any two points, q and r, in P, such that q is to the left of r if q is to the left of the line passing through p and r. Note that to-the-left-of is an order relation on P if and only if all the points in P are on the same side of some line passing through p, that is, if p is outside the convex hull of P. The procedure described above finds the minimum point in P w.r.t. this order, i.e., the "leftmost" point in P. Instead of performing two passes, we can find the maximum (i.e., the "rightmost" point), as well as the minimum, points in P w.r.t. the same order in a single pass, and verify that the minimum is to the left of the maximum, i.e., effectively, that to-the-left-of is transitive.

This would work well if p is outside the convex hull of P, in which case to-the-left-of is actually an order relation, but may break when p is inside the convex hull (for example, try to figure out what will happen if we ran this algorithm where the points in P are the vertices of a regular pentagon, running counter-clockwise, and p is its center.) To accommodate, we slightly alter the algorithm: We select a point q in P, and bisect P along the line passing through p and q (i.e., we partition P around q w.r.t. to-the-left-of.) We now have a "left part" and a "right part" of P, each contained in a halfplane, so that to-the-left-of is an order relation on each; we find the minimum of the left part, and the maximum of the right part, and compare them as described above. Of course, we don't have to physically bisect P, we can simply classify each point in P as we look for the minimum and maximum, in a single pass.

Python 2, 194 bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)
\$\endgroup\$
3
  • \$\begingroup\$ any chance you could make your solutions (at least the Python one, I have no clue if J can do that) take input from STDIN? I find it would be easier to compare solutions with a level playing field. Assuming that input is already a preformatted set of complex numbers or points is a bit of a stretch IMO. \$\endgroup\$ Commented Dec 13, 2015 at 10:24
  • \$\begingroup\$ @AlexandreHalm Added full program. \$\endgroup\$
    – Ell
    Commented Dec 13, 2015 at 16:48
  • \$\begingroup\$ You should split your solutions into one answer per language. \$\endgroup\$
    – user45941
    Commented Dec 15, 2015 at 15:12
4
\$\begingroup\$

Octave, 82 72 bytes

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

The idea is to check whether the linear program min { c'x : Ax=b, e'x=1, x >= 0 } has a solution, where e is a vector of all ones, columns of A are the coordinates of the point cloud, and b is the test point, and c is arbitrary. In other words, we try to represent b as a convex combination of columns of A.

To run the script, use octave -f script.m <input.dat

\$\endgroup\$
0
2
\$\begingroup\$

R, 207 bytes

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

The script takes its inputs from STDIN, e.g. Rscript script.R < inputFile.

It generates all triangles from the N last points (the last line, apply(combn(... ) and checks whether the first point is in the triangle using the t function.

t uses the area method to decide if U is in ABC: (writing (ABC) for the area of ABC) U is in ABC iff (ABC) == (ABU) + (ACU) + (BCU). Also, areas are calculated using the determinant formula (see here for a nice demo from Wolfram).

I suspect this solution is more prone to numerical errors than my other one, but it works on my test cases.

\$\endgroup\$
0
\$\begingroup\$

R, 282 bytes

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

The script takes its inputs from STDIN, e.g. Rscript script.R < inputFile.

It generates all triangles from the N last points (the last line, apply(combn(... ) and checks whether the first point is in the triangle using the t function.

t uses the barycentric method to decide if U is in ABC: (writing XY for the X to Y vector) since (AB,AC) is a basis for the plane (except for the degenerate cases where A,B,C are aligned), AU can be written as AU = u.AB + v.AC and U is in the triangle iff u > 0 && v > 0 && u+v < 1. See for instance here for a more detailed explanation and a nice interactive chart. NB: to save a few chars and avoid DIV0 errors, we only compute a shortcut to u and v and a modified test (min(u*k,v*k,k-u-v)>0).

The only mathematical operators used are +, -, *, min()>0.

\$\endgroup\$

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