Ваша цель - определить, находится ли данная 2D точка X в области треугольника с заданными вершинами A, B, C.

Напишите функцию, которая принимает координаты контрольной точки X и трех вершин треугольника (итого всего 8 координат) и возвращает True, если точка находится внутри этого треугольника, и False, если она находится снаружи.

Не беспокойтесь о крайних случаях. Если точка лежит на границе треугольника (ребра или вершины) или треугольник на самом деле является отрезком линии, ваш код может делать все, что угодно, включая сбой. Также не беспокойтесь о числовой стабильности или точности с плавающей точкой.

Ваш код должен быть именованной функцией. Фрагменты кода не принимаются.

Побеждает несколько персонажей.

Входные данные:

Восемь действительных чисел, представляющих координаты. Числа будут лежать в диапазоне (-1,1).

Точный формат ввода является гибким. Вы можете, например, взять восемь чисел, список из восьми чисел, список из четырех точек, каждой из которых присваивается кортеж, матрицу 2 * 4, четыре комплексных числа, два списка из x-координат и y-координат, и так далее.

Входные данные должны быть просто числами в некотором контейнере, без каких-либо дополнительных данных. Вы не можете использовать входные данные для выполнения какой-либо предварительной обработки, а также не можете требовать каких-либо ограничений на ввод, например, требовать, чтобы точки задавались в восходящей координате y. Ваш ввод должен позволять любые восемь координат (хотя ваш код может вести себя произвольно в случаях краев, упомянутых ранее).

Пожалуйста, укажите ваш формат ввода.

Выход:

Либо соответствующий логический True/ False, соответствующий номер 1/0 , либо аналоги на вашем языке.

Контрольные примеры

Входные данные получают список [X,A,B,C]из четырех кортежей, сначала контрольную точку, а затем три вершины треугольника. Я сгруппировал их в тех, чьи результаты должны быть Trueи те, которые должны бытьFalse .

True экземпляры:

[(-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.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)]

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 (спасибо m.buettner, сохраняет 6 символов)

$=(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}

Назовите это так (возврат trueили false):

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

Использует некоторую причудливую барицентрическую координатную математику на основе кода из этого ответа . Ниже приведена версия для вашего чтения:

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;
}

Python 2,7 128 127 117 110 109 103 99 95 94 91 90

Моя первая попытка игры в гольф!

Код

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

Принимает в качестве входных данных (x, y, t) где (x, y) - точка, которую мы проверяем, а t - треугольник t = ((x1, y1), (x2, y2), (x3, y3)).

объяснение

Я рассчитываю определители матриц

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

Эти детерминанты представляют подписанные расстояния от сторон треугольника до точки (x, y). Если все они имеют одинаковый знак, то точка находится на одной стороне каждой линии и, следовательно, содержится в треугольнике.

В приведенном выше коде, a*y+c*b+d*x-d*a-c*y-b*xявляется определителем одной из этих матриц.

Я использую тот факт, что True+True+True==3и False+False+False==0для определения, все ли эти детерминанты имеют один и тот же знак.

Я использую отрицательные индексы списка Python, используя t[-1]вместоt[(i+1)%3] .

Спасибо Питеру за идею использовать s%3<1вместо того, s in(0,3)чтобы проверить, является ли s 0 или 3!

Версия Sagemath

Не совсем другое решение, поэтому я включаю его в этот ответ, решение Sagemath с использованием 80 символов:

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

где p=[x,y]иt=[[x1,y1],[x2,y2],[x3,y3]]

Mathematica, 67 байт

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

Функция принимает два аргумента: точку Xи список точек {A,B,C}, которые называются #и #2соответственно. Это если вы позвоните

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

тогда вы получите #как Xи #2как {A,B,C}. (Обратите внимание, что в коде есть две другие анонимные функции -# и #2имеют другое значение в них.)

Вот объяснение самой функции:

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

Обратите внимание, что эта функция будет фактически работать для любого выпуклого n-угольника, если его вершины заданы либо по часовой стрелке, либо против часовой стрелки.

CJam, 66 63 59 52 46 34 32 31 30 28 символов

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

После преобразования строки Unicode вычисляется следующий код ( 33 байта ):

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

Ожидается в X [A B C]качестве входных данных, где каждая точка имеет форму [double double]. Выход 1 или 0.

Попробуйте онлайн.

Большое спасибо пользователю 23233 за сохранение 6 символов (13 байт несжатого кода)!

Контрольные примеры

$ 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]

C - 156 байт

Входные данные представляют собой массив из 3 чисел с плавающей запятой в X, 3 поплавков в Y и отдельных x и y для контрольной точки. Бонус: обрабатывает все крайние случаи!

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;}

