[OpenMap Users] RE: BasicGeometry.distanceToEdge doesn't handle SEG_CLOSE properly.

From: Lecomte, J-Francois <JFLecomte_at_rheinmetall.ca>
Date: Thu, 15 Mar 2012 19:54:00 +0000

Oups, classic : forgot the attachment... :-S

Sorry for spamming...


De : Lecomte, J-Francois
Envoy : 15 March 2012 15:47
: 'openmap-users_at_bbn.com'
Objet : BasicGeometry.distanceToEdge doesn't handle SEG_CLOSE properly.

The method distanceToEdge(int x, int y) in class BasicGeometry does not handle the SEG_CLOSE properly, here is a JUnit4 test to illustrate the problem:

public class BasicGeometryTest
{
    private static final float DELTA = 0.00001f;

    /**
     * Test method for {_at_link BasicGeometry#distanceToEdge(int, int)}.
     *
     * The shape tested looks like this:
     *
     * <pre>
     * |
     * | p2__p3
     * | | |
     * | |__|
     * | p1 p4
     * |__________________
     *
     * p1:(1, 1)
     * p2:(1, 3)
     * p3:(3, 3)
     * p4:(3, 1)
     * </pre>
     */
    _at_Test
    public void testDistanceToEdge()
    {
        final Polygon shape = new Polygon();
        shape.addPoint(1, 1);
        shape.addPoint(1, 3);
        shape.addPoint(3, 3);
        shape.addPoint(3, 1);

        final MyBasicGeometry geometry = new MyBasicGeometry(new GeneralPath(shape));


        // Test points on line
        assertEquals(0, geometry.distanceToEdge(1, 1), 0);
        assertEquals(0, geometry.distanceToEdge(1, 2), 0);
        assertEquals(0, geometry.distanceToEdge(1, 3), 0);
        assertEquals(0, geometry.distanceToEdge(2, 1), 0); // Fails here but should not!
        assertEquals(0, geometry.distanceToEdge(2, 3), 0);
        assertEquals(0, geometry.distanceToEdge(3, 1), 0);
        assertEquals(0, geometry.distanceToEdge(3, 2), 0);
        assertEquals(0, geometry.distanceToEdge(3, 3), 0);

        // Test point inside
        assertEquals(1, geometry.distanceToEdge(2, 2), 0);

        // Test distance from the left
        assertEquals(Math.sqrt(2), geometry.distanceToEdge(0, 0), DELTA);
        assertEquals(1, geometry.distanceToEdge(0, 1), 0);
        assertEquals(1, geometry.distanceToEdge(0, 2), 0);
        assertEquals(1, geometry.distanceToEdge(0, 3), 0);
        assertEquals(Math.sqrt(2), geometry.distanceToEdge(0, 4), DELTA);

        // Test distance from the right
        assertEquals(Math.sqrt(2), geometry.distanceToEdge(4, 0), DELTA);
        assertEquals(1, geometry.distanceToEdge(4, 1), 0);
        assertEquals(1, geometry.distanceToEdge(4, 2), 0);
        assertEquals(1, geometry.distanceToEdge(4, 3), 0);
        assertEquals(Math.sqrt(2), geometry.distanceToEdge(4, 4), DELTA);

        // Test distance from the bottom
        assertEquals(1, geometry.distanceToEdge(1, 0), 0);
        assertEquals(1, geometry.distanceToEdge(2, 0), 0);
        assertEquals(1, geometry.distanceToEdge(3, 0), 0);

        // Test distance from the top
        assertEquals(1, geometry.distanceToEdge(1, 4), 0);
        assertEquals(1, geometry.distanceToEdge(2, 4), 0);
        assertEquals(1, geometry.distanceToEdge(3, 4), 0);
    }

    private static class MyBasicGeometry extends OMGraphic
    {
        public MyBasicGeometry(final GeneralPath shape)
        {
            super.shape = shape;
            super.needToRegenerate = false;
        }

        _at_Override
        public boolean generate(final Projection proj)
        {
            return false; // Whatever, I'm not using it...
        }
    }
}

Here is an implementation of the method that fixes the problem:

        /**
         * Return the shortest distance from the edge of a shape to an XY-point.
         * <p>
         * Method taken and adapted from {_at_link BasicGeometry#distanceToEdge(int, int)}
         *
         * _at_param x X coordinate of the point.
         * _at_param y Y coordinate of the point.
         * _at_return float distance, in pixels, from graphic to the point. Returns
         * Float.POSITIVE_INFINITY if the graphic isn't ready (ungenerated).
         */
        _at_Override
        public float distanceToEdge(final int x, final int y)
        {
            float distance = Float.POSITIVE_INFINITY;

            if(getNeedToRegenerate() || shape == null)
            {
                return distance;
            }

            final PathIterator pi2 = shape.getPathIterator(null);
            final FlatteningPathIterator pathIt = new FlatteningPathIterator(pi2, .25);
            final double[] coords = new double[6];
            double endPntX = Double.NaN;
            double endPntY = Double.NaN;

            double lastMovedToPntX = Double.NaN;
            double lastMovedToPntY = Double.NaN;

            while(!pathIt.isDone())
            {
                final int type = pathIt.currentSegment(coords);

                if(type == PathIterator.SEG_LINETO)
                {
                    final double startPntX = endPntX;
                    final double startPntY = endPntY;
                    endPntX = coords[0];
                    endPntY = coords[1];

                    final float dist = (float) Line2D.ptSegDist(startPntX, startPntY, endPntX,
                        endPntY, x, y);

                    if(dist < distance)
                    {
                        distance = dist;
                    }
                }
                else if(type == PathIterator.SEG_MOVETO)
                {
                    endPntX = coords[0];
                    endPntY = coords[1];
                    lastMovedToPntX = coords[0];
                    lastMovedToPntY = coords[1];
                }
                else if(type == PathIterator.SEG_CLOSE)
                {
                    final double startPntX = lastMovedToPntX;
                    final double startPntY = lastMovedToPntY;
                    endPntX = coords[0];
                    endPntY = coords[1];

                    final float dist = (float) Line2D.ptSegDist(startPntX, startPntY, endPntX,
                        endPntY, x, y);

                    if(dist < distance)
                    {
                        distance = dist;
                    }
                }

                pathIt.next();
            }

            return distance;
        }


I joined as attachment a bunch of JUnit4 tests to validate this method.

Also, I suggest this method be moved as a static public method in a Shape Utility class so it can be used without a "BasicGeometry" object (the shape object obviously should be received as parameter).







--
[To unsubscribe to this list send an email to "majdart_at_bbn.com"
with the following text in the BODY of the message "unsubscribe openmap-users"]
Received on Thu Mar 15 2012 - 15:54:58 EDT

This archive was generated by hypermail 2.3.0 : Tue Mar 28 2017 - 23:25:10 EDT