Line through Polygon

Question

Input: A line of the standard slope-and-intercept form: mx+b, as well as a set of Cartesian points determining the vertices of a polygon. Assume that the x and y values of the points will be integers.

Output: A boolean, which is true if the line enters or touches the polygon, and is false otherwise.

This is a little tricky, so I'll give a clue: turn the vertices that determine an edge into lines.

Test Cases
2x+3 (1,2) (2,5) (5,10) -> False
5x+0 (5,10) (2,10) (2,-10) (5,-10) -> True
0.5x+3.1 (1, 2), (-1, 2), (5, 8), (6, 7), (2, 10) -> True

Shortest or most creative code wins. I don't know too many languages, so explain your algorithm in your post. Good luck!

Answer 1

Ruby, 103 101 characters

m,b,*q=gets.scan(/[\d\.]+/).map{|t|t.to_f}
s=t=!0
q.each_slice(2){|x,y|x=x*m+b;s|=x<=y;t|=x>=y}
p s&t

Input is on STDIN in the form specified in the question while output goes to STDOUT.

Answer 2

Scala 255: 224

object P extends App{
val(m,p)=(args(0).split("[^0-9-.]").filter(!_.isEmpty)).map(_.toFloat)splitAt 2
def v(l:Array[Float])=(l(1)-m(0)*l(0)-m(1))*(l(3)-m(0)*l(2)-m(1))<=0
println((p.drop(p.size-2)++p).sliding(4,2) exists v)}

Using splitAt, inspired by Howard. :) Before:

object P extends App{
val f=args(0).split("[^0-9-.]").filter(!_.isEmpty)
val m=f.take(2).map(_.toFloat)
val p=f.drop(2).map(_.toInt)
def v(l:Array[Int])=(l(1)-m(0)*l(0)-m(1))*(l(3)-m(0)*l(2)-m(1))<=0
println((p.drop(p.size-2)++p).sliding(4,2).exists(v))
}

How:

val f=args(0).split("[^0-9-.]").filter(!_.isEmpty)

• Line 2 just splits and filters away everything which isn't part of float or int, since we don't need '(' and ',' and such to identify our parameters - position is enough.
• m is shorthand for mn in m*x+n, the values m and n are floats.
• p is the polygon values.
• v is the verify function

Assume we have f(x) = mx + n and the line pq:

               f(x)=mx+n
 |            / 
 |          / |
 |p  *'--,,'  |
 |   |   / ''-* q
 |   | /       
 |   /
 | /
 /___________________

f(x) crosses only by random the origin in this example. For the two points of the polygon p and q we can for px calculate f(px) and it can lay to the south or to the north of py, the real value of the polygon, or lay exactly on it.

If both calculated values f(px) and f(qx) are on the same side, north or south, the line doesn't cross.

So we have two values for the function:

val a = m*px+n
val b = m*qx+n

if (a == py || b == qy) the function line touches one of the points.

if ((a < py && b > py) || (a > py && b < py)) they are on different sides, and cross as well. We can express this by substracting:

d1 = py - a
d2 = qy - b 

if (( d1 == 0 || d2 == 0 || (sign (d1) != sign(d2))) ...

If the signs are different, the multiplication will return a negative value, and if they match, it returns a positive value. If one of the values is 0, the product is null. So we can condense the whole question to:

d1 * d2 <= 0

And that's what the verify-method v does.

The values of the polygon are (x1, y1), (x2, y2), ...(xn, yn), but they are flattened to x1, y1, x2, y2, ...xn, yn. The drop-statement takes the last 2 of them and prepends them to the front, to build a closed shape (xn, yn -> x1, y1). Sliding (4, 2) takes 4 values and advances for a step size of 2 through the collection. If a pair of xy exists, for which the verify function returns true, the line crosses the polygon or touches it.

Now I have to understand why the Ruby solution is so much shorter. Okay - a few less type declarations, shorter conversions. No println, no object, no App. Similar approach.

Invocation:

 scala P "0.5x+3.1 (1, 2), (-1, 2), (5, 8), (6, 7), (2, 10)"

Answer 3

J, 80 characters

('True';'False'){~*/2=/\0>_2(]-1{y+0{y*[)/\2}.[y=.".'-_x + ( , ) 'charsub 1!:1[1

Takes input from the keyboard in the format specified in the question. It uses the algorithm suggested by Peter Taylor in the comments to the question.

Explanation (bearing in mind that J is read from right to left):

1!:1[1 waits for a line of input from the keyboard.

'-_x + ( , ) 'charsub replaces all occurances of x,+,(,, and ) with a space and replaces - with _. This turns the input into a list of numbers (with _ in front of the negative numbers as required for J).

". reads in the list as an array instead of a string.

y=. assigns the list to the variable y.

2}. removes the first 2 elements of the list.

_2(...)/\ takes each pair of numbers and applies the verb in the brackets to them.

]-1{y+0{y*[ calculates mx+c with the x from this pair of numbers and takes the result out of the y from this pair of numbers.

0> checks if each returned number is less than 0.

At this point we have a list of 1s and 0s depending on whether each point is above or below the line.

2=/\ takes each pair and checks if they are equal.

Now, if all points are on the same side of the line we have all 1s otherwise there are 0s in there somewhere.

*/ multiplies all the 1s and 0s together.

Now we have 0 if the points fall on both sides of the line and 1 and they all fall on the same side of the line.

{~ uses the 1 or 0 as an index into the list ('True';'False') returning the required output.