Wikipedia:Reference desk/Archives/Mathematics/2006 December 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 6

Is a point inside a given triangle?

The problem above on the probability of an arbitrary shape balancing on 3 random-chosen points hinged on whether the triangle of the points included the shape's centroid. Which made me wonder - is there a simple test to determine whether or not the point (x,y) is within the triangle formed by the points (x1,y1), (x2,y2) and (x3,y3)?86.132.238.194 00:21, 6 December 2006 (UTC)

There are lots of tests, and we probably ought to have a article on the problem, but it appears that we don't... this is a good idea for computer work, although it could be optimized further. Does that count as simple? Melchoir 00:39, 6 December 2006 (UTC)

The probability of a point being inside a triangle is surely just area of a triangle / total area (assuming there's equal probability of the point happening in the "total area". --h2g2bob 00:56, 6 December 2006 (UTC)

Right, but does that help? The original question has a fixed centroid whereas all three vertices of the triangle are chosen at random, so its area varies. Melchoir 01:15, 6 December 2006 (UTC)

He wasn't talking about the probability...83.100.138.168 09:32, 6 December 2006 (UTC)

I had a look at your test "Melchoir" and it looks right - check to see if a point is on the same side of line AB (of triangle ABC) as point C, repeat for AC and BC , if all three are true the answer is yes...(it's also the simplest and quickest way as well)

The other possibilty is to express point (x,y) as (x1,y1)+n(x2-x1,y2-y1)+m(x3-x1,y3-y1) ie express point (x,y) as point A plus n times vector AB plus m times vector AC. n and m are obtained by solving the above equation separately for the x terms and the y terms (two linear equations with two unknowns). For the point to be in the triangle n>0 and m>0 and n+m<1

(x1,y1)+n(x2-x1,y2-y1)+m(x3-x1,y3-y1)=(x,y)

Giving x1+n(x2-x1)+m(x3-x1)=x and y1+n(y2-y1)+m(y3-y1)=y solve these for n and m.

eg solving for n by eliminating m m=[y-y1-n(y2-y1)]/(y3-y1) from second equation (could use either)

putting this into first equation x1+n(x2-x1)+(x3-x1)[(y-y1)-n(y2-y1)]/(y3-y1)=x

n[(x2-x1)(y3-y1)-(x3-x1)(y2-y1)]/(y3-y1) =[(x-x1)(y3-y1)-(x3-x1)(y-y1)]/(y3-y1)

n=[(x-x1)(y3-y1)-(x3-x1)(y-y1)]/[(x2-x1)(y3-y1)-(x3-x1)(y2-y1)] and m by a similar proceedure - note this method also can give the relative position inside the triangle but requires a little more computation. Probably no reason to expand all that for you. If you need more try a page or site on "ray tracing" these two equations pop up all the time in such places (usually the three dimensional form) 83.100.138.168 09:51, 6 December 2006 (UTC)

Note this is a reduced form of Line-plane intersection (equations in matrix form at this page).83.100.138.168 10:00, 6 December 2006 (UTC)

Question:can anyone give a third method - can anyone prove there is no third method??83.100.138.168 10:05, 6 December 2006 (UTC)

There are many ways to decide the point-in-triangle question, and the differences have practical implication for computational geometry and computer graphics. The article Point in Polygon Strategies discusses a number of alternatives (for a more general problem) in the context of computer graphics. Jonathan Shewchuk discusses robust primitives for use in computational geometry.

Here are a few alternatives:

1. Shoot a ray from the probe point to infinity in any direction; if it crosses an odd number of edges, the point is inside. (Hitting a vertex is not a problem if done properly.)
2. Perform a "left of" test for each edge; if all succeed, the point is inside.
3. Compute the barycentric coordinates of the probe point with respect to the triangle; if all are positive, the point is inside.
4. Compute the angle at the probe point for each edge segment; if the sum of the angles is 2π, the point is inside.
5. Compute the (unsigned) area formed by the probe point and a pair of triangle vertices; if the sum of the three areas equals the triangle area, the point is inside.

The first test is fast using a horizontal ray and common in computer graphics. The second test is robust and common in computational geometry. --KSmrq^T 16:57, 6 December 2006 (UTC)

Super Excellent - I never would have thought of those, especially the 'sum of angles' one. Thanks.87.102.6.143 17:38, 6 December 2006 (UTC)

I'm not sure about the "sum of the angles is 2π" test. Even if the point is outside the triangle, the sum of the three angles formed by drawing edge segments to each of the three points of the triangle will be 2π because the three angles form a complete circle around the point. However, I think (haven't proven) that a related test that might work would be that all three angles must be less than π. That's because if any one of the angles is greater than π, the picture would look like a cone emanating from the point in question, with all three edges leading from that point to the triangle, sort of like a flashlight shining on the triangle from the outside. (Not a mathematical argument, of course, but visually it makes sense). Dugwiki 20:45, 6 December 2006 (UTC)

I think KSmrq is using interior angles, whereas your angles seem to be directed. Either family of methods ought to work. Melchoir 21:09, 6 December 2006 (UTC)

Ah, ok, that would explain it. Like you said, both methods are basically equivalent. Thanks. Dugwiki 21:18, 6 December 2006 (UTC)

Depending on the size of the triangle compared to the "pointable" zone, it might be a good idea to test if the point is inside the triangle's bounding box before using Melchior's test. yandman 15:38, 6 December 2006 (UTC)

Circle and parabola

Let's suppose we have a circle of radius R centered at (0, R), and a parabola with the vertex at the origin. Let's say, we wanted to find the area that is between the circle and the parabola. What's a good way to parameterize this question so that it's easily solved? If I recall correctly, this might be a Putnam problem. --HappyCamper 20:28, 6 December 2006 (UTC)

Hmm, I know I'm rusty, but what about having the parabola be $f(x)=kx^{2}$ and the circle be $g(x)=\sin({\frac {\pi x}{2r}})$? Then the area between the two would be $\int _{0}^{z}g(x)-f(x)\,dx$ where z is the non-zero point of intersection where f(z)=g(z)? The trick then is to find z.... Dugwiki 21:05, 6 December 2006 (UTC)

That's the correct general idea, but the details are wrong. If I'm not mistaken, any parabola tangent to a circle and then intersecting it elsewhere as well (which it must if the equation is to make sense) must lie inside the circle between the intersections, so we should consider $f(x)-g(x)$. But that's trivial: the real problem is that the $y(x)$ equation of (here, the lower half of) a circle (derived from $(x-h)^{2}+(y-k)^{2}=r^{2}$) is $y=k-{\sqrt {r^{2}-(x-h)^{2}}}$; in this case and in your notation, it's just $g(x)=R\left(1-{\sqrt {1-\left({\frac {x}{R}}\right)^{2}}}\right)$. As for finding z, note that $g(x)=f(x)=kx^{2}$ and you can rather quickly get a quadratic (in $x^{2}$) from the equation for g. Does that help? --Tardis 22:01, 6 December 2006 (UTC)

oops, I misread the problem. I was thinking the circle was centered at (r,0), which is why I had g(x)-f(x). My bad. Dugwiki 22:08, 6 December 2006 (UTC)

Do you mean the parabola described by y=k·x² with k>0, and the area which is above the parabola and below the circle arc? If so, then just draw a chord between intersection points. Then calculate two areas, between the chord and each curve, and sum them to get an answer. --CiaPan 07:07, 7 December 2006 (UTC)

For fun, let's try thinking "outside the box". Let's assume that we have "arms right": x = λy², λ > 0. Then the upper arm must pass through the circle. However, we still have two plausible meanings for "between" from the two areas of the split circle. Fortunately, if we can find one, the other is easily determined as well. We know the parabola intersects the circle at the origin, (0,0). It also intersects at one other point, a joint solution of x−λy² = 0 and x²+(y−R)²−R² = 0. Scale the geometry so that R is 1, which also scales λ; the circle becomes x²+(y−1)²−1 = 0. Unfortunately, even with the simplification we find that the y intersection value is a root of λ²y³+y−2, which does not give a pretty answer. And as we all learn early, set problems have pretty answers. (Not so for real problems!) Apparently we have chosen the wrong geometry.

So let's rotate, and be more specific. A parabola of the form y = κx², κ > 0, can completely contain the circle if κ is large enough; or it can give an uncertain meaning for the area if κ is small enough so that the arms intersect the circle symmetrically. Again fix R at 1 and adjust κ as needed; in fact, use y = ¹⁄₂κx² so that κ > 1 will keep the arms in. Also demand the answer be the portion of the circle area within the arms of the parabola.

We can easily substitute for y in the circle equation to get a quadratic in x², and so find that the intersections are at

$x_{*}=\pm {\frac {2}{\kappa }}{\sqrt {\kappa -1}},\qquad y_{*}={\frac {2}{\kappa }}(\kappa -1).$

This is pretty enough to suggest we've chosen the intended geometry. Now we are asked for a good parameterization. Frankly, we don't need one. Instead of splitting with a chord, as CiaPan suggests, let's split with a sector from the circle center. And given the bilateral symmetry, restrict attention to the right half. Since we have reduced to a unit circle, the area of the sector is merely the angle between the intersection and the vertical,

$A_{\mathrm {sector} }=\arccos(y_{*}-1).\,\!$

Finding the area of the parabola below the sector is now little challenge; we want

$A_{\mathrm {parab} }=\int _{0}^{x_{*}}\left(1+{\frac {y_{*}-1}{x_{*}}}x\right)-{\frac {\kappa }{2}}x^{2}\,dx.$

Finally, we sum the two, double the area, and convert the results to use the original R and κ.

Two cautions should be observed. First, the sought area may be that below the parabola; in that case, subtract our result from πR². Second, unless (our reduced) κ is exactly 2, the circle bulges laterally beyond the intersection points; we include the extra area, which may be unwanted. --KSmrq^T 14:45, 7 December 2006 (UTC)

I really appreciate the responses people! Yes, I think my wording was ambiguous. Let me get back on this question...I think I might be able to dig this up. --HappyCamper 02:03, 8 December 2006 (UTC)

grades

This is a real example, but I've wondered about this for awhile.

The class syllabus says that 70% of my grade is made up of tests (including the final exam).

If I have a C+ in the class, and the average grade of my tests is a B+, what grade do I need on my final to bring my overall grade up? Would I need anything higher than a B+ or anything higher than a C+? In other words, would it be true to say that regardless of "tests" and "homework" categories being grouped together and weighted differently, if you recieve a grade anything higher than your current overall average then it brings your overall average up?

It seems like such an easy question, no wonder I'm doing so poorly :)

--froth^{T C} 21:24, 6 December 2006 (UTC)

A new grade, higher than the current average, will always raise the average, yes. But, by how much or how little is going to depend on the number of points involved. Average in this case would mean the total number of points you've gotten divided by the total number of possible points. So if you're currently at 700/1000 possible points, and you get a perfect score of 1/1 on a new assignment, the effect will be very small. See Arithmetic mean. Friday (talk) 21:30, 6 December 2006 (UTC)

Ah all right thanks friday --froth^{T C} 21:34, 6 December 2006 (UTC)

But if the tests are weighted as 70% of the total grade, as I suspect, then Friday's summary will not work. Friday's example is based upon the idea the grades are based upon a point system whereas, based on what you wrote, it seems more of a block system, with each part given a block of the total grade (i.e. homework is worth 10%, projects 20%, and tests 70%). Irrespective of how many tests are given, the total worth is 70% of the grade. As such, if the test average drops, then the total grade will drop. For example, let's say your current point total is 440/500, or 88%. Then, on the next test, you get a 80. Now your point total for tests is 520/600, or 86.67%. However, this grade has the same weight in your total - 70%. Thus, you're 88% would make up .88 x .70 = .616, or 61.6 of the points in your grade. And once your test average drops to 86.67, .8667 x .70 = .6069, or 60.69 of the points to your grade. As a result, both your test and grade average have dropped - your test average by 1.33%, and your overall grade by .931%. So, in order to raise your grade, you need to get higher than your current test average on your next exam.--AstoVidatu 01:25, 7 December 2006 (UTC)

The distinction you're making only makes a difference when computing grades in the middle of the term. In classes that I've taken and taught, when something like "Tests are 75% of the total grade, homework is 20%, and attendance is 5%" appeared in the syllabus, it meant: everything that gets graded is worth a certain number of points, and the total number of points for tests is 75% of the total number of points, etc. When computing averages midway through the semester (which I usually don't do), it's simply number of points achieved so far, divided by number of points possible so far. As long as the teacher grades this way (reports grades this way, really), then Friday's analysis is correct. Tesseran 02:33, 7 December 2006 (UTC)

Very well could be. And yeah, if that is true, then Sr. Viernes is, as you said, right. --71.235.243.114 04:23, 7 December 2006 (UTC)

You might be interested in the related Simpson's paradox. StuRat 13:55, 7 December 2006 (UTC)