Адаптировано из PNPOLY.

Pyth 1.0.5 , 57 54 51

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

Определяет функцию g, которая принимает два входа: контрольную точку, а затем список вершин треугольника. Выходы Trueи False. Примечание. Уничтожает ввод, в частности, b, список вершин треугольника.

Попробуй это здесь . Последние несколько символов, gvwvwвызовите функцию с контрольным примером на следующих двух строках.

На основе этого алгоритма

Объяснение:

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)

Война CJam - Pyth продолжается!

J 64 45 (42 без присвоения)

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

Присвоение не обязательно для того, чтобы вещь была функцией, поэтому не знаете, считать это или нет. Воспользовавшись гибким вводом: я хотел бы иметь массив (1 + количество вершин) x (размерность пространства).

Надеясь набрать здесь несколько дополнительных очков ...: Это работает для любого измерения симплекса, не только для треугольников на плоскости, но также для 3-сторонней пирамиды в трехмерном пространстве и так далее. Он также работает, когда число вершин симплекса меньше (n + 1), тогда он вычисляет, находится ли проекция точки на симплекс внутри или нет.

Он преобразуется в барицентрические координаты , затем проверяет наличие отрицательных координат , указывая, что точка находится снаружи. Не возражаете, J использует _ для отрицательного

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

Прогон на приведенных примерах:

   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

HTML5 + JS, 13b + 146b / 141b / 114 символов

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]}

или 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]}

или ES6, зашифрованный в Unicode (114 символов):

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

демо: http://jsfiddle.net/xH8mV/

Обфускация Юникода сделана с помощью: http://xem.github.io/obfuscatweet/

Питон (65)

Люди, кажется, закончили отправку, поэтому я опубликую свое собственное решение моего вопроса.

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

Xэто комплексное число, представляющее контрольные точки, и Lпредставляет собой список из трех точек, каждая из которых представляет собой комплексное число.

Сначала я объясню менее понятную версию кода;

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)

Мы смещаем точки A,B,C,Xтак, чтобы они Xнаходились в начале координат, используя преимущества встроенной сложной арифметики Python. Нам нужно проверить, содержится ли источник в выпуклой оболочке A,B,C. Это равносильно тому, что начало координат всегда лежит на одной стороне (слева или справа) отрезков AB, BC и AC.

Сегмент ABимеет начало слева, если он движется против часовой стрелки менее чем на 180 градусов, чтобы добраться от А до В, и справа в противном случае. Если рассматривать углы a, bи cсоответствующие этим точкам, это означает b-a < 180 degrees(взятые углы в диапазоне от 0 до 360 градусов). Как комплексные числа angle(B/A)=angle(B)/angle(A). Кроме того, angle(x) < 180 degreesименно для точки в верхней полуплоскости, которую мы проверяем черезimag(x)>0 .

То, лежит ли происхождение слева от AB, выражается как (A/B).imag>0. Проверка, все ли они равны для каждой циклической пары, A,B,Cговорит нам, ABCсодержит ли треугольник начало координат.

Теперь вернемся к полному коду игры

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

Мы генерируем каждую циклическую пару (A-X,B-X,C-X)=(L[0]-X,L[1]-X,L[2]-X), используя отрицательные индексы списка Python, заключающиеся в ( L[-1]= L[2]). Чтобы проверить, что Bools - это все True( 1) или все False( 0), мы добавляем их и проверяем делимость на 3, как это делали многие решения.

Фортран - 232 218 195 174

Чертовски ужасно. Эта функция ужасна из-за требования, что данные передаются ей, и мы не можем предварительно обработать ее.

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

Уменьшение на 14 символов связано с тем, что я забыл сыграть название функции в моих тестовых прогонах. Дальнейшее уменьшение связано с неявной типизацией и забывчивостью менять имя функции. Следующие 20 символов исчезли из-за чтения в точках в виде одного массива. Полная программа

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

МАТЛАБ: 9!

Не много мне писать здесь

inpolygon

Можно назвать так:

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

Выход назначен переменной с именем ans

Если бы я действительно должен был написать функцию, это может быть что-то вроде этого, возможно, может быть оптимизировано:

function y=f(a,b,c,d)
inpolygon(a,b,c,d)

К # 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]);}

Вероятно, не так эффективно, как математический метод, но это забавное использование библиотек. Кстати, тоже довольно медленно.

