# Geometry question placing a point within a figure **URL:** \ **Category:** Factual Questions\ **Created:** [March 17, 2003, 8:52am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960 "2003-03-17T08:52:25Z")\ **Posts on this page:** 3\ **Page:** 2
**Author:** ![DaveW](https://avatars.discourse-cdn.com/v4/letter/d/9d8465/32.png) [@DaveW](https://boards.straightdope.com/u/DaveW)\ **Post date:** [March 17, 2003, 3:35pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/21 "2003-03-17T15:35:38Z")
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. ---
**Author:** ![aubries](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@aubries](https://boards.straightdope.com/u/aubries)\ **Post date:** [March 17, 2003, 3:53pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/22 "2003-03-17T15:53:13Z")
> [@](#): > > \*Originally posted by Mangetout \* > \*\*It would if there can be any sort of rigorous method of defining ‘close to’ - I’m looking for methods that could be efficiently implemented by a computer program. \*\* My bad. I assumed this was a plain old aplied math question, not a programming one.:smack: ---
**Author:** ![aubries](https://avatars.discourse-cdn.com/v4/letter/a/53a042/32.png) [@aubries](https://boards.straightdope.com/u/aubries)\ **Post date:** [March 17, 2003, 3:54pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/23 "2003-03-17T15:54:35Z")
By which of course I meant applied.:smack: :smack: [Previous page](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960.md?page=1)