3
$\begingroup$

I'm having a bit of an issue with the following problem:

Write a brief (1/2 page) design specification document (including pseudo code for the algorithm itself) that describes your approach to solving the following geometric problem: Given two straight lines in 2D (each line defined by a pair of points), determine whether they intersect.

Explain how you could apply the test in to write an algorithm to find whether a point lies inside or outside a 2D closed polygon consisting of $N$ points joined by straight lines.

As far as I am aware, it is possible to work out whether 2 lines intersect by working out each line equation, and then simultaneously solving those. IE:

2 lines at $(4, 2)$ to $(2, 0)$ and $(0, 4)$ to $(4, 0)$.

Solving simultaneously, the two lines intersect at $(3, 1)$

However, I am not quite sure how I would apply this method into an algorithm that for a 2D polygon as specified in the question.

Any help would be greatly appreciated!

  • 3
    it has to do with finding how many times a certain line is intersecting with the polygon. i could be more specific but i didn't want to spoil your enthusiasm for research.2012-09-11
  • 1
    This should be on Math Exchange2012-09-11

3 Answers 3