Также воспользоваться преимуществом «Также не беспокойтесь о числовой стабильности или точности с плавающей точкой». - к несчастью,GraphicsPath использует ints внутри, поэтому значение в диапазоне -1 <f <1 может иметь только три возможных значения. Поскольку значения с плавающей точкой имеют только 7 цифр, я просто умножаю их на 1e7, чтобы превратить их в целые числа. Хм, я думаю, это не совсем потеряло точность. Это также можно использовать по-другому: я, вероятно, мог бы воспользоваться игнорированием точности и просто дать «неправильный» ответ.

Если мне позволено игнорировать стоимость символьной импортирующих библиотек, 149 (по крайней мере, System.Linqи System.Drawingдовольно стандартные для большинства WinForms проектов, но System.Drawing.Drawing2Dможет быть немного натянуто):

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]);}

Тестовая программа (да, это некрасиво):

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]);
    }
}

Хаскелл - 233 127

Использование перекрестных продуктов, как описано здесь :

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

Предыдущее решение, реализованное с использованием барицентрических координат и формул, описанных в ответе на Stack Exchange :

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)

Обе функции gиh принимают четыре пары, первая из которых - это точка, которую нужно проверить на включение, а остальные - координаты вершин треугольника.

Чтобы проверить с вводом образца:

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]

Нежелательные решения:

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)

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

Непосредственно скопировано с моего ответа на этот другой вопрос

Тест в консоли FireFox / FireBug

Вывести все 1с

;[
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)
]

Вывести все 0

;[
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)
]

SmileBASIC, 111 100 знаков

DEF T X,Y,A,B,C,D,E,F
Q=9e5GCLS
GTRI(A-X)*Q,Q*(B-Y),Q*(C-X),Q*(D-Y),Q*(E-X),Q*(F-Y)?!!GSPOIT(0,0)END

Рисует треугольник и проверяет цвет пикселя в точке. Треугольник увеличен до 99999x и смещен таким образом, чтобы проверяемая точка находилась в точке (0,0) перед рисованием, чтобы минимизировать потерю точности.

Intel 8087 FPU в сборе, 222 220 байт

Для расчета используется только аппаратное обеспечение 8087 FPU. Вот несобранная (в данном случае также не разграбленная) версия в виде MACRO (сэкономит вам 220 шестнадцатеричных байтовых кодов):

; calculate the area of of a triangle ABC using determinate
; input: coordinates (float), Ax,Ay,Bx,By,Cx,Cy
; output: area in ST
TAREA   MACRO   A1,A2,B1,B2,C1,C2
    FLD  A1
    FLD  B2
    FLD  C2
    FSUB        ; ST = By - Cy
    FMUL        ; ST = Ax * ( By - Cy )
    FLD  B1 
    FLD  C2
    FLD  A2
    FSUB        ; ST = Cy - Ay
    FMUL        ; ST = Bx * ( Cy - Ay )
    FLD  C1
    FLD  A2
    FLD  B2
    FSUB        ; Ay - By
    FMUL        ; Cx * ( Ay - By )
    FADD        ; Cx * ( Ay - By ) + Bx * ( Cy - Ay )
    FADD        ; Cx * ( Ay - By ) + Bx * ( Cy - Ay ) + Ax * ( By - Cy )
    FLD1        ; make a value of 2
    FADD ST,ST  ; ST = 2
    FDIV        ; divide by 2
    FABS        ; take abs value
        ENDM

; determine if point X is in triangle ABC
; input: points X, A, B, C
; output: ZF=1 if X in triangle, ZF=0 if X not in triangle
TXINABC     MACRO X1,X2,A1,A2,B1,B2,C1,C2

    TAREA  A1,A2,B1,B2,C1,C2    ; ST(3) = area of triangle ABC
    TAREA  X1,X2,B1,B2,C1,C2    ; ST(2) = area of triangle XBC
    TAREA  A1,A2,X1,X2,C1,C2    ; ST(1) = area of triangle AXC
    TAREA  A1,A2,B1,B2,X1,X2    ; ST(0) = area of triangle ABX

    FADD        ; add areas of triangles with point
    FADD        ; ST = ST + ST(1) + ST(2)
    FCOMPP      ; compare ST to ST(1) and pop results
    FWAIT       ; sync CPU/FPU
    FSTSW R     ; store result flags to R
    MOV  AX, R  ; move result to AX
    SAHF        ; store result into CPU flags for conditional check
        ENDM

объяснение

Использует определитель для вычисления площади треугольника ABC, а затем треугольник, образованный точкой X и двумя другими точками треугольника ABC. Если площадь треугольника ABC равна сумме площадей треугольников XBC + AXC + ABX, то точка находится внутри треугольника. Результат возвращается как ZF.

Что в этом хорошего

