On Wed, Sep 16, 2009 at 1:45 AM, rygoody
<rygoody@xxxxxxxxx> wrote:
But this right here
test = (y - y0)*(x1 - x0) - (x - x0)*(y1 - y0)
That's just the cross product of 2 vectors (which is the same as the dot product of the 2 vectors where one is rotated 90 degrees)
the first vector is the path from the start of the line segment to the text point ((x-x0), (y-y0)) and the second vector is the path from the start of the line segment to the end ((x1-x0), (y1 - y0))
the cross product of two 2d vectors (a,b) and (c,d) is a*d - b*c. You get that cause to rotate (c,d) 90 degrees results in (d, -c), and to dot product (a,b) with (d, -c) results in a*d + b*-c which is the same as a*d - b*c.
the cross product is interesting because it's sign tells you which side of one vector the other one is on, when they have the same origin (so basically would you make a left turn or a right turn from one vector to go in the direction of the other). you can see this in terms of the dot product of one vector rotated 90 degrees, cause the sign of the dot product tells you if 2 vectors go more in the same direction or more away from each other (or 0 for perpendicular), it's hard to explain why that's so, but if you draw pictures you'll get it
How is that working to produce per pixel collison detection when the
for loop is only going through the Lines list which only has 5 entries
of 2 lists (for a pentagon)
I would expect you would have to go through each pixel line and use a
linear equation to interpolate between the points, but you appear not
to be doing that.
How is that working?
the reason that loop works, is because all the line segments of
the polygon go in the same direction (i.e. clockwise or
counter-clockwise) and because your polygon is convex (it doesn't have
any pits in it's outside). Because of those 2 properties, it means that
all inside points in your polygon are on the same side (left or right)
of all of the line segments (so say the line segments go around
clockwise, then the inside of the polygon is always on the right side
of every polygon line segment - if your line segments went counter-clockwise, then the inside of the polygon is always on the left side of every polygon line segment)
So the loop is using the cross-product of the point relative to the edge against the direction of the edge to find out which "side" of the edge the point is on. If the point is on the inside-side of each edge, it must be inside the poly. If it's on the outside-side of any edge, it cannot be inside the poly.
Note if you wound your poly in the other direction, you'd have to check for the other sign
(i.e you'd check for test > 0 inside of test < 0)
also note that if your poly was not convex, the test would fail for some points.