18
\$\begingroup\$

You are the captain of a battleship. The engineering department's been cutting corners with designs this year, so the ship you're on takes the shape of a simple triangle.

You walk out onto the deck and enjoy the sea breeze... though not for long. An enemy has fired at you! — but will the shot hit?

Input

You may write either a function or a full program for this challenge.

Your program will take in 11 integers, ten of which are paired:

  • The first three pairs of integers (x1, y1), (x2, y2), (x3, y3) will specify the vertices of your ship. The triangle formed will have nonzero area.

  • The next pair of integers (ex, ey) specifies the location of the enemy's cannon. The enemy cannon will never lie on, or within the boundary of your ship.*

  • The pair (ax, ay) after that specifies where the enemy aimed at. This will be distinct from (ex, ey).

  • The final positive integer R specifies the range of the enemy's shot

*You'd be a terrible captain if you didn't even notice that happening!

Output

You must print/return a truthy value (e.g. true, 1) if the battleship will be hit, otherwise a falsy value (e.g. false, 0).

What is a hit?

The enemy shot is a straight line segment of length R from (ex, ey) in the direction of (ax, ay). If this line segment overlaps any part of the interior of your triangular battleship, then this counts as a hit. Otherwise it is not a hit.

Shots which graze along or only reach up to the boundary of the triangle do not count as a hit.

Examples

0 0 0 1 1 0
1 1
0 0
2

test1

Hit: The enemy has shot right through the centre of your ship!


2 0 0 2 4 4
0 0
1 1
1

test2

No hit: The enemy's range is too short, so you are safe.


0 0 1 2 3 0
-4 0
0 0
8

test3

No hit: The enemy has grazed the side of your ship, so this does not count as a hit. Lucky!


0 0 -1 3 4 -1
-3 -4
3 4
5

test4

No hit: The enemy shot just stops short of the ship, so you are safe. If the enemy's cannon had even slightly better range, then you would have been hit! Phew!


-2 -3 -3 6 7 -2
-6 2
1 -4
7

test5

Hit: Even though the shot didn't penetrate to the other side, this is still a hit.


-3 2 2 -4 7 -3
-3 -4
-3 0
10

test6

No hit: For the record, this is another close miss.


Additional test cases

0 0 6 0 6 8
-6 -8
6 8
20

test7

No hit: This is another graze, but at an angle.


0 0 -2 -5 5 3
-3 4
0 0
6

test8

Hit: The shot entered via a vertex of the ship.

Scoring

This is , so the shortest code in bytes wins. Standard loopholes apply.

\$\endgroup\$
  • \$\begingroup\$ Just to make sure we can't: can we assume the ship has no bottom and that there's a tiny gap between each two sides, so that if the shot manages to enter the ship through its corner, we count it as a miss? \$\endgroup\$ – John Dvorak Oct 26 '14 at 2:40
  • \$\begingroup\$ @JanDvorak If a shot cuts through the ship by entering through a vertex, then this would be a hit because the line segment overlaps the interior of the ship. So in the 4th example, if the range was greater than 5, then this would be a hit. \$\endgroup\$ – Sp3000 Oct 26 '14 at 2:45
  • \$\begingroup\$ How much are we allowed to play with the arguments? Are we allowed to group them, change the order, or require that they be floats? \$\endgroup\$ – FryAmTheEggman Oct 27 '14 at 18:05
  • \$\begingroup\$ @FryAmTheEggman You may group or reorder the arguments as necessary. You can use floats, but the program needs to work correctly for small grids (say, up to 20x20) without worrying about precision. \$\endgroup\$ – Sp3000 Oct 27 '14 at 21:38
  • \$\begingroup\$ I think the examples are missing one important case that make my intended solution fail: when the ship is penetrated through a corner, for example 0 0 -1 3 4 -1 -3 -4 3 4 6. \$\endgroup\$ – nutki Nov 16 '14 at 13:44
3
\$\begingroup\$

Python 3, 252 bytes

This is certainly the most variables I've ever used in code golf. :^P

from math import*;A=atan2
def h(a,b,c,d,e,f,g,h,i,j,R):
 r=R;_=0
 while r>0:Q=A(j-h,i-g);k,l=g+r*cos(Q),h+r*sin(Q);D=A(d-b,c-a);E=A(f-b,e-a);F=A(l-b,k-a);G=A(b-d,a-c);H=A(f-d,e-c);I=A(l-d,k-c);_=_ or(D<F<E or E<F<D)and(G<I<H or H<I<G);r-=.001
 return _

