23
\$\begingroup\$

Challenge

Premise

Bob lost1 Alice's precious grand piano. Big mistake. Alice has now stolen Bob's low-orbit ion cannon.

Alice refuses to just make up with Bob, so let's help her give him a light tap on the roof. Suppose that from the top Bob's house looks like a lattice polygon, where all points have integer coordinates...

1. So he says.

Task

Input: an \$n\times2\$ matrix of integers (where \$3\leq n\leq16\$) representing the coordinates of the points of an \$n\$-gon, given in the order in which you would join them up. To be absolutely clear, the first and second values in each of the \$n\$ rows are respectively an \$x\$- and a \$y\$-coordinate.

  • If it would be far more natural to take something other than a 2D matrix in your language or it's impossible to take one, you can use something else. Should this happen, please clearly state what you're doing.
  • \$x\$-coordinates or \$y\$-coordinates may be negative, zero or positive.
  • The polygon formed by joining up the points in the given order may be convex or concave.
  • There's no need to consider degenerate polygons.
  • No input polygon will be self-intersecting, thank goodness.

Output: two numbers of any numeric type, respectively representing the \$x\$-coordinate and \$y\$-coordinate of a point within the polygon.

  • No, your numbers needn't be integers.
  • Your output needn't be consistent for any single input. You're allowed to generate an output in any valid way that shortens your code.
  • Corners and edge points are forbidden. Sorry.

Example 1

Input:

0 0
3 0
3 4

Possible output: 1 1

Example 2

Input:

-3 -1
0 1
-1 -1
-1 0

Possible output: -0.31416 0.42

Remarks

  • This is , so fewest bytes wins.
  • The tag is here only to be on the safe side. I expect that not every answer will use randomness.
  • Standard rules, I/O rules and loophole rules apply.
  • If possible, link an online demo of your code.
  • Please explain your code.
\$\endgroup\$
  • 2
    \$\begingroup\$ Got to love that premise :D I half expected us to need to calculate also the strength of the shot based on the cannon's altitude, the current day's weather at Bob's place and the age of the captain :P \$\endgroup\$ – Kaddath Apr 23 at 15:46
  • \$\begingroup\$ Presumably the point must not be on the boundary of the polygon? Otherwise any coordinate within the input matrix is a valid answer! Should hopefully be obvious but probably worth a mention in the rules to be explicit \$\endgroup\$ – Jarmex Apr 23 at 15:46
  • \$\begingroup\$ Brute-forcing is forbidden is a non-observable requirement. Maybe it should be changed to your output must be deterministic? (Although I realize it is a quite different rule.) \$\endgroup\$ – Arnauld Apr 23 at 15:49
  • 7
    \$\begingroup\$ I'd suggest adding a test case with a concave polygon where taking the average of the vertices yields a point not in it, since someone is bound to try this. \$\endgroup\$ – xnor Apr 23 at 16:04
  • 1
    \$\begingroup\$ @xnor dang, you're ruining by big secret plan to rule them all.. gotta think again \$\endgroup\$ – Kaddath Apr 23 at 16:08
15
\$\begingroup\$

Python 3.8, 116 110 bytes

lambda p:[x:=min(p)[0]+.1,sum(sorted(b+(d-b)*(x-a)/(c-a)for(a,b),(c,d)in zip(p,p[-1:]+p)if(a<x)^(c<x))[:2])/2]

Try it online!

Input: A list of points, each is a tuple of 2 integers.
Output: A point as a list of 2 numbers.

Approach

Draw a vertical line through the polygon. Select the first 2 points where the line intersects with the polygon edges. Any point between those 2 points must be inside the polygon.

How to pick an inside point

Note that the line should be chosen such that it doesn't intersect any polygon vertex.

Code explanation

The x-coordinate of the line is selected as the minimum x of all vertices, plus a small amount (0.1 is used in this case):

x:=min(p)[0]+.1

This ensures that the line intersects the polygon, and that it doesn't pass through any vertex (since vertices all have integer coordinates).

