Changeset 7792 in josm for trunk/src


Ignore:
Timestamp:
2014-12-11T22:39:52+01:00 (5 years ago)
Author:
bastiK
Message:

see #10286 - fix numerical rounding problems

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/tools/Geometry.java

    r7776 r7792  
    314314    /**
    315315     * Finds the intersection of two lines of infinite length.
     316     *
     317     * @param p1 first point on first line
     318     * @param p2 second point on first line
     319     * @param p3 first point on second line
     320     * @param p4 second point on second line
    316321     * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
    317322     * @throws IllegalArgumentException if a parameter is null or without valid coordinates
     
    323328        CheckParameterUtil.ensureValidCoordinates(p3, "p3");
    324329        CheckParameterUtil.ensureValidCoordinates(p4, "p4");
    325 
     330       
    326331        if (!p1.isValid()) throw new IllegalArgumentException();
     332
     333        // Basically, the formula from wikipedia is used:
     334        //  https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
     335        // However, large numbers lead to rounding errors (see #10286).
     336        // To avoid this, p1 is first substracted from each of the points:
     337        //  p1' = 0
     338        //  p2' = p2 - p1
     339        //  p3' = p3 - p1
     340        //  p4' = p4 - p1
     341        // In the end, p1 is added to the intersection point of segment p1'/p2'
     342        // and segment p3'/p4'.
    327343
    328344        // Convert line from (point, point) form to ax+by=c
    329345        double a1 = p2.getY() - p1.getY();
    330346        double b1 = p1.getX() - p2.getX();
    331         double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
     347        // double c1 = 0;
    332348
    333349        double a2 = p4.getY() - p3.getY();
    334350        double b2 = p3.getX() - p4.getX();
    335         double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
     351        double c2 = (p4.getX() - p1.getX()) * (p3.getY() - p1.getY()) - (p3.getX() - p1.getX()) * (p4.getY() - p1.getY());
    336352
    337353        // Solve the equations
     
    340356            return null; // Lines are parallel
    341357
    342         return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
     358        return new EastNorth(b1 * c2 / det + p1.getX(),  - a1 * c2 / det + p1.getY());
    343359    }
    344360
     
    717733            result -= 2 * Math.PI;
    718734        }
    719 
     735       
    720736        return result;
    721737    }
Note: See TracChangeset for help on using the changeset viewer.