Wikipedia:Reference desk/Archives/Mathematics/2009 December 17

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Mathematics desk
< December 16 << Nov | December | Jan >> December 18 >
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 17[edit]

recognition of tangent plane for a function[edit]

let a function be f(x,y,z)i.e. a function in three variables . after calculating its partial derivative how can we draw a tangent plane when the differentiation is partial . i just want to know about its concept —Preceding unsigned comment added by (talk) 04:10, 17 December 2009 (UTC)

If is a smooth function in three variables, its tangent space at any point will be three-dimensional. The gradient of this function, may be used to determine the equation of the tangent space. The equation of the tangent space of f at is . Hope this helps (it might also help to visualize this in the case when f is a function of only two variables). --PST 04:58, 17 December 2009 (UTC)
As a one-dimensional analogue, note that if f is a smooth function in one variable; that is, if is smooth, the equation of the tangent line of f at is . --PST 05:03, 17 December 2009 (UTC)

...and one should add that that works only if the function is differentiable, not just as a function of each of the three variables separately, but as a function of the three variables jointly. That means if you take a directional derivative in any direction, it will agree with what you'd get for the tangent space. Michael Hardy (talk) 05:15, 17 December 2009 (UTC)

To PST: I suppose most of planes—at least all I can recall—are two-dimensional, not three-dimensional (although they usually are embedded in three-dimensional, or even more-dimensonal spaces). Smile eye.png CiaPan (talk) 07:17, 17 December 2009 (UTC)
You are right, of course Smile eye.png, but if f is a smooth function in three variables, a tangent space to its graph will not be a plane (contrary to what the OP suggested); rather it will be three-dimensional (a hyperplane, if you like). --PST 08:58, 17 December 2009 (UTC)
Unless the OP meant f(x,y,z)=0 (or some other constant), in which case you will have a plane. --Tango (talk) 21:28, 17 December 2009 (UTC)

Easiest way to decide if a point is within a polygon?[edit]

