Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Your goal is to determine whether a given 2D point X lies within the area of the triangle with given vertices A,B,C.

Write a function that takes in the coordinates of the test point X and the three triangle vertices (so that's 8 coordinates total) and returns True if the point lies inside that triangle, and False if it lies outside.

Don't worry about edge cases. If the point lies on the boundary of the triangle (edge or vertex) or the triangle is actually a line segment, your code can do whatever, including crashing. Also don't worry about numerical stability or floating-point precision.

Your code must be a named function. Code snippets will not be accepted.

Fewest characters wins.

Input:

Eight real numbers representing coordinates. The numbers will lie in the range (-1,1).

The exact input format is flexible. You could, for example, take in eight numbers, a list of eight numbers, a list of four points each given by a tuple, a 2*4 matrix, four complex numbers, two lists of the x-coordinates and y-coordinates, and so on.

The input needs to just be the numbers in some container, with no additional data. You can't use the input to do any preprocessing, nor may you require any constraints on the input, such as requiring the points be given in ascending y coordinate. Your input must allow any eight coordinates (though your code can behave arbitrarily in the edge cases mentioned earlier).

Please state your input format.

Output:

Either the corresponding Boolean True/False, the corresponding number 1/0, or the analogues in your language.

Test cases

The inputs are given a list [X,A,B,C] of four tuples, the test point first, then the three triangle vertices. I've grouped them into those whose outputs should be True and those that should be False.

True instances:

[(-0.31961, -0.12646), (0.38478, 0.37419), (-0.30613, -0.59754), (-0.85548, 0.6633)]
[(-0.87427, -0.00831), (0.78829, 0.60409), (-0.90904, -0.13856), (-0.80685, 0.48468)]
[(0.28997, -0.03668), (-0.28362, 0.42831), (0.39332, -0.07474), (-0.48694, -0.10497)]
[(-0.07783, 0.04415), (-0.34355, -0.07161), (0.59105, -0.93145), (0.29402, 0.90334)]
[(0.36107, 0.05389), (0.27103, 0.47754), (-0.00341, -0.79472), (0.82549, -0.29028)]
[(-0.01655, -0.20437), (-0.36194, -0.90281), (-0.26515, -0.4172), (0.36181, 0.51683)]
[(-0.12198, -0.45897), (-0.35128, -0.85405), (0.84566, 0.99364), (0.13767, 0.78618)]
[(-0.03847, -0.81531), (-0.18704, -0.33282), (-0.95717, -0.6337), (0.10976, -0.88374)]
[(0.07904, -0.06245), (0.95181, -0.84223), (-0.75583, -0.34406), (0.16785, 0.87519)]
[(-0.33485, 0.53875), (-0.25173, 0.51317), (-0.62441, -0.90698), (-0.47925, 0.74832)]

False instances:

[(-0.99103, 0.43842), (0.78128, -0.10985), (-0.84714, -0.20558), (-0.08925, -0.78608)]
[(0.15087, -0.56212), (-0.87374, -0.3787), (0.86403, 0.60374), (0.01392, 0.84362)]
[(0.1114, 0.66496), (-0.92633, 0.27408), (0.92439, 0.43692), (0.8298, -0.29647)]
[(0.87786, -0.8594), (-0.42283, -0.97999), (0.58659, -0.327), (-0.22656, 0.80896)]
[(0.43525, -0.8923), (0.86119, 0.78278), (-0.01348, 0.98093), (-0.56244, -0.75129)]
[(-0.73365, 0.28332), (0.63263, 0.17177), (-0.38398, -0.43497), (-0.31123, 0.73168)]
[(-0.57694, -0.87713), (-0.93622, 0.89397), (0.93117, 0.40775), (0.2323, -0.30718)]
[(0.91059, 0.75966), (0.60118, 0.73186), (0.32178, 0.88296), (-0.90087, -0.26367)]
[(0.3463, -0.89397), (0.99108, 0.13557), (0.50122, -0.8724), (0.43385, 0.00167)]
[(0.88121, 0.36469), (-0.29829, 0.21429), (0.31395, 0.2734), (0.43267, -0.78192)]
share|improve this question
    
What is your definition of a character? Ascii? Encodable in 7 bits? In a byte? Any Unicode? –  isaacg Jul 5 at 19:07
    
What do you suggest? There's already solutions that use compressed code. –  xnor Jul 5 at 19:46
    
Typically, I believe bytes are used for non-Ascii characters, because otherwise the Utf-32 advantage is insurmountable. –  isaacg Jul 6 at 19:51
    
Well, I can't go back now; any Unicode character is a character. Compress if you want. –  xnor Jul 6 at 21:55

18 Answers 18

Javascript / ECMAScript 6, 161 159 158 / 152

Javascript:

function $(t,r,i,a,n,g,l,e){b=(-g*l+a*(-n+l)+i*(g-e)+n*e)/2;c=b<0?-1:1;d=(a*l-i*e+(e-a)*t+(i-l)*r)*c;f=(i*g-a*n+(a-g)*t+(n-i)*r)*c;return d>0&&f>0&&d+f<2*b*c}

ECMAScript 6 version (thanks m.buettner, saves 6 characters)

$=(t,r,i,a,n,g,l,e)=>{b=(-g*l+a*(-n+l)+i*(g-e)+n*e)/2;c=b<0?-1:1;d=(a*l-i*e+(e-a)*t+(i-l)*r)*c;f=(i*g-a*n+(a-g)*t+(n-i)*r)*c;return d>0&&f>0&&d+f<2*b*c}

Call it as such (returns true or false):

$(pointX, pointY, v1X, v1Y, v2X, v2Y, v3X, v3Y);

Uses some fancy barycentric coordinate math based on code from this answer. An ungolfed version for your reading enjoyment follows:

function $ (pointX, pointY, v1X, v1Y, v2X, v2Y, v3X, v3Y) {
  var A =  (-v2Y * v3X + v1Y * (-v2X + v3X) + v1X * (v2Y - v3Y) + v2X * v3Y) / 2;
  var sign = A < 0 ? -1 : 1;
  var s = (v1Y * v3X - v1X * v3Y + (v3Y - v1Y) * pointX + (v1X - v3X) * pointY) * sign;
  var t = (v1X * v2Y - v1Y * v2X + (v1Y - v2Y) * pointX + (v2X - v1X) * pointY) * sign;
  return s > 0 && t > 0 && s + t < 2 * A * sign;
}
share|improve this answer
8  
+1, if only for the parameter names! –  Matt Jul 4 at 0:18
    
Why do you have to break my character-counting UserScript??? –  kitcar2000 Jul 4 at 17:21
    
@kitcar2000 what do you mean? –  Abraham Jul 4 at 17:40
    
The rules says that characters are counted, not bytes. So you can use this: xem.github.io/obfuscatweet to fit in 122 chars –  xem Jul 4 at 19:53
    
@kitcar2000 This tool counts both characters and bytes (as per UTF-8): mothereff.in/byte-counter –  Mathias Bynens Jul 5 at 4:55

Python 2.7 128 127 117 110 109 103 99 95 94 91 90

My first code-golf attempt!

Code

f=lambda x,y,t:sum(a*y+c*b+d*x<d*a+c*y+b*x for i in(0,1,2)for a,b,c,d in[t[i-1]+t[i]])%3<1

Takes as input (x,y,t) where (x,y) is the point we're checking and t is a triangle t = ((x1,y1),(x2,y2),(x3,y3)).

Explanation

I'm calculating the determinants of the matrices

| 1 x1 y1 |      | 1 x2 y2 |      | 1 x3 y3 |
| 1 x2 y2 | ,    | 1 x3 y3 | ,    | 1 x1 y1 | .
| 1 x  y  |      | 1 x  y  |      | 1 x  y  |

These determinants represent the signed distances from the sides of the triangle to the point (x,y). If they all have the same sign, then the point is on the same side of every line and is thus contained in the triangle.

In the code above, a*y+c*b+d*x-d*a-c*y-b*x is a determinant of one of these matrices.

I'm using the fact that True+True+True==3 and False+False+False==0 to determine if these determinants all have the same sign.

I make use of Python's negative list indices by using t[-1] instead of t[(i+1)%3].

Thanks Peter for the idea to use s%3<1 instead of s in(0,3) to check if s is either 0 or 3!

Sagemath Version

Not really a different solution so I'm including it in this answer, a sagemath solution using 80 characters:

f=lambda p,t,o=[1]:sum([det(Matrix([o+t[i-1],o+t[i],o+p]))<0for i in 0,1,2])%3<1

where p=[x,y], and t=[[x1,y1],[x2,y2],[x3,y3]]

share|improve this answer
1  
Could s in (0,3) be shortened to s%3<1? –  Peter Taylor Jul 4 at 8:43
    
Thanks @PeterTaylor! –  Alex L Jul 4 at 8:45
1  
The use of negative indices can be tweaked to save one more: -1,0,1 ... t[i]+t[i+1] is equivalent to 0,1,2 ... t[i-1]+t[i] –  Peter Taylor Jul 4 at 9:34
    
@PeterTaylor Absolutely right! Too bad I removed the space in in -1,0,1 before reading this. Actually your way is more readable so I'll use it anyway. –  Alex L Jul 4 at 9:37
1  
Welcome to code golf! You can get rid of the square brackets for the list comprehension inside the sum if you encase the 0,1,2 in parentheses, which case a character by replacing a space. The reason is that Python allow unbracketed comprehension to be passed in to functions, but the commas in the naked tuple 1,2,3 confuse it because it tries to parse them as separate arguments. –  xnor Jul 6 at 22:07

Mathematica, 67 bytes

f=Equal@@({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])&

The function takes two arguments, the point X and a list of points {A,B,C}, which are referred to as # and #2 respectively. That is if you call

f[X,{A,B,C}]

then you'll get # as X and #2 as {A,B,C}. (Note that there are two other anonymous functions nested inside the code - # and #2 have a different meaning within those.)

Here is an explanation of the function itself:

                                              x=#;#2            & (* Save X into a variable x, but evaluate to {A,B,C}. *)
                                    Partition[x=#;#2,2,1,{1,1}] & (* Get a cyclic list of pairs {{A,B},{B,C},{C,B}}. *)
       (                        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Define an anonymous function and apply it to each 
                                                                     of the above pairs. The two elements are referred 
                                                                     to as # and #2. *)
       (          (#-#2)        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Subtract the two points. For a pair of vertices 
                                                                     this yields a vector corresponding to the edge 
                                                                     between them. *)
        {#2,-#}&                                                  (* An anonymous function that takes two values, 
                                                                     reverses them, inverts the sign of one of them 
                                                                     and puts them into a list. *)
       ({#2,-#}&@@(#-#2)        &@@@Partition[x=#;#2,2,1,{1,1}])& (* Applied to the edge, this yields its normal. *)
       ({#2,-#}&@@(#-#2).(x-#)  &@@@Partition[x=#;#2,2,1,{1,1}])& (* Take the scalar product of that normal with a
                                                                     vector from a vertex to x. This is projection of 
                                                                     this vector onto that normal and hence the SIGNED
                                                                     distance of x from the edge. *)
       ({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])& (* Check the sign of that distance, the exact mapping 
                                                                     between (left, right) and (True, False) is 
                                                                     irrelevant, as long as it's consistent. *)
Equal@@({#2,-#}&@@(#-#2).(x-#)>0&@@@Partition[x=#;#2,2,1,{1,1}])& (* Check if all signs are equal - that is, if point X 
                                                                     lies on the same side of all edges. This is 
                                                                     equivalent to check that the point is inside the 
                                                                     triangle. *)

Note that this function will actually work for any convex n-gon as long as its vertices are given in either clockwise or counter-clockwise order.

share|improve this answer
    
Wouldn't it be more efficient to check if the product of the distances is positive than if all of the signs are equal? I don't Mathematica, but it seems like that should be easier. –  isaacg Jul 3 at 20:57
    
@isaacg There are three terms, so if they are all negative, their product is negative and if they are all positive, their product is positive. Your approach only works if the signs of two numbers are to be equal. –  Martin Büttner Jul 3 at 21:01
    
Why not use Det? –  alephalpha Jul 7 at 5:56
    
@alephalpha Well, mostly likely because I didn't think of it. :P ... I'll look into that –  Martin Büttner Jul 7 at 9:49
    
@alephalpha Hm no, I can't find a way right now to build the three required matrices in less characters. –  Martin Büttner Jul 7 at 10:02

CJam, 66 63 59 52 46 34 32 31 30 28 characters

"Ă䒟损崙㩴ァ椟饃꿾藭鑭蘁"2G#b131b:c~

After transforming the Unicode string, the following code (33 bytes) gets evaluated:

{2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T

Expects X [A B C] as input, where each point is of the form [double double]. Output is 1 or 0.

Try it online.

A big thank you goes to user23013 for saving 6 characters (13 bytes of uncompressed code)!

Test cases

$ cat triangle.cjam
"Ă䒟损崙㩴ァ椟饃꿾藭鑭蘁"2G#b131b:c~

[
  [-0.31961 -0.12646] [ [0.38478 0.37419]   [-0.30613 -0.59754] [-0.85548 0.6633]   ] T
  [-0.87427 -0.00831] [ [0.78829 0.60409]   [-0.90904 -0.13856] [-0.80685 0.48468]  ] T
  [0.28997 -0.03668]  [ [-0.28362 0.42831]  [0.39332 -0.07474]  [-0.48694 -0.10497] ] T
  [-0.07783 0.04415]  [ [-0.34355 -0.07161] [0.59105 -0.93145]  [0.29402 0.90334]   ] T
  [0.36107 0.05389]   [ [0.27103 0.47754]   [-0.00341 -0.79472] [0.82549 -0.29028]  ] T
  [-0.01655 -0.20437] [ [-0.36194 -0.90281] [-0.26515 -0.4172]  [0.36181 0.51683]   ] T
  [-0.12198 -0.45897] [ [-0.35128 -0.85405] [0.84566 0.99364]   [0.13767 0.78618]   ] T
  [-0.03847 -0.81531] [ [-0.18704 -0.33282] [-0.95717 -0.6337]  [0.10976 -0.88374]  ] T
  [0.07904 -0.06245]  [ [0.95181 -0.84223]  [-0.75583 -0.34406] [0.16785 0.87519]   ] T
  [-0.33485 0.53875]  [ [-0.25173 0.51317]  [-0.62441 -0.90698] [-0.47925 0.74832]  ] T
  [-0.99103 0.43842]  [ [0.78128 -0.10985]  [-0.84714 -0.20558] [-0.08925 -0.78608] ] T
  [0.15087 -0.56212]  [ [-0.87374 -0.3787]  [0.86403 0.60374]   [0.01392 0.84362]   ] T
  [0.1114 0.66496]    [ [-0.92633 0.27408]  [0.92439 0.43692]   [0.8298 -0.29647]   ] T
  [0.87786 -0.8594]   [ [-0.42283 -0.97999] [0.58659 -0.327]    [-0.22656 0.80896]  ] T
  [0.43525 -0.8923]   [ [0.86119 0.78278]   [-0.01348 0.98093]  [-0.56244 -0.75129] ] T
  [-0.73365 0.28332]  [ [0.63263 0.17177]   [-0.38398 -0.43497] [-0.31123 0.73168]  ] T
  [-0.57694 -0.87713] [ [-0.93622 0.89397]  [0.93117 0.40775]   [0.2323 -0.30718]   ] T
  [0.91059 0.75966]   [ [0.60118 0.73186]   [0.32178 0.88296]   [-0.90087 -0.26367] ] T
  [0.3463 -0.89397]   [ [0.99108 0.13557]   [0.50122 -0.8724]   [0.43385 0.00167]   ] T
  [0.88121 0.36469]   [ [-0.29829 0.21429]  [0.31395 0.2734]    [0.43267 -0.78192]  ] T
]p;

$ cjam triangle.cjam
[1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
share|improve this answer
    
Is that a named function? –  Martin Büttner Jul 3 at 23:02
    
@m.buettner: Sort of. The official wiki says the following: Block - a program section delimited by { and } and treated as a single unit. Similar to code blocks in C/java, except blocks are first-class objects and can be assigned to variables (thus defining functions). –  Dennis Jul 3 at 23:05
1  
@xnor 1m<@m* prepares 3 pairs of X and the next (i+1th) vertex of the triangle. @-@@- moves the current (ith) vertex to the origin (and mirrored if it was not @-\@-, but it doesn't matter). @@*@@*> calculates the z-axis of the cross product, aka determinant, and returns 1 if it is negative. :+3%! returns whether they are all the same, that is, all 3 are negative or non-negative, which means positive except for the edge cases. I think it is more challenging to read CJam than golfing. –  user23013 Jul 7 at 10:43
1  
37 bytes: {[_1m<\]z\f{f{+~@-@@-}~@@*@@*>})-!}:T. Use 2m> or Wm< for Unicode safety. –  user23013 Jul 7 at 19:31
1  
33 bytes: {2*2/\f{f{+~@-@@-}~@@*@@*>})-!}:T –  user23013 Jul 13 at 12:39

C – 156 bytes

Input are array of 3 floats in X, 3 floats in Y and separate x and y for the test point. Bonus: handles all edge cases!

int f(float*X,float*Y,float x,float y){int i,j,c=0;for(i=0,j=2;i<3;j=i++)if(((Y[i]>y)!=(Y[j]>y))&&(x<(X[j]-X[i])*(y-Y[i])/(Y[j]-Y[i])+X[i]))c=!c;return c;}

Adapted from PNPOLY.

share|improve this answer
    
i;j;c;f(float*X,float*Y,float x,float y){for(c=i=0,j=2;i<3;)c^=(Y[i]>y)-(Y[j]>y)&(x<(X[j]-X[i])*(y-Y[i])/(Y[j]-Y[i])+X‌​[j=i++]);return c;} 137 - tested in javascript –  bebe Jul 4 at 11:20
    
@bebe - That causes a syntax error. –  Derek 朕會功夫 Jul 6 at 0:00
    
That does not cause a syntax error. –  bebe Jul 6 at 15:01

Pyth 1.0.5, 57 54 51

DgYb=Z0J'bWbK;bDiHNR*-'H'K-@N1@K1~Z>iYJiJY=JK)R!%Z3

Defines the function g, which takes two inputs: the test point, and then the list of the vertices of the triangle. Outputs True and False. Note: Destroys the input, specifically b, the list of the vertices of the triangle.

Try it here. The last few characters, gvwvw call the function with a test case on the next two lines.

Based on this algorithm

Explanation:

DgYb                  Define g(Y,b):
=Z0                     Z=0
J'b                     J=b[0]              (No = is needed because j is special).
Wb                      While len(b)>0:     (While b:)
K;b                       K=b.pop()
DiHN                      Define i(H,N):    
R*-'H'K-@N1@K1              Return half of the linked equation.
~ZiYJiJY                  Z+=i(Y,J)>i(J,Y)
=JK                       J=K
)                       Wend
R!%Z3                   return not Z%3==0   (True iff Z == 0 or 3)

The CJam - Pyth war rages on!

share|improve this answer
    
This should be a named function. Is w taking STDIN input? –  xnor Jul 3 at 22:50
    
@xnor Oops, I missed that piece of the description. Will edit. –  isaacg Jul 3 at 22:57
    
@xnor Are functions that print out the answer allowed, or must they return the answer? Currently, this prints out the answer, but I could have it return for one more character. –  isaacg Jul 3 at 23:09
    
Return the answer. –  xnor Jul 3 at 23:11
    
Can you perhaps save characters by replacing the counter Z with an empty set that you accumulate with Z|=, then test its length to see if only 0's or 1 were seen? The strategy turned out longer in Python, but perhaps it's worth it using Pyth primitives. –  xnor Jul 6 at 22:11

J 64 45 (42 without assignment)

c=:*./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)

The assignment is not necessary for the thing to be a function, so unsure whether to count it or not. Taking advantage of the flexible input: I'd like to have an array of (1 + number of vertices) x (dimensionality of the space).

Hoping to score some extra points here ... : This thing works for any dimension of simplex, not just triangles in a plane, but also a 3 sided pyramid in 3d space and so on. It also works when the number of vertices of the simplex is smaller than (n+1), then it computes whether the projection of the point onto the simplex is inside or not.

It converts to barycentric coordinates, then checks for negative ones, indicating the point is outside. Do mind J uses _ for negative

NB. example in triangle
D =: 4 2 $ 1 1 0 0 3 0 0 2 NB. 4 rows , x first, then the vertices of the triangle

NB. subtract last vertex coordinates from the rest and drop reference node
n=: (}:-"1{:)

NB. preprocessed to barycentric coordinates
bar=: {. (, 1 - +/)@%. |:@}.

NB. all positive
ap =: *./@(>:&0)

insided =: ap@bar@n

inside D
1

A run on the given examples:

   true =: 0 : 0
[(-0.31961, -0.12646), (0.38478, 0.37419), (-0.30613, -0.59754), (-0.85548, 0.6633)]
[(-0.87427, -0.00831), (0.78829, 0.60409), (-0.90904, -0.13856), (-0.80685, 0.48468)]
[(0.28997, -0.03668), (-0.28362, 0.42831), (0.39332, -0.07474), (-0.48694, -0.10497)]
[(-0.07783, 0.04415), (-0.34355, -0.07161), (0.59105, -0.93145), (0.29402, 0.90334)]
[(0.36107, 0.05389), (0.27103, 0.47754), (-0.00341, -0.79472), (0.82549, -0.29028)]
[(-0.01655, -0.20437), (-0.36194, -0.90281), (-0.26515, -0.4172), (0.36181, 0.51683)]
[(-0.12198, -0.45897), (-0.35128, -0.85405), (0.84566, 0.99364), (0.13767, 0.78618)]
[(-0.03847, -0.81531), (-0.18704, -0.33282), (-0.95717, -0.6337), (0.10976, -0.88374)]
[(0.07904, -0.06245), (0.95181, -0.84223), (-0.75583, -0.34406), (0.16785, 0.87519)]
[(-0.33485, 0.53875), (-0.25173, 0.51317), (-0.62441, -0.90698), (-0.47925, 0.74832)]
)

   false =: 0 : 0
[(-0.99103, 0.43842), (0.78128, -0.10985), (-0.84714, -0.20558), (-0.08925, -0.78608)]
[(0.15087, -0.56212), (-0.87374, -0.3787), (0.86403, 0.60374), (0.01392, 0.84362)]
[(0.1114, 0.66496), (-0.92633, 0.27408), (0.92439, 0.43692), (0.8298, -0.29647)]
[(0.87786, -0.8594), (-0.42283, -0.97999), (0.58659, -0.327), (-0.22656, 0.80896)]
[(0.43525, -0.8923), (0.86119, 0.78278), (-0.01348, 0.98093), (-0.56244, -0.75129)]
[(-0.73365, 0.28332), (0.63263, 0.17177), (-0.38398, -0.43497), (-0.31123, 0.73168)]
[(-0.57694, -0.87713), (-0.93622, 0.89397), (0.93117, 0.40775), (0.2323, -0.30718)]
[(0.91059, 0.75966), (0.60118, 0.73186), (0.32178, 0.88296), (-0.90087, -0.26367)]
[(0.3463, -0.89397), (0.99108, 0.13557), (0.50122, -0.8724), (0.43385, 0.00167)]
[(0.88121, 0.36469), (-0.29829, 0.21429), (0.31395, 0.2734), (0.43267, -0.78192)]
)
   NB. replace - by _ to avoid problems
   NB. cut up per row, drop the [ ] and convert to numbers
   $dat_t =: ((4 2 $ ".)@}:@}.;._2) (true='-')} true ,: '_'
10 4 2
   $dat_f =: ((4 2 $ ".)@}:@}.;._2) (false='-')}false,: '_'
10 4 2
   NB. this results in arrays with shape 10 4 2

   NB. for each 4 x 2 array (rank 2), do c for all true instances
   c=:*./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)
   c"2 dat_t
1 1 1 1 1 1 1 1 1 1
   NB. the same for the false ones, demonstrating anonymous usage
   NB. still a function though (or verb in J parlance)
   *./@(>:&0)@({.(,(1-+/))@%.|:@}.)@(}:-"1{:)"2 dat_f
0 0 0 0 0 0 0 0 0 0
share|improve this answer
    
I asked for a named function, so the assignment characters count. Here are some points for generalizing to polygons! ······ –  xnor Jul 6 at 22:01
    
Well, actually, I don't quite generalize to polygons, but to N-dimensional simplexes, with maximum N+1 vertices. For instance a 4 vertex pyramid in 3-D space, or a 5 vertex simplex in 4-D space. The number of vertices can be lower than N+1, in which case the algorithm looks whether the orthogonal projection onto the hyperplane the simplex resides in lies inside the simplex or not (eg a 2 point simplex in 2-D will be projected on the line and checked whether this projection lies between the end points) –  jpjacobs Jul 7 at 7:34

Fortran - 232 218 195 174

Bloody awful. The function is horrendous because of the requirement that the data is passed to it and we cannot preprocess it.

logical function L(x);real::x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);t=x(7)-x(3);u=x(8)-x(4);L=ALL([p*(s-u)+q*(t-r)+r*u-t*s,p*u-q*t,q*r-p*s]>=r*u-t*s);endfunction

The decrease of 14 characters is because I forgot to golf the function name from my test runs. The further decrease is due to implicit typing and forgetting to change the function name. The next 20 characters came off due to reading in the points as a single array. The full program is

program inTriagle
   real, dimension(2) :: a,b,c,x
   do 
      print*,"Enter coordinates as x,a,b,c"
      read*,x,a,b,c
      if(all(x==0.0).and.all(a==0.0).and.all(b==0.0).and.all(c==0.0)) exit
      print*,"Is point in triangle: ",T(x,a,b,c)
   enddo
 contains!                       
   logical function L(x)
     real::x(8)
     p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3)
     s=x(6)-x(4);t=x(7)-x(3);u=x(8)-x(4)
     L=ALL([p*(s-u)+q*(t-r)+r*u-t*s,p*u-q*t,q*r-p*s]>=r*u-t*s)
   endfunction
end program inTriagle
share|improve this answer
1  
You can make this a bit shorter by relying on Fortran's implicit typing and using a single input array containing all 8 numbers: logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);o=r‌​*v-u*s;T=ALL([p*(s-v)+q*(u-r)+o,p*v-q*u,q*r-p*s]>=o);end I've tried shortening this further by using list operations, but unfortunately that didn't work out very well. –  Ventero Jul 3 at 21:47
1  
Even shorter by eliminating more common subexpressions: logical function T(x);real x(8);p=x(1)-x(3);q=x(2)-x(4);r=x(5)-x(3);s=x(6)-x(4);u=x(7)-x(3);v=x(8)-x(4);a=r‌​*v-u*s;b=p*v-q*u;d=q*r-p*s;T=ALL([a-b-d,b,d]>=a);end I hope I didn't make any mistakes in the transformations! Though it looks like your original code doesn't pass all testcases. –  Ventero Jul 3 at 21:57
    
@Ventero: I can't believe I forgot to abuse implicit typing :(. Thanks for your help! –  Kyle Kanos Jul 3 at 22:39
    
@Ventero: Also, it seems my answer depends on the orientation of the triangle. The first True example in OP gives False if I swap B and C's values while giving True for the original orientation. –  Kyle Kanos Jul 4 at 0:54
    
Ah, indeed, the problem is caused when (re-using the notation from my previous comment) a < 0, which effectively inverts the condition you have to test. Unfortunately this can't just be fixed by wrapping everything in an abs, as then the implied condition of b and d having the same sign as a gets lost. This can be fixed by using something like (again, re-using the notation and pre-defined variables from my last comment) e=a-b-d;T=ALL([a*a-b*b,a*a-d*d,a*a-e*e,a*b,a*d,a*e]>=0) - which probably can be golfed more. –  Ventero Jul 4 at 14:56

C# 218 (149?)

using P=System.Drawing.PointF;
bool F(P[]p){for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}P[]a=new P[3];Array.Copy(p,1,a,0,3);var g=new System.Drawing.Drawing2D.GraphicsPath();g.AddLines(a);return g.IsVisible(p[0]);}

Probably not as character-efficient as a mathematical method, but it's a fun use of libraries. Incidentally, also rather slow.

Also taking advantage of "Also don't worry about numerical stability or floating-point precision." - unfortunately, GraphicsPath uses ints internally, so a value in the range -1 < f < 1 can only have three possible values. Since floats only have 7 digits of precision, I just multiply by 1e7 to turn them into whole numbers. Hm, I guess it's not really losing any precision. It's also exploitable in another way: I probably could have taken advantage of ignoring precision and just given the "wrong" answer.

If I'm allowed to ignore the character cost of importing libraries, 149 (at the very least, System.Linq and System.Drawing are pretty standard on most WinForms projects, but System.Drawing.Drawing2D might be a bit of a stretch):

bool G(PointF[]p){for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}var g=new GraphicsPath();g.AddLines(p.Skip(1).ToArray());return g.IsVisible(p[0]);}

Test program (yea, it's ugly):

using System;
using System.Drawing;
using System.Drawing.Drawing2D;
using P=System.Drawing.PointF;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        Program prog = new Program();
        foreach (string test in
@"[(-0.31961, -0.12646), (0.38478, 0.37419), (-0.30613, -0.59754), (-0.85548, 0.6633)]
[(-0.87427, -0.00831), (0.78829, 0.60409), (-0.90904, -0.13856), (-0.80685, 0.48468)]
[(0.28997, -0.03668), (-0.28362, 0.42831), (0.39332, -0.07474), (-0.48694, -0.10497)]
[(-0.07783, 0.04415), (-0.34355, -0.07161), (0.59105, -0.93145), (0.29402, 0.90334)]
[(0.36107, 0.05389), (0.27103, 0.47754), (-0.00341, -0.79472), (0.82549, -0.29028)]
[(-0.01655, -0.20437), (-0.36194, -0.90281), (-0.26515, -0.4172), (0.36181, 0.51683)]
[(-0.12198, -0.45897), (-0.35128, -0.85405), (0.84566, 0.99364), (0.13767, 0.78618)]
[(-0.03847, -0.81531), (-0.18704, -0.33282), (-0.95717, -0.6337), (0.10976, -0.88374)]
[(0.07904, -0.06245), (0.95181, -0.84223), (-0.75583, -0.34406), (0.16785, 0.87519)]
[(-0.33485, 0.53875), (-0.25173, 0.51317), (-0.62441, -0.90698), (-0.47925, 0.74832)]
[(-0.99103, 0.43842), (0.78128, -0.10985), (-0.84714, -0.20558), (-0.08925, -0.78608)]
[(0.15087, -0.56212), (-0.87374, -0.3787), (0.86403, 0.60374), (0.01392, 0.84362)]
[(0.1114, 0.66496), (-0.92633, 0.27408), (0.92439, 0.43692), (0.8298, -0.29647)]
[(0.87786, -0.8594), (-0.42283, -0.97999), (0.58659, -0.327), (-0.22656, 0.80896)]
[(0.43525, -0.8923), (0.86119, 0.78278), (-0.01348, 0.98093), (-0.56244, -0.75129)]
[(-0.73365, 0.28332), (0.63263, 0.17177), (-0.38398, -0.43497), (-0.31123, 0.73168)]
[(-0.57694, -0.87713), (-0.93622, 0.89397), (0.93117, 0.40775), (0.2323, -0.30718)]
[(0.91059, 0.75966), (0.60118, 0.73186), (0.32178, 0.88296), (-0.90087, -0.26367)]
[(0.3463, -0.89397), (0.99108, 0.13557), (0.50122, -0.8724), (0.43385, 0.00167)]
[(0.88121, 0.36469), (-0.29829, 0.21429), (0.31395, 0.2734), (0.43267, -0.78192)]".Split('\n'))
        {
            string t = test.Replace("[(", "").Replace(")]", "");
            string[] points = t.Split(new string[] { "), (" }, StringSplitOptions.None);

            string[] p = points[0].Split(',');
            P[] xabc = new P[4];

            for (int i = 0; i < 4; i++)
            {
                p = points[i].Split(',');
                xabc[i] = new F(float.Parse(p[0]), float.Parse(p[1]));
            }

            Console.WriteLine(test + "=>" + prog.F(xabc));
        }

        Console.ReadKey();
    }

    bool G(PointF[]p)
    {
        for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}
        var g=new GraphicsPath();
        g.AddLines(p.Skip(1).ToArray());
        return g.IsVisible(p[0]);
    }

    bool F(P[]p)
    {
        for(int i=0;i<4;i++){p[i].X*=1e7f;p[i].Y*=1e7f;}
        var g=new System.Drawing.Drawing2D.GraphicsPath();
        g.AddLines(p.Skip(1).ToArray());
        return g.IsVisible(p[0]);
    }
}
share|improve this answer
    
Cute, getting the drawing engine to do the work. –  xnor Jul 6 at 21:58

HTML5 + JS, 13b + 146b / 141b / 114 chars

HTML:

<canvas id=C>

JS (146b):

// @params: t1x, t1y, t2x, t2y, t3x, t3y, pointx, pointy
function T(a,b,c,d,e,f,g,h){with(C.getContext("2d"))return beginPath(),moveTo(a,b),lineTo(c,d),lineTo(e,f),fill(),!!getImageData(g,h,1,1).data[3]}

or ES6 (141b):

T=(a,b,c,d,e,f,g,h)=>{with(C.getContext("2d"))return beginPath(),moveTo(a,b),lineTo(c,d),lineTo(e,f),fill(),!!getImageData(g,h,1,1).data[3]}

or ES6 unicode-obfuscated (114 chars):

eval(unescape(escape('𥀽𚁡𛁢𛁣𛁤𛁥𛁦𛁧𛁨𚐽🡻𭱩𭁨𚁃𛡧𩑴𠱯𫡴𩑸𭀨𘠲𩀢𚐩𬡥𭁵𬡮𘁢𩑧𪑮𤁡𭁨𚀩𛁭𫱶𩑔𫰨𨐬𨠩𛁬𪑮𩑔𫰨𨰬𩀩𛁬𪑮𩑔𫰨𩐬𩠩𛁦𪑬𫀨𚐬𘐡𩱥𭁉𫑡𩱥𡁡𭁡𚁧𛁨𛀱𛀱𚐮𩁡𭁡𦰳𧑽').replace(/uD./g,'')))

demo: http://jsfiddle.net/xH8mV/

Unicode obfuscation made with: http://xem.github.io/obfuscatweet/

share|improve this answer
    
It doesn't seem to yield the correct result when the point is close to the side: jsfiddle.net/L2B2A I believe this is because all inputs are between (-1,1), and your code is only testing the 4 pixels around the origin. –  Derek 朕會功夫 Jul 6 at 0:48
    
that's right, to fit the examples, I should change the origin and the scale of my canvas to handle triangles inside [-1,1]. But why are those triangles so small anyways? –  xem Jul 6 at 6:56
    
the problem says that all x y are between -1 and 1. Don't really know why, but I believe you can just multiply every input by 1e7 (to maintain precision) can get the correct result :D –  Derek 朕會功夫 Jul 6 at 16:21
    
A graphical solution, very clever! –  xnor Jul 6 at 21:57

Haskell — 233 127

Using cross products as described here:

h(a,b)(p,q)(r,s)(t,u)=z a b p q r s==z a b r s t u&&z a b r s t u==z a b t u p q where z j k l m n o =(o-m)*(j-l)+(l-n)*(k-m)>0

Previous solution implemented using barycentric coordinates and the formulae described in this Stack Exchange answer:

g(p,q)(r,s)(t,u)(v,w)=
 let (j,k)=(p+(-r),q+(-s))
     (l,m)=(t+(-r),u+(-s))
     (n,o)=(v+(-r),w+(-s))
     d=l*o-n*m
     a=(j*(m-o)+k*(n-l)+l*o-n*m)/d
     b=(j*o-k*n)/d
     c=(k*l-j*m)/d
 in (0<=a&&a<1)&&(0<=b&&b<1)&&(0<=c&&c<1)

Both functions g and h take four pairs, the first of which is the point to be tested for inclusion and the rest being the coordinates of the vertices of the triangle.

To test with the sample input:

let trueTestCases =
  [((-0.31961, -0.12646), (0.38478, 0.37419), (-0.30613, -0.59754), (-0.85548, 0.6633)),
   ((-0.87427, -0.00831), (0.78829, 0.60409), (-0.90904, -0.13856), (-0.80685, 0.48468)),
   ((0.28997, -0.03668), (-0.28362, 0.42831), (0.39332, -0.07474), (-0.48694, -0.10497)),
   ((-0.07783, 0.04415), (-0.34355, -0.07161), (0.59105, -0.93145), (0.29402, 0.90334)),
   ((0.36107, 0.05389), (0.27103, 0.47754), (-0.00341, -0.79472), (0.82549, -0.29028)),
   ((-0.01655, -0.20437), (-0.36194, -0.90281), (-0.26515, -0.4172), (0.36181, 0.51683)),
   ((-0.12198, -0.45897), (-0.35128, -0.85405), (0.84566, 0.99364), (0.13767, 0.78618)),
   ((-0.03847, -0.81531), (-0.18704, -0.33282), (-0.95717, -0.6337), (0.10976, -0.88374)),
   ((0.07904, -0.06245), (0.95181, -0.84223), (-0.75583, -0.34406), (0.16785, 0.87519)),
   ((-0.33485, 0.53875), (-0.25173, 0.51317), (-0.62441, -0.90698), (-0.47925, 0.74832))]

let falseTestCases =
  [((-0.99103, 0.43842), (0.78128, -0.10985), (-0.84714, -0.20558), (-0.08925, -0.78608)),
   ((0.15087, -0.56212), (-0.87374, -0.3787), (0.86403, 0.60374), (0.01392, 0.84362)),
   ((0.1114, 0.66496), (-0.92633, 0.27408), (0.92439, 0.43692), (0.8298, -0.29647)),
   ((0.87786, -0.8594), (-0.42283, -0.97999), (0.58659, -0.327), (-0.22656, 0.80896)),
   ((0.43525, -0.8923), (0.86119, 0.78278), (-0.01348, 0.98093), (-0.56244, -0.75129)),
   ((-0.73365, 0.28332), (0.63263, 0.17177), (-0.38398, -0.43497), (-0.31123, 0.73168)),
   ((-0.57694, -0.87713), (-0.93622, 0.89397), (0.93117, 0.40775), (0.2323, -0.30718)),
   ((0.91059, 0.75966), (0.60118, 0.73186), (0.32178, 0.88296), (-0.90087, -0.26367)),
   ((0.3463, -0.89397), (0.99108, 0.13557), (0.50122, -0.8724), (0.43385, 0.00167)),
   ((0.88121, 0.36469), (-0.29829, 0.21429), (0.31395, 0.2734), (0.43267, -0.78192))]

type Point = (Double, Double)

test :: [(Point, Point, Point, Point)] -> [Bool]
test testCases =
  map (\((px,py),(ax,ay),(bx,by),(cx,cy)) -> h (px,py) (ax,ay) (bx,by) (cx,cy)) testCases

test trueTestCases --> [True,True,True,True,True,True,True,True,True,True]
test falseTestCases --> [False,False,False,False,False,False,False,False,False,False]

Ungolfed solutions:

type Point = (Double, Double)

-- using cross products

triangulate' (a, b) (p, q) (r, s) (t, u) =
  (side a b p q r s == side a b r s t u) && (side a b r s t u == side a b t u p q)
  where side j k l m n o = (o - m) * (j - l) + (-n + l) * (k - m) >= 0

-- using barycentric coordinates

triangulate :: (Point, Point, Point, Point) -> Bool
triangulate ((px, py), (ax, ay), (bx, by), (cx, cy)) = 
  let (p'x, p'y) = (px + (-ax), py + (-ay))
      (b'x, b'y) = (bx + (-ax), by + (-ay))
      (c'x, c'y) = (cx + (-ax), cy + (-ay))
      d = b'x * c'y - c'x * b'y
      a = (p'x * (b'y - c'y) + p'y * (c'x - b'x) + b'x * c'y - c'x * b'y) / d
      b = (p'x * c'y - p'y * c'x) / d
      c = (p'y * b'x - p'x * b'y) / d
  in
      (0 <= a && a < 1) && (0 <= b && b < 1) && (0 <= c && c < 1)
share|improve this answer

C 414 (was 465)

Golfed

#define D double 
int F(D ax,D ay,D bx,D by,D cx,D cy,D px,D py){int y=0;double J,K;D m=(ax-bx<0.001)?(by-ay)/(ax-bx):1000;D b=m*ax+ay;J=m*cx-cy+b;K=m*px-py+b;if(J*K>=0)y=1;return y;}D T[8],k;int i,n;void G(){while(i<8){scanf("%lf",&k);T[i++]=k;}n+=F(T[2],T[3],T[4],T[5],T[6],T[7],T[0],T[1]);n+=F(T[4],T[5],T[6],T[7],T[2],T[3],T[0],T[1]);n+=F(T[2],T[3],T[6],T[7],T[4],T[5],T[0],T[1]);printf(n==3?"True":"False");}

Original function declaration added for explanation

/**
* determine if points C & P are on same side of line AB
* return 1 if true, 0 otherwise
*/
int PointsSameSide(D ax,D ay,D bx,D by,D cx, D cy, D px, D py);

Rewritten as a named function: input via stdin one each line or all in one line space-separated.

#define D double
int F(D ax,D ay,D bx,D by,D cx, D cy, D px, D py)
{
int y=0;
double J,K;
D m = (ax-bx<0.001)?(by-ay)/(ax-bx):1000;
D b = m*ax+ay;
J=m*cx-cy+b;
K=m*px-py+b;
if(J*K>=0)y=1;
return y;
}
double T[8],k;
int i,n;
void G()
{
while(i<8){scanf("%lf",&k);T[i++]=k;}
n+=F(T[2],T[3],T[4],T[5],T[6],T[7],T[0],T[1]);
n+=F(T[4],T[5],T[6],T[7],T[2],T[3],T[0],T[1]);
n+=F(T[2],T[3],T[6],T[7],T[4],T[5],T[0],T[1]);
printf(n==3?"True":"False");
}
share|improve this answer
2  
You could save some bytes by getting rid of newlines and unnecessary spaces. Also, you have double redefined as D but you still use double in the code. –  gronostaj Jul 3 at 22:18

MATLAB: 9!

Not a whole lot of me to write here

inpolygon

Can be called like so:

inpolygon(2/3, 2/3, [0 1 1], [0 0 1])

Output is assigned to a variable named ans


If I actually had to write a function, it may be something like so, could probably be optimized:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)
share|improve this answer
2  
can be shorter using a function handle: f=@(a,b,c,d)inpolygon(a,b,c,d) –  jpjacobs Jul 4 at 12:43

JavaScript 125/198

If points are provided in 8 arguments:

function d(x,y,a,b,c,d,e,f){function z(a,b,c,d){return(y-b)*(c-a)-(x-a)*(d-b)>0}return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}

If points are provided in a 2-dimensional array:

function c(s){return (z(s[1][0],s[1][1],s[2][0],s[2][1])+z(s[2][0],s[2][1],s[3][0],s[3][1])+z(s[3][0],s[3][1],s[1][0],s[1][1]))%3<1;function z(a,b,c,d){return (s[0][1]-b)*(c-a)-(s[0][0]-a)*(d-b)>0}}

This code doesn't use any of those fancy vector math. Instead, it only uses a simple algebra trick to determine if the point is inside the triangle or not. The formula:

(y-b)(c-a) - (x-a)(d-b)

which tells the point is on which side of a line, is derived from rearranging the definition of slope:

            m = (y2-y1)/(x2-x1)
      (y2-y1) = m(x2-x1)
       (y-y1) = m(x-x1)     ,substituting point we are testing (x,y) to be the 2nd point
       (y-y1) = (x-x1)(y2-y1)/(x2-x1)  ,substitute back the original definition of m
(y-y1)(x2-x1) = (x-x1)(y2-y1)    <-- left side will be greater than the right side, if
                                     the point is on the left; otherwise, it's on the right
            0 = (y-b)(c-a)-(x-a)(d-b) ,where (a,b)=(x1,y1), (c,d)=(x2,y2)

If we test all 3 sides, all 3 should yield some numbers with the same sign only when the point is inside the triangle since we are testing it around the triangle. If the point is on a side then one of the test should return 0.

jsFiddle test code: http://jsfiddle.net/DerekL/zEzZU/

var l = [[-0.31961, -0.12646, 0.38478, 0.37419, -0.30613, -0.59754, -0.85548, 0.6633],[-0.87427, -0.00831, 0.78829, 0.60409, -0.90904, -0.13856, -0.80685, 0.48468],[0.28997, -0.03668, -0.28362, 0.42831, 0.39332, -0.07474, -0.48694, -0.10497],[-0.07783, 0.04415, -0.34355, -0.07161, 0.59105, -0.93145, 0.29402, 0.90334],[0.36107, 0.05389, 0.27103, 0.47754, -0.00341, -0.79472, 0.82549, -0.29028],[-0.01655, -0.20437, -0.36194, -0.90281, -0.26515, -0.4172, 0.36181, 0.51683],[-0.12198, -0.45897, -0.35128, -0.85405, 0.84566, 0.99364, 0.13767, 0.78618],[-0.03847, -0.81531, -0.18704, -0.33282, -0.95717, -0.6337, 0.10976, -0.88374],[0.07904, -0.06245, 0.95181, -0.84223, -0.75583, -0.34406, 0.16785, 0.87519],[-0.33485, 0.53875, -0.25173, 0.51317, -0.62441, -0.90698, -0.47925, 0.74832],
         [-0.99103, 0.43842, 0.78128, -0.10985, -0.84714, -0.20558, -0.08925, -0.78608],[0.15087, -0.56212, -0.87374, -0.3787, 0.86403, 0.60374, 0.01392, 0.84362],[0.1114, 0.66496, -0.92633, 0.27408, 0.92439, 0.43692, 0.8298, -0.29647],[0.87786, -0.8594, -0.42283, -0.97999, 0.58659, -0.327, -0.22656, 0.80896],[0.43525, -0.8923, 0.86119, 0.78278, -0.01348, 0.98093, -0.56244, -0.75129],[-0.73365, 0.28332, 0.63263, 0.17177, -0.38398, -0.43497, -0.31123, 0.73168],[-0.57694, -0.87713, -0.93622, 0.89397, 0.93117, 0.40775, 0.2323, -0.30718],[0.91059, 0.75966, 0.60118, 0.73186, 0.32178, 0.88296, -0.90087, -0.26367],[0.3463, -0.89397, 0.99108, 0.13557, 0.50122, -0.8724, 0.43385, 0.00167],[0.88121, 0.36469, -0.29829, 0.21429, 0.31395, 0.2734, 0.43267, -0.78192]];

function d(x,y,a,b,c,d,e,f){function z(a,b,c,d){return(y-b)*(c-a)-(x-a)*(d-b)>0}return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}

for(var i = 0; i < l.length; i++){
    console.log(d.apply(undefined,l[i]));    //10 true, 10 false
}

97 characters (not counting spaces or tabs) count if converted into CoffeeScript:

d=(x,y,a,b,c,d,e,f)->
    z=(a,b,c,d)->
        (y-b)*(c-a)-(x-a)*(d-b)>0
    (z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1

115 characters if converted into ES6:

d=(x,y,a,b,c,d,e,f)=>{z=(a,b,c,d)=>{return (y-b)*(c-a)-(x-a)*(d-b)>0};return(z(a,b,c,d)+z(c,d,e,f)+z(e,f,a,b))%3<1}
share|improve this answer
    
That is the "fancy vector math" I'm using :D (not the fancy barycentric coordinate approach some others took, though). Like the top-voted answer, you can save a few bytes by using ES6 and defining the functions like d=(x,y,...)=>{...}. In your case, you can save even more by using CoffeeScript, which doesn't need return: pastebin.com/RVFk1D5k ... and in any case you can save one byte by using <1 instead of ==0. –  Martin Büttner Jul 5 at 9:25
    
@m.buettner :o I thought the equation I used have nothing to do with vectors (derived from simple algebra) but apparently they both yield the same equation. Math is wonderful. –  Derek 朕會功夫 Jul 5 at 15:27

Python (65)

People seem to be done submitting, so I'll post my own solution to my question.

f=lambda X,L:sum(((L[i-1]-X)/(L[i]-X)).imag>0for i in(0,1,2))%3<1

X is the complex number representing the test points, and L is a list of three points, each a complex number.

First, I'll explain a less golfed version of the code;

def f(X,A,B,C):A-=X;B-=X;C-=X;return((A/B).imag>0)==((B/C).imag>0)==((C/A).imag>0)

We shift the points A,B,C,X so that X is at the origin, taking advantage of Python's built-in complex arithmetic. We need to check if the origin is contained in the convex hull of A,B,C. This is equivalent to the origin always lying on the same side (left or right) of the line segments AB, BC, and AC.

A segment AB has the origin on the left if one travel counterclockwise less than 180 degrees to get from A to B, and on the right otherwise. If we consider the angles a, b, and c corresponding to these points, this means b-a < 180 degrees (taken angles in the range 0 to 360 degrees). As complex numbers, angle(B/A)=angle(B)/angle(A). Also, angle(x) < 180 degrees exactly for point in he upper half-plane, which we check via imag(x)>0.

So whether the origin lies to the left of AB is expressed as (A/B).imag>0. Checking whether these are all equal for each cyclic pair in A,B,C tells us whether triangle ABC contains the origin.

Now, let's return to the fully golfed code

f=lambda X,L:sum(((L[i-1]-X)/(L[i]-X)).imag>0for i in(0,1,2))%3<1

We generate each cyclic pair in (A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X), taking advantage of negative Python list indices wrapping around (L[-1] = L[2]). To check that the Bools are all True (1) or all False (0), we add them and check divisibility by 3, as many solutions did.

share|improve this answer

JavaScript (ES6) 120

C=(p,q,i,j,k,l,m,n,
 z=j*(m-k)+i*(l-n)+k*n-l*m,
 s=(j*m-i*n+(n-j)*p+(i-m)*q)/z,
 t=(i*l-j*k+(j-l)*p+(k-i)*q)/z
)=>s>0&t>0&s+t<1

Directly copied from my answer to This other question

Test In FireFox/FireBug console

Output all 1s

;[
C(-0.31961, -0.12646, 0.38478, 0.37419, -0.30613, -0.59754, -0.85548, 0.6633),
C(-0.87427, -0.00831, 0.78829, 0.60409, -0.90904, -0.13856, -0.80685, 0.48468),
C(0.28997, -0.03668, -0.28362, 0.42831, 0.39332, -0.07474, -0.48694, -0.10497),
C(-0.07783, 0.04415, -0.34355, -0.07161, 0.59105, -0.93145, 0.29402, 0.90334),
C(0.36107, 0.05389, 0.27103, 0.47754, -0.00341, -0.79472, 0.82549, -0.29028),
C(-0.01655, -0.20437, -0.36194, -0.90281, -0.26515, -0.4172, 0.36181, 0.51683),
C(-0.12198, -0.45897, -0.35128, -0.85405, 0.84566, 0.99364, 0.13767, 0.78618),
C(-0.03847, -0.81531, -0.18704, -0.33282, -0.95717, -0.6337, 0.10976, -0.88374),
C(0.07904, -0.06245, 0.95181, -0.84223, -0.75583, -0.34406, 0.16785, 0.87519),
C(-0.33485, 0.53875, -0.25173, 0.51317, -0.62441, -0.90698, -0.47925, 0.74832)
]

Output all 0s

;[
C(-0.99103, 0.43842,0.78128, -0.10985,-0.84714, -0.20558,-0.08925, -0.78608),
C(0.15087, -0.56212,-0.87374, -0.3787,0.86403, 0.60374,0.01392, 0.84362),
C(0.1114, 0.66496,-0.92633, 0.27408,0.92439, 0.43692,0.8298, -0.29647),
C(0.87786, -0.8594,-0.42283, -0.97999,0.58659, -0.327,-0.22656, 0.80896),
C(0.43525, -0.8923,0.86119, 0.78278,-0.01348, 0.98093,-0.56244, -0.75129),
C(-0.73365, 0.28332,0.63263, 0.17177,-0.38398, -0.43497,-0.31123, 0.73168),
C(-0.57694, -0.87713,-0.93622, 0.89397,0.93117, 0.40775,0.2323, -0.30718),
C(0.91059, 0.75966,0.60118, 0.73186,0.32178, 0.88296,-0.90087, -0.26367),
C(0.3463, -0.89397,0.99108, 0.13557,0.50122, -0.8724,0.43385, 0.00167),
C(0.88121, 0.36469,-0.29829, 0.21429,0.31395, 0.2734,0.43267, -0.78192)
]
share|improve this answer

Java, 149 characters

g=Math.atan2(100*(d-y),(a-x));h=Math.atan2(100*(e-y),(b-x));i=Math.atan2(100*(f-y),(c-x));k=Math.round(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g))==6;

Horrible considering I have to write "Math." every time. This is the actual program:

package mathPackage;
public class InTriangle {
public static void main(String[] args) {
    boolean k;
    double a=-1,b=0,c=1,d=0,e=1,f=0,x=0,y=0.4;
    double g,h,i;
    g=Math.atan2(100*(d-y),(a-x));
    h=Math.atan2(100*(e-y),(b-x));
    i=Math.atan2(100*(f-y),(c-x));
    k=Math.round(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g))==6;
    System.out.println(k);
    System.out.println(g);
    System.out.println(h);
    System.out.println(i);
    System.out.print(Math.abs(g-h)+Math.abs(h-i)+Math.abs(i-g));
}
}

where a is the x of point a,b is the x of point b, c for x of c, d is y of a, e is y of b, f is the y of c, and x and y are the x and y of the point. The boolean k determines whether it is true or not.

share|improve this answer
    
What are the 100* for? –  xnor Jul 6 at 21:56

R, 23

Inspired by MATLAB,

SDMTools::pnt.in.poly()

called like SDMTools::pnt.in.poly(point,triangle) where point is a length-2 vector and triangle is a 3x2 matrix of vertices. SDMTools is available on CRAN.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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