For each edge through vertices \$(a,b)\$ and \$(c,d)\$, the line intersects the edge if \$a<x<c\$ or \$a>x>c\$. Golfed using xor trick:

if (a<x)^(b<x)

The y-coordinate of each intersection is calculated using the following formula: $$\frac{y-b}{x-a}=\frac{d-b}{c-a}$$ or b+(d-b)*(x-a)/(c-a)

The y-coordinate of the final point is calculated as the average of the smallest 2 y-coordinates.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Arg! I thought Python 3.8 handles 0 division... \$\endgroup\$ – Third-party 'Chef' Apr 24 at 12:16
11
\$\begingroup\$

Wolfram Language (Mathematica), 11 bytes

Mathematica has a built-in for pointing ion cannons. In fact, as far as I know, it should support self-intersecting roofs. Takes input as a polygon.

RandomPoint

Try it online!

By the way, RandomPoint@Polygon@#& is 5 bytes of Sledgehammer: ⡘⠼⡃⡖⣳.

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Perl 5, 191 bytes

sub{sub c{($_[0]+$_[1])/2}map{$x{$_->[0]}=0}@_;$x=c sort
keys%x;for(0..$#_){($t,$y)=@{$_[$_]};($d=$_[$_-1][0]-$t)&&($t=($x-$t)/$d,$t*(1-$t)>0&&push@y,$y+$t*($_[$_-1][1]-$y))}@{[$x,c
sort@y]}}

It's deterministic and O(n).

Choose an \$x\$-coordinate \$P_x\$ ($x) halfway between the smallest two unique input \$x\$ coordinates. Test each polygon side to see if that line segment intersects the \$x=P_x\$ vertical line. If it does, add the \$y\$-coordinate of that intersection point to @y. Finally, let \$P_y\$ be halfway between the two smallest values in @y, and the output is \$(P_x,P_y)\$: since you cross exactly one edge to get here from the \$y=-\infty\$ end of the \$x=P_x\$ line, the point must be inside the polygon.

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Java 10, 378 bytes

import java.awt.geom.*;X->Y->{var p=new Path2D.Double();p.moveTo(X[0],Y[0]);int l=X.length,f=1,i=1;for(;i<l;)p.lineTo(X[i],Y[i++]);p.closePath();var r=p.getBounds();double x=0,y=0;for(;f>0;)for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),i=f=0;i<l-1;)f=!p.contains(x,y)|new Line2D.Double(X[i],Y[i++],X[i],Y[i]).contains(x,y)?1:f;return x+","+y;}

Having builtins is usually an advantage, right?.. :/ I'll see if a manual approach is shorter later on.

Input-coordinates as two loose arrays for x and y respectively, output as a comma-delimited String of the random x,y-coordinate.

Try it online.

Explanation:

import java.awt.geom.*;      // Required import for Path2D and Line2D
X->Y->{                      // Method with two int-arrays as parameters and String return-type
  var p=new Path2D.Double(); //  Create a Path2D
  p.moveTo(X[0],Y[0]);       //  Start at the first input-coordinate
  int l=X.length,            //  Store the amount of points in `l`
      f=1,                   //  Flag integer, starting at 1
  i=1;for(;i<l;)             //  Loop `i` in the range [1, l):
    p.lineTo(X[i],Y[i++]);   //   And draw a line to the `i`'th x,y-coordinate of the input
  p.closePath();             //  Close the path, so we now have our polygon
  var r=s.getBounds();       //  Create a Rectangle that encapsulates this polygon
  double x=0,y=0;            //  Create the random x,y-coordinate
  for(;f>0;)                 //  Loop as long as the flag is still 1:
    for(x=r.getX()+Math.random()*r.getWidth(),y=r.getY()+Math.random()*r.getHeight(),
                             //   Get a random x,y-coordinate within the Rectangle
        i=f=0;               //   (Re)set both the flag and `i` to 0
        i<l-1;)              //   Inner loop `i` in the range [0, l-1):
      f=!p.contains(x,y)     //    If the Path2D-polygon does NOT contain this random x,y-coordinate
        |                    //    Or:
         new Line2D.Double(  //    Create a Line2D
          X[i],Y[i++],       //    from the `i`'th x,y-coordinate of the input
          X[i],Y[i])         //    to the `i+1`'th x,y-coordinate of the input
         .contains(x,y)?     //    And if this line does contain the random x,y-coordinate:
          1                  //     Change the flag to 1
        :                    //    Else:
          f;                 //     Keep the flag the same
  return x+","+y;}           //  And finally return our random x,y-coordinate as String
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

