Talk:Point in polygon

From Wikipedia, the free encyclopedia

Contents 1 Old talk 2 Deleted 3 Algorithm 4 Hmm

[edit] Old talk

The algorithm given in this page is not correct.
For example, consider the unit square polygon and a test point (0.5,0.5). The algorithm will terminate with either L=0,R=2 or L=2,R=0 (depending on which way you order the vertices). So the algorithm will report that the point is not within the polygon. Clearly, this is wrong.

Not clearly -- if you take 'left' to mean that the x of the point is less than the x of the segment at the level of y. -- It will always be to the right of the left hand segment, and to the left of the right hand segment, so L=1 and R=1. Drf5n 22:09, 10 August 2006 (UTC)

I would suggest this algorithm be removed, and this article only give short list of different strategies for solving this problem. Say, a summary of the article "Point in Polygon Strategies" by Eric Haines : http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

It looks poorly transcribed from http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html Drf5n 21:47, 18 July 2006 (UTC)

I concur that the algorithm is not correct, but the above counterexample actually works. It's possible the algorithm was revised since the counterexample was written. Today, the algorithm gives the wrong answer if the point is inside a triangle with points (0,0), (10,0), and (10,10). For example, the point might be (9, 1). This terminates with l=0, r=1 which is an error condition, yet the polygon is closed and there were no rounding issues. I will be changing the main page to warn the unwary. Marc W. Abel 15:24, 4 August 2006 (UTC)

Are you sure it doesn't terminate properly with l=1 and r=1? The point (9,1) is to the left of the (10,0)-(10,10) segment, and to the right of the (0,0)-(10,10) segment. I don't think the test condition is clear. It might be best to think of this algorithm as drawing a line from (-infinity,y0) to (x0,y0) to (+infinity,y0) and counting the segments that cross the left hand ray (r) or the right hand ray (l). If you expect it to be a closed polygon, then whether or not either l or r is is odd or not tells you if it is in or out. The test requiring l and r to both be either even or both be odd is a weak sort of a test for the set of segments making up the polygon to be closed or not-- it tries two rays. But this algorithm doesn't test closedness well at all -- it completely ignores all the segments that don't intersect the horizontal line through x0. This algorithm is optimized for computational speed, rather than clarity. Drf5n 22:09, 10 August 2006 (UTC)

The algorithm is wrong. Removed. I will not go into details, since it was unreferenced anyway. `'mikka 05:13, 8 January 2007 (UTC)

The algorithm was actually almost good, although not precise (lacking an algorithmic explanation of the term 'point lies in the half plane to the left of a line segment'), and a bit superfluous (you don't need two counters, l and r — one of them would be enough). The only flaw I can see in it is an inconsistent output for points on the polygon's edge. --CiaPan 10:19, 21 June 2007 (UTC)

PS. You missed a reference when deleting the algorithm from the article. Corrected.

[edit] Deleted

The following recently added piece is deleted from "winding number" section

There are at least two ways to avoid trigonometric functions and make the winding-number method much more efficient. One is to replace the unit circle about the given point to which the arc-tangent function maps the direction of a vertex, by a unit square, so that a measure of direction can be computed as a simple function of the tangent of the line between the given point and the vertex. (The winding number then becomes a multiple of 4 rather than an even multiple of pi.)

Another way is to count transitions of the direction from the given point to the vertices past a particular arbitrarily chosen direction, with clockwise and counter-clockwise transitions given opposite signs. When the positive x axis of a cartesian coordinate system is chosen, a transition is easily detected as a change in sign of the y coordinate when the given point lies to the left of the side of the polygon. The sense of the sign change gives the sign of the transition; and the sign of a simple dot product determines the relative locations of the given point and the polygon side.

First, it si not referenced, second it is barely comprehensible despite good English. Third it is dubious (as the text stands). `'Mїkka 17:31, 11 July 2007 (UTC)

I do not understand what is "not comprehensible" in it. First method uses e.g. a simple rational function:

(I belive this or similar function has been described in 'Algorithms in C++' by Robert Sedgewick for the purpose of sorting points for convex hull computing.) This function is constant on any ray starting at (0,0), and its values are from -1 on the Y negative half-axis through 0 on X positive half-axis, 1 on positive Y, 2 on negative X up to 3 back on negative Y half-axis. This is similar to what atan() returns, except the range [-1,3) vs. [0,2π) and that atan() starts growing from X+ while f() starts from Y-. But these two differences do not matter in the winding algorithm. The only effective difference is that a full circle (angle), as accumulated from atan() outputs, is 2π while the full circle defined by f() is 4. Just think of f() as the angle measure in hundreds of grads, i.e. in right angles.

The other method is essentially the ray casting: it starts with selecting a ray (direction) from the given point and checks for segments intersecting the chosen ray.

IMHO there is nothing incomprehensible here. --CiaPan 22:16, 12 July 2007 (UTC)

