How do I determine if a series of points (or polygon) is within a rectangular region?

I have been looking at posts about determining if a point lies within a polygon or not and the answers are either too vague, abstract, or complex for me. So I am going to try to ask my question specific to what I need to 开发者_如何学编程do.

I have a set of points that describe a non-straight line (sometimes a closed polygon). I have a rectangular "view" region. I need to determine as efficiently as possible whether any of the line segments (or polygon borders) pass through the view region.

I can't simply test each point to see if it lies within the view region. It is possible for a segment to pass through the region without any point actually inside the region (ie the line is drawn across the region).

Here is an example of what I want to determine (red means the function should return true for the set of points, blue means it should return false, example uses straight lines and rectangles because I am not an artist).

Another condition I want to be able to account for (though the method/function may be a separate one), is to determine not just whether a polygon's border passes through the rectangular region, but whether the region is entirely encompassed by the polygon. The nuance here is that in the situation first described above, if I am only concerned with drawing borders, the method should return false. But in the situation described here, if I need to fill the polygon region then I need the function to return true. I currently do not need to worry about testing "donut" shaped polygons (thank God!).

Here is an example illustrating the nuance (the red rectangle does not have a single vertex or border segment passing through the on-screen region, but it should still be considered on-screen):

For the "does any line segment or polygon border pass through or lie on screen?" problem I know I can come up with a solution (albeit perhaps not an efficient one). Even though it is more verbose, the conditions are clear to me. But the second "is polygon region on screen?" problem is a little harder. I'm hoping someone might have a good suggestion for doing this. And if one solution is easily implemented on top of the other, well, booya.

As always, thank you in advance for any help or suggestions.

PS I have a function for determining line intersection, but it seems like overkill to use it to compare each segment to each side of the on-screen region because the on-screen region is ALWAYS a plain [0, 0, width, height] rectangle. Isn't there some kind of short-cut?

---

What you are searching for is named a Collision Detection Algorithm A Google search will lead you to plenty of implementations in various language as well as a lot of theory

There are plenty of Geometric theory behind, from the simplest bisector calculus to Constrained Delaunay Triangulations and Voronoi Diagrams (that are just examples). It depends on the shape of Object, the number of dimensions and for sure the ratio between exactness needed and computing time afforded ;-)

Good read

---

PS I have a function for determining line intersection, but it seems like overkill to use it to compare each segment to each side of the on-screen region because the on-screen region is ALWAYS a plain [0, 0, width, height] rectangle. Isn't there some kind of short-cut?

It's not an overkill, its neccessary here. The only kind of shortcut I can think of is to hardcode values [0, 0, width, height] into that function and simplify it a bit.