MATL, 19 bytes

`xx,Xr]yy&G4$TF#ZQ~

The input is a vector with x coordinates, then a vector with y coordinates. The ouput is x, then y. Running time is random, but finite with probability 1.

Try it online!

How it works

The program randomly generates points with a bidimensional Gaussian distribution until one of them happens to be inside the polygon. This distribution spans the full plane, so the code eventually finds a solution.

`       % Do...while
  xx    %   Delete twice. In the first iterarion this takes the two inputs
        %   (implicitly) and deletes them. In subsequent iterations this
        %   deletes the previous x, y candidate coordinates, which turned out
        %   not to be a solution
  ,     %   Do twice
    Xr  %     Generate a random number with a standard Gaussian distribution.
        %     Note that his covers the whole plane, although points close to
        %     the origin have greater a probability density
  ]     %   End. The stack contains two numbers representing x, y coordinates
        %   of a potential solution
  yy    %   Duplicate top two elements in the stack
  &G    %   Push the two inputs
  4$    %   Specify four inputs for the next function
  TF#   %   Specify the first of two possible outputs for the next function
  ZQ    %   Inpolygon function: takes four inputs, where the first and second
        %   define x, y coordinates of a point, and the third and fourth define
        %   the x, y coordinates of the polygon vertices. The (first) output is
        %   true if the point is strictly in the polygon, and false if not
  ~     %   Negate
        % End (implicit). A new iteration starts if the top of the stack is
        % true, meaning that the tested x, y values were not a solution
        % Display (implicit)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Erlang (escript), 174 bytes

f(P)->X=hd(lists:min(P))+0.1,[X,lists:sum(lists:sublist(lists:sort([B+(D-B)*(X-A)/(C-A)||{[A,B],[C,D]}<-lists:zip(P,[lists:last(P)|lists:droplast(P)]),(A<X)xor(C<X)]),2))/2].

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 2, 89 bytes

l=input()
(B,b),(A,a),(C,c)=min(zip(l[1:]+l,l,l[2:]+l))
print.2+B,b+(a+c-b*2)/(A+C-B*2)/5

Try it online!

Here's the strategy for picking the point:

  • Take the vertex \$p\$ with the smallest \$x\$-coordinate. If there's a tie, any is fine.
  • Consider the two edges leading from \$p\$. To obtain a direction that's in between them, add them as vectors.
  • Travel from \$p\$ in this direction far enough to go +0.2 units in the \$x\$ direction, and pick the point you arrive at.

Because \$p\$ is among the leftmost points of the polygon, any direction that's in between the two edges leading from it points inside the polygon. Because we only travel 0.2 units in the \$x\$ direction and all vertices lie on integer points, we can't have exited the polygon after going less than 0.5.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This fails for the edge case of the unit triangle - the resulting point lies on the triangle's hypotenuse. I think changing 0.5 to something smaller like 0.2 fixes this problem. \$\endgroup\$ – Surculose Sputum Apr 24 at 5:53
  • \$\begingroup\$ @SurculoseSputum Good catch. I suspect a smallest value does indeed work, but I'll delete this now and think about that later. \$\endgroup\$ – xnor Apr 24 at 7:16
  • 1
    \$\begingroup\$ @SurculoseSputum I think I've convinced myself that 0.2, or indeed any value less that 0.5 works, by considering shearing the coordinates to make one edge from the point it be horizontal. I don't have a proof though, so let me know if it still doesn't work. Thanks again for catching this. \$\endgroup\$ – xnor Apr 28 at 4:08

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.