Slightly ungolfed, with comments:

from math import*
# Parameters:
#  (a,b) (c,d) (e,f) - vertices of the triangle
#  (g,h) - location of cannon
#  (i,j) - aim of cannon
#  R - range of cannon
# Variables within function:
#  _ - was this shot a hit?
#  r - distance 0 < r <= R that we're testing
#  Q - angle between cannon source and destination
#  (k,l) - point that we're testing
#  D,E,F - angles between point 1 and 2,3,test
#  G,H,I - angles between point 2 and 1,3,test
def h(a,b,c,d,e,f,g,h,i,j,R):
    r=R;_=0
    while r>0:
        Q=atan2(j-h,i-g)
        k,l=g+r*cos(Q),h+r*sin(Q)
        D=atan2(d-b,c-a)
        E=atan2(f-b,e-a)
        F=atan2(l-b,k-a)
        G=atan2(b-d,a-c)
        H=atan2(f-d,e-c)
        I=atan2(l-d,k-c)
        _=_ or(D<F<E or E<F<D)and(G<I<H or H<I<G)
        r-=.001
    return _

How it works:

  • Calculate the endpoint of the shot.
  • Test lots of points along the line from the endpoint to the cannon's location:
    • Calculate angles from vertex 1 to other two vertices and to test point;
    • Calculate angles from vertex 2 to other two vertices and to test point;
    • If the test point angle is between the other two angles, in both cases, then the test point is within the triangle and the ship has been hit.

Sample runs:

>>> h(0,0,0,1,1,0,1,1,0,0,2)
True
>>> h(0,0,1,2,3,0,-4,0,0,0,8)
False
>>> h(0,0,-1,3,4,-1,-3,-4,3,4,5)
False
>>> h(-2,-3,-3,6,7,-2,-6,2,1,-4,7)
True
\$\endgroup\$
2
\$\begingroup\$

Python 2.7, 235 bytes

from numpy import*
X=cross
h=lambda q,w,a,s,y,x,c,v,d,f,r:max([(X([a-q,s-w],[c+k*(d-c)-q,v+k*(f-v)-w])>0)==(X([y-a,x-s],[c+k*(d-c)-a,v+k*(f-v)-s])>0)==(X([q-y,w-x],[c+k*(d-c)-y,v+k*(f-v)-x])>0)for k in arange(0,r/hypot(d-c,f-v),1e-4)])

Computes the cross product AB x AP between the corners A,B and the point P. If all three have the same sign, then the point is inside the triangle.

Ungolfed:

from numpy import *
def i(q,w,a,s,y,x,e,r): # helper-function, checks whether ER is inside the triangle QW-AS-YX
  t=cross([a-q,s-w],[e-q,r-w])>0
  g=cross([y-a,x-s],[e-a,r-s])>0
  b=cross([q-y,w-x],[e-y,r-x])>0
  return t==g==b

def h(q,w,a,s,y,x,c,v,d,f,r):
  R=arange(0,r/hypot(d-c,f-v),1e-3)
  return max([i(q,w,a,s,y,x,c+k*(d-c),v+k*(f-v)) for k in R])

Tests:

In : h(0,0,0,1,1,0,1,1,0,0,2)
Out: True

In : h(-3,2,2,-4,7,-3,-3,-4,-3,0,10)
Out: False

In : h(0,0,1,2,3,0,-4,0,0,0,8)
Out: True
     Grazes may count as hits...
In : h(1,2,0,0,3,0,-4,0,0,0,8)
Out: False
     ...or not, depending on the order of edges
\$\endgroup\$
1
\$\begingroup\$

C, 247 bytes

Definitely not quite golfed yet.

#include<math.h>
int z(float*k){float s=1e-3,t=s,p=k[8]-k[6],q=k[9]-k[7],r=k[10]/hypot(p,q);int w=0;for(;t<1;t+=s){float x=k[6]-k[0]+p*r*t,y=k[7]-k[1]+q*r*t,b=k[2]*k[5]-k[3]*k[4],d=(x*k[5]-y*k[4])/b,e=(x*k[3]-y*k[2])/b;w|=d>0&e<0&d-e<1;}return w;}

