# 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:** 20\ **Page:** 1
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 8:52am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/1 "2003-03-17T08:52:25Z")
Given four pairs of coordinates, three of them describing the vertices of a triangle on a plane, is it possible to determine whether the point described by the fourth pair is inside or outside the triangle figure? Also, How about a point within a quadrilateral described by its four vertices? ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 9:03am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/2 "2003-03-17T09:03:25Z")
Yes it is. Is the question really “what’s the most efficient algorithm for determining the answer analytically”? (_Pairs_ of _coordinates_?) ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 9:12am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/3 "2003-03-17T09:12:13Z")
> [@](#): > > [Test for Point Inside Triangle](http://mathforum.org/library/drmath/view/54735.html) > How can I know whether a point P(x,y) is in a triangle with vertices P1(x1,y1), P2(x2,y2), and P3(x3,y3)? > > There are two possibilities: > > ``` > 1. P is INSIDE or ON, > 2. P is OUTSIDE triangle P1P2P3. > > ``` > > If you draw a sketch and consider triangles, > > ``` > PP1P2, PP2P3, PP3P1 > > ``` > > You will notice the following relationship in their areas. > > If P is ON or INSIDE, > > ``` > A(PP1P2) + A(PP2P3) + A(PP3P1) = A(P1P2P3) > > ``` > > If P is OUTSIDE then, > > ``` > A(PP1P2) + A(PP2P3) + A(PP3P1) > A(P1P2P3) > > ``` > > Area of a triangle can be found using the determinant: > > ``` > A = abs(1/2 * |x1 y1 1| ) > |x2 y2 1| > |x3 y3 1| > > ``` > > You can write a function in C++ that accepts the three points > (as Classes) or their coordinates and returns the area. > > Finally if you have to distinguish between ON and INSIDE, put the point in the equations of the three lines that form the sides. If one of them is satisfied, P is ON a side. If two are satisfied, P is a vertex of the triangle. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 9:13am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/4 "2003-03-17T09:13:54Z")
> [@](#): > > \*Originally posted by Desmostylus \* > \*\*(_Pairs_ of _coordinates_?) \*\* Brought to you by the department of redundancy department. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [March 17, 2003, 9:17am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/5 "2003-03-17T09:17:15Z")
Here’s the method I’ve used, which is similar to the one **Desmostylus** gives. I don’t know which one I like better yet… Draw the vectors PA, PB, and PC. Take the three cross products PA × PB, PB × PC, and PC × PA. For each of these three vectors, take the dot product with the the perpendicular vector to the plane\*. This will give you three scalars. If they all have the same sign, P is inside triangle ABC. If one of them has a different sign, it’s outside. If one or more has a value of 0, then P is **on** the triangle. This method should also work with a convex n-gon. You just have to take n cross products and n dot products. For a non-convex n-gon, though, it gets tricky. Quadrilaterals should be okay, however. - - If it’s easier, you may use AB × AC in place of the perpendicular vector. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [March 17, 2003, 9:21am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/6 "2003-03-17T09:21:02Z")
Here’s the C++ code I wrote for it, by the way. In this case, the points are all in the x-y plane, so the perpendicular to the plane is in the z-direction. So, instead of dot products, I just take the z-component: ```auto int Within(vect2d Omega, vect2d Alpha, vect2d Beta, vect2d Gamma) { vect3d A = Alpha, B = Beta, C = Gamma, Z = Omega; if ((((A - Z) * (B - Z)).z > 0) != (((A - C) * (B - C)).z > 0)) return 0; if ((((B - Z) * (C - Z)).z > 0) != (((B - A) * (C - A)).z > 0)) return 0; if ((((C - Z) * (A - Z)).z > 0) != (((C - B) * (A - B)).z > 0)) return 0; return 1; } ``` ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 9:27am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/7 "2003-03-17T09:27:39Z")
> [@](#): > > \*Originally posted by Mangetout \* > > > [@](#): > > > > _Originally posted by Desmostylus_ > > (Pairs of coordinates?) > > \*\*Brought to you by the department of redundancy department. \*\* Actually, I think I might take that back; a coordinate is one member of a set of numbers, a single coordinate is required to describe a point on a one-dimensional line, but to describe a point on a 2D plane, a _pair_ of coordinates is required. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 9:29am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/8 "2003-03-17T09:29:57Z")
Freakin’ spacing. ```auto Area of a triangle can be found using the determinant: A = abs(1/2 * |x1 y1 1| ) |x2 y2 1| |x3 y3 1| ``` Note that it’s entirely possible for a quadrilateral to be concave, so you have to be careful about extending this method. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [March 17, 2003, 10:22am UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/9 "2003-03-17T10:22:12Z")
You’re right about that. I was thinking parallelogram, for some reason. For a general quadrilateral, you can divide it up into two triangles, and test point P for both of them. This is not as simple as it sounds, however. If you split quadrilateral ABCD into triangles ABC and CDA, for instance, you must test B to make sure it’s not inside triangle CDA, and D to make sure it’s not inside triangle ABC. If either of those tests fails, you can use triangles BCD and DAB instead. At any rate, even if your 4-gon is convex, you run the risk of P lying on the dividing line between your two triangles. ---
**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, 1:14pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/10 "2003-03-17T13:14:59Z")
> [@](#): > > \*Originally posted by Desmostylus \* > \*\*Finally if you have to distinguish between ON and INSIDE, put the > point in the equations of the three lines that form the sides. If one of > them is satisfied, P is ON a side. If two are satisfied, P is a vertex of > the triangle. \*\* Um, if P is a vertex of the triangle, that would be screamingly obvious from the original conditions. Speaking of which, and not to deflate any of the sound methods described above, but wouldn’t it be way, way, way easier just to graph the system and inspect it? If the point shows up too close to one of the lines in your sketch, find the equation for the line in slope-intercept form and test the point for \<, \> or =. Seems like less work to me, and 100% reliable. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 1:23pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/11 "2003-03-17T13:23:09Z")
> [@](#): > > \*Originally posted by aubries \* > \*\*but wouldn’t it be way, way, way easier just to graph the system and inspect it? If the point shows up too close to one of the lines in your sketch, find the equation for the line in slope-intercept form and test the point for \<, \> or =. Seems like less work to me, and 100% reliable. \*\* 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. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 1:25pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/12 "2003-03-17T13:25:41Z")
> [@](#): > > \*Originally posted by Desmostylus \* > \*\*Note that it’s entirely possible for a quadrilateral to be concave, so you have to be careful about extending this method. \*\* It is also possible for a set of four coordinate pairs to produce not a quadrilateral, but a figure that looks like a pair of triangles joined at the vertices (sort of hourglass shaped). ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 1:54pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/13 "2003-03-17T13:54:04Z")
> [@](#): > > \*Originally posted by Mangetout \* > \*\*It is also possible for a set of four coordinate pairs to produce not a quadrilateral, but a figure that looks like a pair of triangles joined at the vertices (sort of hourglass shaped). \*\* No, that’s getting silly. You’re looking for interior points. If you’re going to say that five points could define a _pentagram_ rather than a _pentagon_, then there’s no solution to your question. What I said to **Achernar** about the possibility of concavity in a quadrilateral referred to an “arrowhead” or a “chevron” shape. Not an “hourglass” shape. Minimum circumfrence or minimum perimeter is the criterion. ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 17, 2003, 1:58pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/14 "2003-03-17T13:58:02Z")
> [@](#): > > \*Originally posted by Mangetout \* > \*\*It is also possible for a set of four coordinate pairs to produce not a quadrilateral, but a figure that looks like a pair of triangles joined at the vertices (sort of hourglass shaped). \*\* I don’t see how that’s possible, given that the shape you describe requires _five_ points. ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 2:01pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/15 "2003-03-17T14:01:32Z")
> [@](#): > > \*Originally posted by Desmostylus \* > **No, that’s getting silly. You’re looking for interior points. If you’re going to say that five points could define a _pentagram_ rather than a _pentagon_, then there’s no solution to your question.** That is rather a bold statement and I don’t feel that the question is a silly one; given a set of points and instructed to link them one to the next (and back to the start) in a given order, surely it _must_ be possible to detect closed polygons produced… ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 2:09pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/16 "2003-03-17T14:09:39Z")
> [@](#): > > \*Originally posted by Q.E.D. \* > \*\*I don’t see how that’s possible, given that the shape you describe requires _five_ points. \*\* No it doesn’t; the central point that appears as two linked vertices is not described - they are coincidental to the fact that two of the lines have crossed (like [this](http://www.eat-it.freeserve.co.uk/stuff/hourglass.gif)) ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 2:13pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/17 "2003-03-17T14:13:57Z")
OK. Given an _ordered_ set of n points, it’s possible to determine whether the area enclosed by the _polyline connecting those points_ includes a given point P. That wasn’t the OP. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [March 17, 2003, 2:17pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/18 "2003-03-17T14:17:11Z")
It might help, **Mange** , if you provided a few more details about the problem you’re trying to solve. ---
**Author:** ![Q.E.D](https://avatars.discourse-cdn.com/v4/letter/q/51bf81/32.png) [@Q.E.D](https://boards.straightdope.com/u/Q.E.D)\ **Post date:** [March 17, 2003, 2:23pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/19 "2003-03-17T14:23:21Z")
> [@](#): > > \*Originally posted by Mangetout \* > \*\*No it doesn’t; the central point that appears as two linked vertices is not described - they are coincidental to the fact that two of the lines have crossed (like [this](http://www.eat-it.freeserve.co.uk/stuff/hourglass.gif)) \*\* Ah, gotcha. But allowing lines to cross opens up a whole new can of worms, doesn’t it? ---
**Author:** ![Mangetout](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mangetout/32/19_2.png) [@Mangetout](https://boards.straightdope.com/u/Mangetout)\ **Post date:** [March 17, 2003, 2:28pm UTC](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960/20 "2003-03-17T14:28:13Z")
> [@](#): > > \*Originally posted by Desmostylus \* > \*\*It might help, **Mange** , if you provided a few more details about the problem you’re trying to solve. \*\* Nothing related to any specific project, just something that I have idly wondered about from time to time. I probably should have defined the question a little more clearly, sorry. [Next page](https://boards.straightdope.com/t/geometry-question-placing-a-point-within-a-figure/161960.md?page=2)