I am writing a computer program in BASIC (I'm neither a career programmer or a mathematician). I have polygons represented as lines. The lines consist of two x,y coordinates. What would be the easiest practical method to determine if a point x,y is within a polygon or not?

I have thought about extending a line vertically or horizontally from the point to see if it cuts two polygon-lines on either side. But this would give the wrong answer if the point was between two polygons rather than in one, or near a concave part of a polygon.

Sorry, referring me to a standard graphics library written in C or whatever would not help as I would not understand it and could not use it. Thanks (talk) 11:09, 17 December 2009 (UTC)

  • The easiest way is to calculate the winding number of the polygon around the point, by calculating then summing the angles subtended by each edge that the point. This works for a polygon of any complexity. --JohnBlackburne (talk) 11:50, 17 December 2009 (UTC)
I get the feeling, from your description of your representation, that you have several polygons, that are only represented as lines with an x and a y coordinate. What makes me suspect this is the statement that extending a vertical or horizontal line would not work if the point was between two polygons rather than in one. The computer will not automatically sort the lines into separate polygons. Therefore, whatever algorithm you chose, you'll need to somehow represent which polygon a given line belongs to, and to test a point against one polygon at a time. --NorwegianBlue talk 14:46, 17 December 2009 (UTC)
Correct, although you could have more easily deduced that from seeing that I wrote polygons rather than polygon. (talk) 19:59, 17 December 2009 (UTC)
If you have multiple polygons then doing a test multiple times, once for each polygon, will work. You can early out when your condition is satisfied. If you're doing this a lot with the same polygons you might save some time if you consolidate your polygons, merging e.g. overlapping ones. But this will only be beneficial if the results are still polygons, i.e. there are no holes, and at least some overlap, and is probably a lot of extra work. --JohnBlackburne (talk) 20:21, 17 December 2009 (UTC)
WP:WHAAOE: point in polygon. My understanding is that the "cast a horizontal (or vertical) ray" approach is the simplest to program. --Tardis (talk) 18:21, 17 December 2009 (UTC)
I didn't know about that page, which presents them both quite nicely. I'd still say the winding number is easier as it's just to a simple for loop. It may not be the most efficient but there are things you can do to deal with that: as well as what the article suggests you can be as careless as you want working out the angle, i.e. use whatever approximations and fast but inaccurate routines you know; even errors of ± 25% are acceptable. --JohnBlackburne (talk) 18:52, 17 December 2009 (UTC)

Can I check please if I've got it right about calculating the winding number? Do I calculate the angle subtended from the point to each line, then add them all up? Then I imagine I divide that by 360 degrees, which gives me a number. What is the significance of that number? Wont it be a similar number even if the point is inside or outside the polygon? (talk) 20:14, 17 December 2009 (UTC)

Is the central pentagon inside or outside the polygon?
I've only used the first approach you suggested, which happened to be the first example in the article Tardis linked to (and which works fine, as long as you check for the special cases, such as your line intersecting with a vertex). Nevertheless, whichever approach you use, I think you need to decide how to deal with self-intersecting polygons. Are the holes created in such circumstances, such as the pentagon within the pentagram in the figure to the right, inside or outside the polygon? --NorwegianBlue talk 21:00, 17 December 2009 (UTC)
Yes. Sum the angles and it should be either 0°, 360° or -360°. It can be plus or minus as you don't need to do anything to ensure it's a clockwise or anticlockwise winding - it doesn't matter. 0° means the point is outside the polygon, ±360° means it is inside. Your maths only needs to be accurate enough to tell these cases apart. Divide by 360° to get the winding number.
As for self intersecting polygons they are a very different problem: the winding number can be anything, e.g. zero or two, even "inside" such a shape, which makes "inside" a much less well defined property.--JohnBlackburne (talk) 21:32, 17 December 2009 (UTC)
How can you get a total of 0 degrees when the point is outside the polygon? The angles will all be positive, so it will not add up to zero. What am I missing please? (talk) 00:45, 18 December 2009 (UTC)
The angles are directed: you go around the polygon in one direction and count how far counterclockwise (say) the ray from the test point sweeps with each step. If it moves clockwise instead, you subtract. --Tardis (talk) 05:23, 18 December 2009 (UTC)
If you can arrange that the pairs of points for each particular polygon are such that they describe a cycle round the polygon when considered as directed arrows then the job can be one fairly easily by extending a line like you say. The extra trick is to check for each line cut which side of it the line from your point cuts it, ie to the left of the arrow or to the right. If the cuts all balance out you're outside any polygon. If there is more of one than the other you're inside a polygon. This is a varia nt of the cycle counting algorithm. You don't need to note which polygon each line belongs to. Dmcq (talk) 23:51, 17 December 2009 (UTC)
I am late on this discussion, but it is important to know if the poygons are convex or concave. Convex polygons are easy to work with. Concave polygons are difficult. -- kainaw 02:51, 18 December 2009 (UTC)
Both convex and concave polygons are handled perfectly well by these algorithms. If you know all your polygons are convex things are a little simpler, e.g. a raycast from the point in any direction will intersect the polygon exactly once if the point is inside it. But otherwise the approach is the same.--JohnBlackburne (talk) 09:26, 18 December 2009 (UTC)

The winding number W of the polygon (z0, z1, ... , zn−1, zn=z0) around the point z = x + iy may be computed by a simple formula involving complex numbers:

The principal branch of the logarithm is chosen. If W = 0 then the point z is outside the polygon (z0, z1, ... , zn−1). Note that W is undefined when z is on the border of the polygon. Bo Jacoby (talk) 04:36, 18 December 2009 (UTC).

That looks simpler but is of limited use when programming as you generally can't use complex numbers --JohnBlackburne (talk) 09:26, 18 December 2009 (UTC)
If you don't have any self intersections like that picture or count the centre as being outside then just counting how many lines you cross to get outis enough, for instance if you check a line going vertically see how many intersections you have with y > that of your point. If it is odd your point is inside. You don't even have to have a particular direction associated with the lines for this. Dmcq (talk) 10:48, 18 December 2009 (UTC)

John Blackburne: Several programming languages support complex numbers, but BASIC does not. The J (programming language) allows this short implementation of the winding number formula: W=.9&o.@(%&0j2p1)@(+/)@:^.@(% _1&|.) . To test if (0,0) is within the square ((1,0),(0,1),(-1,0),(0,-1)), type W 1 0j1 _1 0j_1 and get the result 1, indicating YES. To test if (4,0) is within the square, type W 1 0j1 _1 0j_1 - 4 and get the result 0, indicating NO. This is perhaps the the easiest practical method to determine if a point x,y is within a polygon or not. Bo Jacoby (talk) 01:47, 19 December 2009 (UTC).

Thanks. Can the winding number, or any other simple proceedure, be used to check that a) a polygon does not overlap itself, or b) that two different polygons do not overlap? edit: I suppose the answer is that at least two of the lines would cross. (talk) 12:04, 19 December 2009 (UTC)