Currently this uses an approach similar to DLosc's solution, i.e. iterates through all possible coordinates on the line segment to determine if it intersects with the triangle. (So it will fail if the range is over 1000) However, it uses the formula from http://mathworld.wolfram.com/TriangleInterior.html to determine if a point is inside the triangle. This avoids a bunch of trigonometric functions.


Example check, should print 1 0 0 0 1 0.

#include <stdio.h>
int main() {
    {
        float arr[] = {0,0,0,1,1,0,1,1,0,0,2};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {2,0,0,2,4,4,0,0,1,1,1};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {0,0,1,2,3,0,-4,0,0,0,8};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {0,0,-1,3,4,-1,-3,-4,3,4,5};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {-2,-3,-3,6,7,-2,-6,2,1,-4,7};
        printf("%d\n", z(arr));
    }

    {
        float arr[] = {-3,2,2,-4,7,-3,-3,-4,-3,0,10};
        printf("%d\n", z(arr));
    }
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6) 320 448 522 627

(Could still be golfed more?)

Steps:

  1. Find the actual hit target (point at distance r on the line from enemy to aim)
  2. Hit: if the segment from enemy to target intersect any of the sides of the ship, but not at the endpoints
  3. Hit too: if the target is inside the ship - even if the shot entered at a vertex - test case 8

Ref:
Segment intersection
Point inside triangle
Point in a segment given a distance

Test in Firefox

C=(i,j,k,l,m,n,g,h,a,b,r,
  d=a-g,e=b-h,f=r/Math.sqrt(d*d+e*e),
  p=g+f*d,q=h+f*e,
  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=(i,j,k,l,
     a=k-i,b=l-j,c=p-g,d=q-h,e=i-g,f=j-h,
     s=a*f-b*e,t=c*f-d*e,m=a*d-c*b)=>
     m&&((s/=m)>0&s<1&(t/=m)>0&t<1)
)=>s>0&t>0&s+t<1|S(i,j,k,l)|S(i,j,m,n)|S(m,n,k,l)

// Test
MyOutput.innerHTML = ['Test1', C(0,0, 0,1, 1,0, 1,1, 0,0, 2),
'<br>Test2', C(2,0, 0,2, 4,4, 0,0, 1,1, 1),
'<br>Test3', C(0,0, 1,2, 3,0, -4,0, 0,0, 8),
'<br>Test4', C(0,0, -1,3, 4,-1, -3,-4, 3,4, 5),
'<br>Test5', C(-2,-3, -3,6, 7,-2, -6,2, 1,-4, 7),
'<br>Test6', C(-3,2, 2,-4, 7,-3, -3,-4, -3,0 ,10),
'<br>Test7', C(0,0, 6,0, 6,8, -6,-8, 6,8, 20),
'<br>Test8', C(0,0,-2,-5, 5,3, -3,4, 0,0, 6)];
<div id="MyOutput"></div>

Ungolfed

function check(p0x, p0y, p1x, p1y, p2x, p2y, ex, ey, ax, xy, r)
{
  var sec = function(p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y)
  {
      var s10x = p1x - p0x, s10y = p1y - p0y, 
          s32x = p3x - p2x, s32y = p3y - p2y,
          s02x = p0x - p2x, s02y = p0y - p2y,
          s = s10x * s02y - s10y * s02x, t = s32x * s02y - s32y * s02x,
          d = s10x * s32y - s32x * s10y;
      return d && (s/=d) > 0 && s<1 && (t/=d) > 0 && t < 1 && [p0x + (t * s10x), p0y + (t * s10y)];
  }
  var pr = function(p0x, p0y, p1x, p1y, r)
  {
      var dx = (p1x-p0x), dy = (p1y-p0y), f = r/Math.sqrt(dx*dx+dy*dy);
      return [p0x + f*dx, p0y+f*dy];
  }
  var inside = function(p0x, p0y, p1x, p1y, p2x, p2y, px, py)
  {
      var area2 = (-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y),
          s = (p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py)/area2,
          t = (p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py)/area2;
      return s > 0 && t > 0 && s+t < 1;
  }
  var tx, xy;
  [tx, ty] = pr(ex, ey, ax, ay, r);

  return inside(p0x, p0y, p1x, p1y, p2x, p2y, tx,ty)
  || sec(p0x, p0y, p1x, p1y, ex, ey, tx, ty)
  || sec(p0x, p0y, p2x, p2y, ex, ey, tx, ty)
  || sec(p2x, p2y, p1x, p1y, ex, ey, tx, ty);
}  
\$\endgroup\$

Your Answer

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

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