Все математические операции и операции с плавающей запятой выполняются аппаратно с 80-битной расширенной точностью. Окончательное сравнение с плавающей запятой также выполняется аппаратно, поэтому будет очень точным.

При этом также используются все восемь регистров стека 8087 одновременно.

Что не так хорошо в этом

Поскольку точки треугольника должны быть подключены обратно в формулы несколько раз во время вычисления, необходимо, чтобы каждая переменная в памяти загружалась в регистры стека FPU по одному в правильном порядке. Хотя это может быть довольно легко смоделировано как функция как MACRO, это означает, что код расширяется каждый раз при сборке, создавая избыточный код. 41 байт был сохранен путем перемещения некоторых повторяющихся сегментов кода в PROC. Однако это делает код менее читабельным, поэтому приведенный выше листинг не содержит его (поэтому он помечен как «ungolfed»).

тесты

Вот тестовая программа, использующая IBM DOS, показывающая вывод:

TTEST   MACRO T
        LOCAL IS_IN_TRI

    TXINABC T,T+4*1,T+4*2,T+4*3,T+4*4,T+4*5,T+4*6,T+4*7
    MOV  DX, OFFSET TEQ     ; load true string by default 
    JZ   IS_IN_TRI          ; if ZF=1, it is in triangle, skip to display
    MOV  DX, OFFSET FEQ     ; otherwise ZF=0 means not in triangle, so load false string
IS_IN_TRI:
    MOV  AH, 9              ; DOS write string function
    INT  21H 
        ENDM

START:
    FINIT                   ; reset 8087

    TTEST   T0              ; true tests
    TTEST   T1
    TTEST   T2
    TTEST   T3
    TTEST   T4
    TTEST   T5
    TTEST   T6
    TTEST   T7
    TTEST   T8
    TTEST   T9

    TTEST   F0              ; false tests
    TTEST   F1
    TTEST   F2
    TTEST   F3
    TTEST   F4
    TTEST   F5
    TTEST   F6  
    TTEST   F7
    TTEST   F8  
    TTEST   F9

    RET         ; return to DOS

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

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

TEQ DB 'In Triangle',0DH,0AH,'$'
FEQ DB 'Not In Triangle',0DH,0AH,'$'

Выход

In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle
Not In Triangle

C 414 (было 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");}

Добавлено оригинальное объявление функции для объяснения

/**
* 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);

Переписан как именованная функция: ввод через stdin по одной в каждой строке или через одну строку через пробел.

#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");
}

Java, 149 символов

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;

Ужасно, учитывая, что я должен написать «Математика». каждый раз. Это актуальная программа:

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));
}
}

где a - это x точки a, b - это x точки b, c для x of c, d - это y of a, e - это y of b, f - это y of c, а x и y - x и у точки. Логическое значение k определяет, является ли оно истинным или нет.

JavaScript 125/198

Если точки указаны в 8 аргументах:

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}

Если точки представлены в двухмерном массиве:

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

Этот код не использует ни одной из этих причудливых математических задач. Вместо этого он использует только простую алгебраическую уловку, чтобы определить, находится ли точка внутри треугольника или нет. Формула:

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

который говорит, точка находится на какой стороне линии , получается путем изменения определения наклона:

            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)

Если мы проверим все 3 стороны, все 3 должны привести к некоторым числам с одним и тем же знаком только тогда, когда точка находится внутри треугольника, поскольку мы проверяем ее вокруг треугольника. Если точка находится на стороне, то один из тестов должен вернуть 0.

Тестовый код jsFiddle: 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 символов (не считая пробелов и табуляций) подсчитываются при конвертации в 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 символов при конвертации в 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}

R, 23

Вдохновленный MATLAB ,

SDMTools::pnt.in.poly()

называется как SDMTools::pnt.in.poly(point,triangle)где pointвектор длины 2 и triangleявляется матрицей вершин 3x2. SDMTools доступен на CRAN.

Mathematica, 38 символов

RegionMember[Polygon[#[[1]]],#[[2]]] &

Пример:

d = {{{0, 0}, {1, 0}, {.5, .7}}, {.5, .6}};

RegionMember[Polygon[#[[1]]], #[[2]]] & @ d

(* Правда *)

C (gcc) , 108 байтов

i;f(a,b,c,d,e,f,g,h)float a,b,c,d,e,f,g,h;{i=(e-=a)*(h-=b)>(f-=b)*(g-=a);i=(c-=a)*f>(d-=b)*e==i&i==g*d>h*c;}

Попробуйте онлайн!

Принимает три перекрестных продукта и возвращает, 1если знак k̂компонента не изменяется.