Geometry question placing a point within a figure

I once programmed a system wherein the user could draw shapes on the screen, and the program would need to figure out, given the list of points used to draw each shape, whether or not a mouse click was inside any particular shape.

The only condition on the drawings was that no two line segments could cross. The only condition on “inside” was that if the mouse click fell precisely on one of the lines, that would be “inside.”

Given these conditions, the solution I found was, for each shape, to count the number of intersections between the line segments and an imaginary line segment drawn between the mouse click location and the top of the screen. If it’s an even number of intersections, the mouse click was outside the figure. An odd number of intersections meant the mouse click was inside. Convex or concave shapes, doesn’t matter.

The only exception during that process is when a line segment is parallel to the vertical imaginary line. If the x-values don’t match, or if the y-value for the mouse click isn’t within the line segment, the counter doesn’t get incremented. But if those conditions aren’t true, then the mouse was on the line, and thus “inside,” and the whole process gets short-cut at that point in the algorithm.

To extend this out to any set of points, only the length of the imaginary line needs to change. It only needs to be long enough to definitely be outside the figure (and it doesn’t need to be vertical, either). If you were to take the maximum x-values from all points, and then add 1 (or 10 or 100 or whatever “comfort factor” you want), you’d create an imaginary horizontal line segment running off to the right of the point being tested. Then you count the intersections with that line. Odd equals inside.

You could use diagonal lines, but one of the nice things about using vertical or horizontal lines is that it makes the tests for intersection much easier. If the x-values for two points defining a line segment are both less than the x-value of an imaginary vertical line, the code doesn’t need to bother with calculating the slope of the segment or anything else - it’s already shown that there’s no intersection.

My bad. I assumed this was a plain old aplied math question, not a programming one.:smack:

By which of course I meant applied.:smack: :smack: