Polygon Intersection with Java

I just figured out what was wrong. It wasn't even with the code I posted. After the asteroid, and ship updated I added the new x and y points by typing

shape.xpoints = xPoints; //xPoints is the array of x coords
shape.ypoints = yPoints; //yPoints is the array of y coords

I'm not still not sure why that did not work when I tried collisions, but it worked when I drew the polygon. I had to change those two lines to

shape = new Polygon(xPoints,yPoints,numVertexes);

I'm not certain exactly what "it does not work" means on your end, but it seems like the following should do what you are wanting:


One thing to note is the decrementing outer loop, from size() to 0. Anytime you are removing anything from a collection in a loop, you want to do it from the end to the beginning. If you loop from 0 to size(), size() will be changing and the element after the one you remove will shift into it's place, causing elements to be skipped. It can definitely causing some debugging headaches if you don't know to watch for that behavior.

The only other change I made was to remove the ship.contains(asteroid) check which seems redundant.

Edit: Oops, just noticed I didn't start loop from size()-1... fixed hehe

Quote:

Original post by lkdizzlel7 I just figured out what was wrong. It wasn't even with the code I posted. After the asteroid, and ship updated I added the new x and y points by typing shape.xpoints = xPoints; //xPoints is the array of x coords shape.ypoints = yPoints; //yPoints is the array of y coords I'm not still not sure why that did not work when I tried collisions, but it worked when I drew the polygon. I had to change those two lines to shape = new Polygon(xPoints,yPoints,numVertexes);

From the documentation for the Polygon class:

Quote:

http://java.sun.com/j2se/1.4.2/docs/api/java/awt/Polygon.html invalidate public void invalidate() Invalidates or flushes any internally-cached data that depends on the vertex coordinates of this Polygon. This method should be called after any direct manipulation of the coordinates in the xpoints or ypoints arrays to avoid inconsistent results from methods such as getBounds or contains that might cache data from earlier computations relating to the vertex coordinates.

Actually, looking over the documentation, this is a pretty poorly designed class. I really don't think these Sun engineers understand OO at all :(

But, let's still see how we can clean up the code you originally posted.

First, the remove() logic has problems. As soon as you remove() one Asteroid from the list, the 'loop' index will index the *next* Asteroid in the container. So consider what happens when you are going through each of the loop2-many points on one asteroid, and then find that you need to remove it. This doesn't end your loop, so you keep looping. Now when we test if we need to exit the loop, we see that there are still more points left before we hit the 'asteroids.get(loop).getShape()' for the next asteroid - but the loop counter didn't get reset to 0! So when an asteroid is removed, some of the vertices of the next asteroid in the vector won't get tested.

In general, it is a very bad idea to "just" remove elements from a container while you are iterating over it. You need to be careful, and consider your approach more carefully.

I am going to implement the approach taken by the C++ standard library algorithm 'std::remove_if'. (This also has an algorithmic performance advantage with some containers, including the Vector you are using.) It works like this: we track *two* positions in the list - one for the element we're currently looking at (which I call the "read head"), and one that is *just past* the set of elements that we *know will be kept* (which I call the "write head"). Then we proceed:

For each element that we see under the read head:  If we should keep this element:    Copy the element to the position under the write head.    Advance the write head.Finally, use the current position of the write head to trim the container,since elements at this position and beyond are "garbage".

(std::remove_if doesn't actually perform the last step, because it can't, due to the fact that it also "works" on plain old arrays, which are not resizable. Normally, C++ programmers follow up a call to std::remove_if() with a call to the .erase() member function of the container, assuming it was used on a container.)

This way, every kept element gets written exactly once, in sequence, so we know that the container will end up containing exactly what it should. There is also no way that the process of "keeping" elements could interfere with the read head, for the simple reason that the write head can move *at most* once each time the read head does - it lags behind. (Well, it can also sit at the same position - as it does to start off - but copying an element over itself is not an issue.)

The performance benefit that I mentioned comes from the fact that every time something is .remove()d from a Vector, all the elements following it have to be "shifted" over, because a Vector stores all its valid elements right next to each other (presumably in an underlying array) without any "holes".

In order to detect 'kept' elements, I will simply set a flag 'keep' to true for each element, and set it false if any of the tests say we should remove the element.



Step 2 is to clean up all those repeated access patterns. We can make a temporary, for example, to hold 'asteroids.get(read_head).getShape()'. I'll also do this with 'asteroids.size()', simply because we know that the number of asteroids won't change - at least, not until *after* we've "combed through" for the kept elements.

I'll also pick a slightly more conventional name for the loop counter ;)



Finally, I'll move the inner loops into their own function. This gives us a way to clarify the meaning of the code without using comments, by instead using a meaningful name for the function. It also will give us a way to reuse the basic "polygon intersection" algorithm, which is bound to be useful somewhere else some day. Also, using that function gives us a slightly nicer way to implement "early-out" logic (by simply returning from the function immediately), which is currently missing (you would need to add a 'break;' after each 'keep = false;', and that's a bit messy).