In general no. The winding number is limited to 0 and [±]1 in and around standard polygons, so if you get a winding number of 2 you know it's a self-intersecting polygon. But there are also self-intersecting polygons with winding numbers of only 0 and 1. As for two polygons, the winding number is of little use there too. If you find a vertex of one inside the other then they intersect, but they can intersect without this ever happening. If your polygons are always convex you can look for a separating line, i.e. a line not in either which they lie on either side of. But in general checking edges in one against edges in the other is probably best.--JohnBlackburne (talk) 23:45, 19 December 2009 (UTC)

Thanks, slightly off-topic question - how could two polygons intersect without a vertex (I assume that means corner) of one within the other, assuming they are made of straight lines? (talk) 16:14, 20 December 2009 (UTC)

Think of a cross make of two long rectangles on top of each other. Dmcq (talk) 16:45, 20 December 2009 (UTC)

Are the slopes of and necessarily reciprocal?[edit]

I just noticed that as I was working through some problems in my precalculus book's section on inverse functions, it seemed to be the case for every example I tried. (talk) 13:12, 17 December 2009 (UTC)

Did you test non-linear functions ? Try with say ... Abecedare (talk) 13:26, 17 December 2009 (UTC)
Good point, thanks. I actually tried , but of course only at exactly the point where 2x and intersect, but I just looked at the graphs using Walter Zorn's online grapher now. feel dumb now. (talk) 13:44, 17 December 2009 (UTC)
Yes because if y = f(x) and x = f-1(y) then f'(x) is dy/dx and (f-1)'(y) is dx/dy. i.e. one fraction is the reciprocal of the other so provided they are calculated at the same (x, y) their numerical values are reciprocal too. That is a great simplification, i.e. I've left out all the detail and justification, but it's how I'd approach it if I wanted to show it formally. --JohnBlackburne (talk) 14:00, 17 December 2009 (UTC)

The slopes are indeed reciprocals of each other if you look at the corresponding points on the two graphs. For example, the slope of y = x^2 at x = 4 is 8, and the slope of x = Sqrt(y) at y = 16 is 1/8. One common source of confusion is that the slopes of perpendicular lines are negative reciprocals of each other; there is no contradiction because inverse functions are not the same ting as perpendicular lines. — Carl (CBM · talk) 14:03, 17 December 2009 (UTC)

Good point. I think it would be useful to clarify the two different interpretations of the question. In the following, we use and assume that the function and its inverse are differentiable over the range of interest.
  • Question 1: For , is for all . Answer: No.
  • Question 2: For , is for all . Answer: Yes.
The first result is easily proven by an counter-example. For the second question, see Inverse functions and differentiation. Abecedare (talk) 14:22, 17 December 2009 (UTC)

It may be easier if you simply turn the graph on its "side", instantly changing y from a function of x to x as a function of y. You will then notice that, where the slopes of both the function and its inverse are well defined, they *have* to be reciprocals of each other. The key tricky point there is "where defined." Where one slope goes to 0, or the function isn't 1-1, you can have troubles. RayTalk 21:12, 17 December 2009 (UTC)

Maybe a somewhat simpler way to say what Abecedare said above: if


are each other's reciprocals. One is x and the other is y. Michael Hardy (talk) 23:37, 17 December 2009 (UTC)

right? Rckrone (talk) 20:03, 19 December 2009 (UTC)