Implementing Polygon2D in Java 2D

Question

I'm creating a 2D game in Java using the Java2D library for drawing, and I really need a float-precision Polygon object that I can use both to draw game objects and to do collision detection on them. Unfortunately, Java's Polygon object comes in int precision only, and there is no equivalent Polygon2D like there is with Rectangle and Rectangle2D. I've already done enough research to see that I have a few options, but none of them seem very good.

1. Use Path2D. According to a Java developer posting in this forum, the lack of Polygon2D was an oversight, but its suggested replacement is Path2D. Unfortunately, Path2D doesn't provide a way to access its individual vertices or edges, which I need in order to do collision detection (specifically I need to get a vector orthogonal to each edge).

2. Implement my own Polygon2D that implements the Shape interface so that I can still pass it to Graphics2D.draw(Shape). This looks like it would be pretty difficult. The Shape interface requires tricky-to-implement methods like contains(Rectangle2D) and getPathIterator(AffineTransform). For getPathIterator in particular, it seems that in order to implement it I'd need to return an object of type PathIterator, but there are no concrete implementations of the PathIterator interface available in the public AWT packages.

3. Wrap Path2D in an object that "remembers" the individual vertices and provides them to the client. This worked for me when I needed an Area that remembered its component shapes: I wrapped it in a CompoundShape class that implemented the Shape interface and forwarded all the Shape methods to Area's implementation of them, while keeping track of each Shape that was added to the Area in an ArrayList. The problem with this is that if I keep track of the individual vertices in two arrays of floats, there is no way to expose them to the user without the possibility of the user changing the vertices - and since that would happen by direct array access, the internal Path2D wouldn't get notified of the changes.

4. Copy Polygon.java. The actual source code of Java's Polygon class is available on grepcode.com, and I could simply replace the vertex-related ints with floats throughout to get a Polygon2D. Unfortunately, when I tried this, the line import sun.awt.geom.Crossings; threw a compiler error saying "The type Crossings is not accessible due to restriction on required library C:\Program Files\Java\jre7\lib\rt.jar." According to this question that happens because Sun's license agreement prevents you from replacing core Java classes with your own, but Polygon doesn't try to do that - it simply creates an object of type sun.awt.geom.Crossings, no replacing or extending happens, and I made sure to put my copy of Polygon in a package not called "java".

What's the best way to proceed with this? I'd appreciate either suggestions for how make one of these options work or an idea for another option that doesn't have the problems these encounter.

Solution 1

I would also recommend Path2D. GeneralPath is a legacy class; don't use it.

Path2D does provide access to the vertex values, albeit it a roundabout fashion. You need to use a PathIterator:

PathIterator pi = path.getPathIterator(null);
float[] value = new float[6];
float x = 0, y = 0;

while (!pi.isDone()) {
    int type = pi.currentSegment(values);
    if (type == PathIterator.SEG_LINETO) {
        x = values[0];
        y = values[1];
    }
    else if (type == PathIterator.SEG_CLOSE) {
        x = 0;
        y = 0;
    }
    else {
        // SEG_MOVETO, SEG_QUADTO, SEG_CUBICTO
    }
    pi.next();
}

When you're ready to get fancy, you can expand that else to support the quadratic and cubic curves. I assume you don't need those at this time as you're talking about polygons.

Also, Path2D has some handy static methods for testing whether the path intersects a rectangle and whether the path contains a rectangle or point. Sadly, there are no methods for testing for a path intersecting or containing another path.

Solution 2

Perhaps have the internals of the polygon at a different scale?

Multiply by a large number and typecast to int when writing to it, divide by the same large number when reading?

Comments

[Stevens Miller]

I test for Path2D/Path2D intersection and containment by iterating over each segment of one path and, for each such segment, iterating over each segment of the other path. It's O(n^2), but I think that's unavoidable. For each two segments (one from each path), I test for intersection. If there is no intersection between any two segments, I test for a point from each path being contained inside the other. If both tests fail, neither path intersects, nor encloses, the other.