See next section for an answer. `'Mїkka 00:43, 13 July 2007 (UTC)

[edit] Algorithm

Here is the algorithm, deleted by Mikka in this edit:

Let P = (x₀,y₀) be the point to be tested against a polygon specified by the ordered list of its vertices (and hence, edges).

• Set l := 0 and r := 0
• for each line segment L of the polygon do the following:
  • if the y-coordinate of one endpoint of L is less than y₀ and the other is greater than or equal to y₀, then:
    • if P lies in the half plane to the left of L, then set l := l + 1, else set r := r + 1 (*)
• if both l and r are odd, then P lies inside the polygon; if both l and r are even, then P lies outside the polygon; if one is even and the other is odd, then some error has occurred, e.g. a rounding error or the line segments do not form a closed path.

I'm quite convinced it is okay. Could any opponent prove their claim the algorithm is wrong? Please give a counterexample for it — ie. show the list of vertices and the point P (not on the polygon boundary) which make the routine to give wrong answer. Note that it's enough to compute one counter only, say l, because in ordinary cases (when rounding does not matter) either both r and l are even or both are odd. --CiaPan 21:31, 12 July 2007 (UTC)

First of all, have you ever heard about the rule WP:CITE? Second, don't you see the difference between how you wrote and how the deleted piece was written? Third, it is not my business to prove the algorithm is wrong; it is your business to provide the reference where it was published, right or wrong. Fourth, yes, I did notice that the second method is basically ray casting. And again, it would be a useful and interesting observation, if you can provide a reference. Fifth, just to make your life more difficult and to show that the disputed text is not so clear as you think, your f() is the function for a representation of the slope, not for the angle, required in the "angle summation method", so prepare to be surprized when you start summing its values.

Concluding, the article sucks, but to improve it one is not required to show how smart they are, but just get a decent book and make a decent summary (while staying away from plagiarism :-). `'Mїkka 00:43, 13 July 2007 (UTC)

I'm totally confused — can not understand, why you mix your comments to the algorithm you added and then deleted from the article and comments to IP 208.53.214.130 contribution Possibly because I'm only en-1 user (in my own classification.) Anyway I'll try to answer here, in the order.

1) No, I haven't. But I hope this is not the kind of crime one would punish by immediate decapitation.

• No it is not. But not getting the hint suggests that you don't need one. (Sorry, your joke just begged for it. I amy take it back if you feel offended) `'Míkka 20:14, 14 July 2007 (UTC)

2) Yes, I can see the difference. And – gee, what a SURPRISE! – that's the reason I wrote it. It would not make any sense to write my explanation if I thought there's no difference, would it?

• And that's the reason I deleted it. `'Míkka 20:14, 14 July 2007 (UTC)

3) You claim it wrong, and you deleted it. I am sure it is okay, that's why ask the question: what makes you think it's wrong? I want to see you argument, so I can either correct my thinking or, I hope, your thinking. In the latter case we could restore the algorithm to the article, thus making it better.

• Wikipedia is not exercise in thinking; it is an exercise in summarizing what other people, smarter than us, think. `'Míkka 20:14, 14 July 2007 (UTC)

3) (contd.) It is not my business to provide any source, as long as the information is obvious. For me it is obvious, so I do not see a need of sources. And you did not request a source, which would help to make the article better. Instead you deleted useful information, which made it worse. Even if anybody knows the source, there's nothing to be 'sourced' now. On the other hand I'm curious why you deleted information that is obviously true.

3) (contd.) Especially I don't feel responsible for giving sources as it was you, who added the algorithm to the article, not me. I just copied it here to make it clear what the Old talk above is about. (BTW, is it requred to provide the source of every information published in Wikipedia? If so, I will recommend line (mathematics) for speedy deletion, as it has no references to any source.)

• I did not "add" it, see edit summary. Just like you I "just copied", then used some brain and deleted. `'Míkka 20:04, 14 July 2007 (UTC)

4) Your arguments seem to me to reduce Wikipedia to the store of references instead of a set of information.

• Not exactly; see WP:Attribution, WP:CITE, WP:NOR. In wikipedia the only way to distinguish "information" from "bullshit" is providing references. `'Míkka 20:04, 14 July 2007 (UTC)

5) I have used it some time ago. No surprize occured, works same good as atan().

• Yes, it is as good as atan(). So what? `'Míkka 20:04, 14 July 2007 (UTC)

Concludig, still no essential reason to delete the algorithm. Both examples given in 'Old talk' above are false, and your deleted it just because it is too hard to you to verify it, and want to have a 'written proof' in some book, right? --CiaPan 16:57, 14 July 2007 (UTC)

Concluding, wikipedia is not a place for scientific discussions. I wasted all this time to repeatedly explain you that we don't write things off our head because we think it is "information". I will no longer continue this discussion. If I will have spare time, I will write a correct text following my own advice in the end of my previous reply. You may do the same, again, followng my advice: just take a good book. Or two. `'Míkka 20:04, 14 July 2007 (UTC)

[edit] Hmm

Ray casting algorithm

One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray (see the line article section) starting from the point intersects the edges of the polygon. If it is an even number of times, the point is outside, if odd, inside.

No explaination of WHY is given, just that it IS this way. Whilst using a diagram it may be vary obvious that an even number of intersections means it is outside the polygon, but from a text description I would say that it's rather cryptic.

ie: needs more diagrams. Poddster 06:49, 19 September 2007 (UTC)