Changeset 3650 in josm for trunk/src/org/openstreetmap


Ignore:
Timestamp:
2010-11-06T18:52:29+01:00 (14 years ago)
Author:
bastiK
Message:

applied #5599 (patch by extropy) - Join areas speed improvement

Location:
trunk/src/org/openstreetmap/josm
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java

    r3636 r3650  
    4848import org.openstreetmap.josm.tools.Shortcut;
    4949
     50
    5051/**
    5152 * Join Areas (i.e. closed ways and multipolygons)
    … …  
    402403
    403404        //find intersection points
    404         ArrayList<Node> nodes = Geometry.addIntersections(allStartingWays, true, cmds);
     405        Set<Node> nodes = Geometry.addIntersections(allStartingWays, true, cmds);
    405406        return nodes.size() > 0;
    406407    }
    … …  
    438439
    439440        //find intersection points
    440         ArrayList<Node> nodes = Geometry.addIntersections(allStartingWays, false, cmds);
     441        Set<Node> nodes = Geometry.addIntersections(allStartingWays, false, cmds);
    441442
    442443        //no intersections, return.
    … …  
    474475        List<AssembledMultipolygon> preparedPolygons = findPolygons(bounadries);
    475476
     477
    476478        //assemble final polygons
    477479        List<Multipolygon> polygons = new ArrayList<Multipolygon>();
     480        Set<Relation> relationsToDelete = new LinkedHashSet<Relation>();
     481
    478482        for (AssembledMultipolygon pol : preparedPolygons) {
    479483
    … …  
    485489
    486490            //add back the original relations, merged with our new multipolygon relation
    487             fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation);
     491            fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation, relationsToDelete);
    488492
    489493            //strip tags from inner ways
    … …  
    495499
    496500        commitCommands(marktr("Assemble new polygons"));
     501
     502        for(Relation rel: relationsToDelete) {
     503            cmds.add(new DeleteCommand(rel));
     504        }
     505
     506        commitCommands(marktr("Delete relations"));
    497507
    498508        // Delete the discarded inner ways
    … …  
    828838     * @return list of split ways (or original ways if no splitting is done).
    829839     */
    830     private ArrayList<Way> splitWayOnNodes(Way way, Collection<Node> nodes) {
     840    private ArrayList<Way> splitWayOnNodes(Way way, Set<Node> nodes) {
    831841
    832842        ArrayList<Way> result = new ArrayList<Way>();
    … …  
    10951105    public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) {
    10961106        Set<Node> outsideNodes = new HashSet<Node>(outside.getNodes());
    1097 
    1098         for (Node insideNode : inside.getNodes()) {
     1107        List<Node> insideNodes = inside.getNodes();
     1108
     1109        for (Node insideNode : insideNodes) {
    10991110
    11001111            if (!outsideNodes.contains(insideNode))
    … …  
    13641375     * @param ArrayList<RelationRole> List of relations with roles the (original) ways were part of
    13651376     * @param Way The newly created outer area/way
    1366      */
    1367     private void fixRelations(ArrayList<RelationRole> rels, Way outer, RelationRole ownMultipol) {
     1377     * @param relationsToDelete - set of relations to delete.
     1378     */
     1379    private void fixRelations(ArrayList<RelationRole> rels, Way outer, RelationRole ownMultipol, Set<Relation> relationsToDelete) {
    13681380        ArrayList<RelationRole> multiouters = new ArrayList<RelationRole>();
    13691381
    … …  
    14101422                }
    14111423                // Delete old relation
    1412                 cmds.add(new DeleteCommand(r.rel));
     1424                relationsToDelete.add(r.rel);
    14131425            }
    14141426            newRel.addMember(new RelationMember("outer", outer));

  • trunk/src/org/openstreetmap/josm/actions/mapmode/ExtrudeAction.java

    r3634 r3650  
    4141import org.openstreetmap.josm.gui.layer.MapViewPaintable;
    4242import org.openstreetmap.josm.gui.layer.OsmDataLayer;
     43import org.openstreetmap.josm.tools.Geometry;
    4344import org.openstreetmap.josm.tools.ImageProvider;
    4445import org.openstreetmap.josm.tools.Shortcut;
    … …  
    306307                    //find if the new points overlap existing segments (in case of 90 degree angles)
    307308                    Node prevNode = getPreviousNode(selectedSegment.lowerIndex);
    308                     boolean nodeOverlapsSegment = prevNode != null && segmentsParralel(initialN1en, prevNode.getEastNorth(), initialN1en, newN1en);
     309                    boolean nodeOverlapsSegment = prevNode != null && Geometry.segmentsParralel(initialN1en, prevNode.getEastNorth(), initialN1en, newN1en);
    309310                    boolean hasOtherWays = this.hasNodeOtherWays(selectedSegment.getFirstNode(), selectedSegment.way);
    310311
    … …  
    323324                    //find if the new points overlap existing segments (in case of 90 degree angles)
    324325                    Node nextNode = getNextNode(selectedSegment.lowerIndex + 1);
    325                     nodeOverlapsSegment = nextNode != null && segmentsParralel(initialN2en, nextNode.getEastNorth(), initialN2en, newN2en);
     326                    nodeOverlapsSegment = nextNode != null && Geometry.segmentsParralel(initialN2en, nextNode.getEastNorth(), initialN2en, newN2en);
    326327                    hasOtherWays = hasNodeOtherWays(selectedSegment.getSecondNode(), selectedSegment.way);
    327328
    … …  
    387388    private static EastNorth calculateSegmentOffset(EastNorth segmentP1, EastNorth segmentP2, EastNorth moveDirection,
    388389            EastNorth targetPos) {
    389         EastNorth intersectionPoint = getLineLineIntersection(segmentP1, segmentP2, targetPos,
     390        EastNorth intersectionPoint = Geometry.getLineLineIntersection(segmentP1, segmentP2, targetPos,
    390391                new EastNorth(targetPos.getX() + moveDirection.getX(), targetPos.getY() + moveDirection.getY()));
    391392
    … …  
    395396            //return distance form base to target position
    396397            return new EastNorth(targetPos.getX() - intersectionPoint.getX(),
    397                         targetPos.getY() - intersectionPoint.getY());
    398     }
    399 
    400     /**
    401      * Finds the intersection of two lines of infinite length.
    402      * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
    403      */
    404     public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
    405         // Convert line from (point, point) form to ax+by=c
    406         double a1 = p2.getY() - p1.getY();
    407         double b1 = p1.getX() - p2.getX();
    408         double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
    409 
    410         double a2 = p4.getY() - p3.getY();
    411         double b2 = p3.getX() - p4.getX();
    412         double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
    413 
    414         // Solve the equations
    415         double det = a1 * b2 - a2 * b1;
    416         if (det == 0)
    417             return null; // Lines are parallel
    418 
    419         return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
    420     }
    421 
    422     private static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
    423 
    424         // Convert line from (point, point) form to ax+by=c
    425         double a1 = p2.getY() - p1.getY();
    426         double b1 = p1.getX() - p2.getX();
    427 
    428         double a2 = p4.getY() - p3.getY();
    429         double b2 = p3.getX() - p4.getX();
    430 
    431         // Solve the equations
    432         double det = a1 * b2 - a2 * b1;
    433         return Math.abs(det) < 1e-13;
    434     }
     398                    targetPos.getY() - intersectionPoint.getY());
     399    }
     400
    435401
    436402    /**

  • trunk/src/org/openstreetmap/josm/data/osm/NodePositionComparator.java

    r3636 r3650  
    1212    @Override
    1313    public int compare(Node n1, Node n2) {
     14
     15        if (n1.getCoor().equalsEpsilon(n2.getCoor()))
     16            return 0;
     17
    1418        double dLat = n1.getCoor().lat() - n2.getCoor().lat();
    1519        if (dLat > 0)

  • trunk/src/org/openstreetmap/josm/tools/Geometry.java

    r3636 r3650  
    55import java.util.ArrayList;
    66import java.util.Comparator;
     7import java.util.HashSet;
    78import java.util.LinkedHashSet;
    89import java.util.List;
    910import java.util.Set;
     11
    1012import org.openstreetmap.josm.Main;
    1113import org.openstreetmap.josm.command.AddCommand;
    … …  
    1315import org.openstreetmap.josm.command.Command;
    1416import org.openstreetmap.josm.data.coor.EastNorth;
    15 import org.openstreetmap.josm.data.coor.LatLon;
     17import org.openstreetmap.josm.data.osm.BBox;
    1618import org.openstreetmap.josm.data.osm.Node;
    1719import org.openstreetmap.josm.data.osm.NodePositionComparator;
    … …  
    2426 */
    2527public class Geometry {
     28    public enum PolygonIntersection {FIRST_INSIDE_SECOND, SECOND_INSIDE_FIRST, OUTSIDE, CROSSING}
     29
    2630    /**
    2731     * Will find all intersection and add nodes there for list of given ways. Handles self-intersections too.
    … …  
    3135     * Prerequisite: no two nodes have the same coordinates.
    3236     */
    33     public static ArrayList<Node> addIntersections(List<Way> ways, boolean test, List<Command> cmds) {
    34         //TODO: this is a bit slow - O( (number of nodes)^2 + numberOfIntersections * numberOfNodes )
     37    public static Set<Node> addIntersections(List<Way> ways, boolean test, List<Command> cmds) {
    3538
    3639        //stupid java, cannot instantiate array of generic classes..
    3740        @SuppressWarnings("unchecked")
    3841        ArrayList<Node>[] newNodes = new ArrayList[ways.size()];
     42        BBox[] wayBounds = new BBox[ways.size()];
    3943        boolean[] changedWays = new boolean[ways.size()];
    4044
    4145        Set<Node> intersectionNodes = new LinkedHashSet<Node>();
    4246
     47        //copy node arrays for local usage.
    4348        for (int pos = 0; pos < ways.size(); pos ++) {
    4449            newNodes[pos] = new ArrayList<Node>(ways.get(pos).getNodes());
     50            wayBounds[pos] = getNodesBounds(newNodes[pos]);
    4551            changedWays[pos] = false;
    4652        }
    4753
    48         //iterate over all segment pairs and introduce the intersections
    49 
     54        //iterate over all way pairs and introduce the intersections
    5055        Comparator<Node> coordsComparator = new NodePositionComparator();
    5156
    52         int seg1Way = 0;
    53         int seg1Pos = -1;
    54 
    55         while (true) {
    56             //advance to next segment
    57             seg1Pos++;
    58             if (seg1Pos > newNodes[seg1Way].size() - 2) {
    59                 seg1Way++;
    60                 seg1Pos = 0;
    61 
    62                 if (seg1Way == ways.size()) { //finished
    63                     break;
     57        WayLoop: for (int seg1Way = 0; seg1Way < ways.size(); seg1Way ++) {
     58            for (int seg2Way = seg1Way; seg2Way < ways.size(); seg2Way ++) {
     59
     60                //do not waste time on bounds that do not intersect
     61                if (!wayBounds[seg1Way].intersects(wayBounds[seg2Way])) {
     62                    continue;
    6463                }
    65             }
    66 
    67 
    68             //iterate over secondary segment
    69 
    70             int seg2Way = seg1Way;
    71             int seg2Pos = seg1Pos + 1;//skip the adjacent segment
    72 
    73             while (true) {
    74 
    75                 //advance to next segment
    76                 seg2Pos++;
    77                 if (seg2Pos > newNodes[seg2Way].size() - 2) {
    78                     seg2Way++;
    79                     seg2Pos = 0;
    80 
    81                     if (seg2Way == ways.size()) { //finished
    82                         break;
     64
     65                ArrayList<Node> way1Nodes = newNodes[seg1Way];
     66                ArrayList<Node> way2Nodes = newNodes[seg2Way];
     67
     68                //iterate over primary segmemt
     69                for (int seg1Pos = 0; seg1Pos + 1 < way1Nodes.size(); seg1Pos ++) {
     70
     71                    //iterate over secondary segment
     72                    int seg2Start = seg1Way != seg2Way ? 0: seg1Pos + 2;//skip the adjacent segment
     73
     74                    for (int seg2Pos = seg2Start; seg2Pos + 1< way2Nodes.size(); seg2Pos ++) {
     75
     76                        //need to get them again every time, because other segments may be changed
     77                        Node seg1Node1 = way1Nodes.get(seg1Pos);
     78                        Node seg1Node2 = way1Nodes.get(seg1Pos + 1);
     79                        Node seg2Node1 = way2Nodes.get(seg2Pos);
     80                        Node seg2Node2 = way2Nodes.get(seg2Pos + 1);
     81
     82                        int commonCount = 0;
     83                        //test if we have common nodes to add.
     84                        if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
     85                            commonCount ++;
     86
     87                            if (seg1Way == seg2Way &&
     88                                    seg1Pos == 0 &&
     89                                    seg2Pos == way2Nodes.size() -2) {
     90                                //do not add - this is first and last segment of the same way.
     91                            } else {
     92                                intersectionNodes.add(seg1Node1);
     93                            }
     94                        }
     95
     96                        if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
     97                            commonCount ++;
     98
     99                            intersectionNodes.add(seg1Node2);
     100                        }
     101
     102                        //no common nodes - find intersection
     103                        if (commonCount == 0) {
     104                            EastNorth intersection = getSegmentSegmentIntersection(
     105                                    seg1Node1.getEastNorth(), seg1Node2.getEastNorth(),
     106                                    seg2Node1.getEastNorth(), seg2Node2.getEastNorth());
     107
     108                            if (intersection != null) {
     109                                if (test) {
     110                                    intersectionNodes.add(seg2Node1);
     111                                    return intersectionNodes;
     112                                }
     113
     114                                Node newNode = new Node(Main.proj.eastNorth2latlon(intersection));
     115                                Node intNode = newNode;
     116                                boolean insertInSeg1 = false;
     117                                boolean insertInSeg2 = false;
     118
     119                                //find if the intersection point is at end point of one of the segments, if so use that point
     120
     121                                //segment 1
     122                                if (coordsComparator.compare(newNode, seg1Node1) == 0) {
     123                                    intNode = seg1Node1;
     124                                } else if (coordsComparator.compare(newNode, seg1Node2) == 0) {
     125                                    intNode = seg1Node2;
     126                                } else {
     127                                    insertInSeg1 = true;
     128                                }
     129
     130                                //segment 2
     131                                if (coordsComparator.compare(newNode, seg2Node1) == 0) {
     132                                    intNode = seg2Node1;
     133                                } else if (coordsComparator.compare(newNode, seg2Node2) == 0) {
     134                                    intNode = seg2Node2;
     135                                } else {
     136                                    insertInSeg2 = true;
     137                                }
     138
     139                                if (insertInSeg1) {
     140                                    way1Nodes.add(seg1Pos +1, intNode);
     141                                    changedWays[seg1Way] = true;
     142
     143                                    //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment.
     144                                    if (seg2Way == seg1Way) {
     145                                        seg2Pos ++;
     146                                    }
     147                                }
     148
     149                                if (insertInSeg2) {
     150                                    way2Nodes.add(seg2Pos +1, intNode);
     151                                    changedWays[seg2Way] = true;
     152
     153                                    //Do not need to compare again to already split segment
     154                                    seg2Pos ++;
     155                                }
     156
     157                                intersectionNodes.add(intNode);
     158
     159                                if (intNode == newNode) {
     160                                    cmds.add(new AddCommand(intNode));
     161                                }
     162                            }
     163                        }
     164                        else if (test && intersectionNodes.size() > 0)
     165                            return intersectionNodes;
    83166                    }
    84167                }
    85 
    86                 //need to get them again every time, because other segments may be changed
    87                 Node seg1Node1 = newNodes[seg1Way].get(seg1Pos);
    88                 Node seg1Node2 = newNodes[seg1Way].get(seg1Pos + 1);
    89                 Node seg2Node1 = newNodes[seg2Way].get(seg2Pos);
    90                 Node seg2Node2 = newNodes[seg2Way].get(seg2Pos + 1);
    91 
    92                 int commonCount = 0;
    93                 //test if we have common nodes to add.
    94                 if (seg1Node1 == seg2Node1 || seg1Node1 == seg2Node2) {
    95                     commonCount ++;
    96 
    97                     if (seg1Way == seg2Way &&
    98                             seg1Pos == 0 &&
    99                             seg2Pos == newNodes[seg2Way].size() -2) {
    100                         //do not add - this is first and last segment of the same way.
    101                     } else {
    102                         intersectionNodes.add(seg1Node1);
    103                     }
    104                 }
    105 
    106                 if (seg1Node2 == seg2Node1 || seg1Node2 == seg2Node2) {
    107                     commonCount ++;
    108 
    109                     intersectionNodes.add(seg1Node2);
    110                 }
    111 
    112                 //no common nodes - find intersection
    113                 if (commonCount == 0) {
    114                     LatLon intersection = getLineLineIntersection(
    115                             seg1Node1.getEastNorth().east(), seg1Node1.getEastNorth().north(),
    116                             seg1Node2.getEastNorth().east(), seg1Node2.getEastNorth().north(),
    117                             seg2Node1.getEastNorth().east(), seg2Node1.getEastNorth().north(),
    118                             seg2Node2.getEastNorth().east(), seg2Node2.getEastNorth().north());
    119 
    120                     if (intersection != null) {
    121                         if (test) {
    122                             intersectionNodes.add(seg2Node1);
    123                             return new ArrayList<Node>(intersectionNodes);
    124                         }
    125 
    126                         Node newNode = new Node(intersection);
    127                         Node intNode = newNode;
    128                         boolean insertInSeg1 = false;
    129                         boolean insertInSeg2 = false;
    130 
    131                         //find if the intersection point is at end point of one of the segments, if so use that point
    132 
    133                         //segment 1
    134                         if (coordsComparator.compare(newNode, seg1Node1) == 0) {
    135                             intNode = seg1Node1;
    136                         } else if (coordsComparator.compare(newNode, seg1Node2) == 0) {
    137                             intNode = seg1Node2;
    138                         } else {
    139                             insertInSeg1 = true;
    140                         }
    141 
    142                         //segment 2
    143                         if (coordsComparator.compare(newNode, seg2Node1) == 0) {
    144                             intNode = seg2Node1;
    145                         } else if (coordsComparator.compare(newNode, seg2Node2) == 0) {
    146                             intNode = seg2Node2;
    147                         } else {
    148                             insertInSeg2 = true;
    149                         }
    150 
    151                         if (insertInSeg1) {
    152                             newNodes[seg1Way].add(seg1Pos +1, intNode);
    153                             changedWays[seg1Way] = true;
    154 
    155                             //fix seg2 position, as indexes have changed, seg2Pos is always bigger than seg1Pos on the same segment.
    156                             if (seg2Way == seg1Way) {
    157                                 seg2Pos ++;
    158                             }
    159                         }
    160 
    161                         if (insertInSeg2) {
    162                             newNodes[seg2Way].add(seg2Pos +1, intNode);
    163                             changedWays[seg2Way] = true;
    164 
    165                             //Do not need to compare again to already split segment
    166                             seg2Pos ++;
    167                         }
    168 
    169                         intersectionNodes.add(intNode);
    170 
    171                         if (intNode == newNode) {
    172                             cmds.add(new AddCommand(intNode));
    173                         }
    174                     }
    175                 }
    176                 else if (test && intersectionNodes.size() > 0)
    177                     return new ArrayList<Node>(intersectionNodes);
    178             }
    179         }
     168            }
     169        }
     170
    180171
    181172        for (int pos = 0; pos < ways.size(); pos ++) {
    … …  
    191182        }
    192183
    193         return new ArrayList<Node>(intersectionNodes);
    194     }
    195 
    196     /**
    197      * Finds the intersection of two lines
    198      * @return LatLon null if no intersection was found, the LatLon coordinates of the intersection otherwise
    199      */
    200     static private LatLon getLineLineIntersection(
    201             double x1, double y1, double x2, double y2,
    202             double x3, double y3, double x4, double y4) {
    203 
    204         if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null;
    205 
    206         // Convert line from (point, point) form to ax+by=c
    207         double a1 = y2 - y1;
    208         double b1 = x1 - x2;
    209         double c1 = x2*y1 - x1*y2;
    210 
    211         double a2 = y4 - y3;
    212         double b2 = x3 - x4;
    213         double c2 = x4*y3 - x3*y4;
    214 
    215         // Solve the equations
    216         double det = a1*b2 - a2*b1;
    217         if (det == 0) return null; // Lines are parallel
    218 
    219         return Main.proj.eastNorth2latlon(new EastNorth(
    220                 (b1*c2 - b2*c1)/det,
    221                 (a2*c1 -a1*c2)/det
    222         ));
    223     }
    224    
     184        return intersectionNodes;
     185    }
     186
     187    private static BBox getNodesBounds(ArrayList<Node> nodes) {
     188
     189        BBox bounds = new BBox(nodes.get(0));
     190        for(Node n: nodes) {
     191            bounds.add(n.getCoor());
     192        }
     193        return bounds;
     194    }
     195
    225196    /**
    226197     * Tests if given point is to the right side of path consisting of 3 points.
    … …  
    259230
    260231    /**
     232     * Finds the intersection of two line segments
     233     * @return EastNorth null if no intersection was found, the EastNorth coordinates of the intersection otherwise
     234     */
     235    public static EastNorth getSegmentSegmentIntersection(
     236            EastNorth p1, EastNorth p2,
     237            EastNorth p3, EastNorth p4) {
     238        double x1 = p1.getX();
     239        double y1 = p1.getY();
     240        double x2 = p2.getX();
     241        double y2 = p2.getY();
     242        double x3 = p3.getX();
     243        double y3 = p3.getY();
     244        double x4 = p4.getX();
     245        double y4 = p4.getY();
     246
     247        //TODO: do this locally.
     248        if (!Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4)) return null;
     249
     250        // Convert line from (point, point) form to ax+by=c
     251        double a1 = y2 - y1;
     252        double b1 = x1 - x2;
     253        double c1 = x2*y1 - x1*y2;
     254
     255        double a2 = y4 - y3;
     256        double b2 = x3 - x4;
     257        double c2 = x4*y3 - x3*y4;
     258
     259        // Solve the equations
     260        double det = a1*b2 - a2*b1;
     261        if (det == 0) return null; // Lines are parallel
     262
     263        double x = (b1*c2 - b2*c1)/det;
     264        double y = (a2*c1 -a1*c2)/det;
     265
     266        return new EastNorth(x, y);
     267    }
     268
     269    /**
     270     * Finds the intersection of two lines of infinite length.
     271     * @return EastNorth null if no intersection was found, the coordinates of the intersection otherwise
     272     */
     273    public static EastNorth getLineLineIntersection(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
     274
     275        // Convert line from (point, point) form to ax+by=c
     276        double a1 = p2.getY() - p1.getY();
     277        double b1 = p1.getX() - p2.getX();
     278        double c1 = p2.getX() * p1.getY() - p1.getX() * p2.getY();
     279
     280        double a2 = p4.getY() - p3.getY();
     281        double b2 = p3.getX() - p4.getX();
     282        double c2 = p4.getX() * p3.getY() - p3.getX() * p4.getY();
     283
     284        // Solve the equations
     285        double det = a1 * b2 - a2 * b1;
     286        if (det == 0)
     287            return null; // Lines are parallel
     288
     289        return new EastNorth((b1 * c2 - b2 * c1) / det, (a2 * c1 - a1 * c2) / det);
     290    }
     291
     292    public static boolean segmentsParralel(EastNorth p1, EastNorth p2, EastNorth p3, EastNorth p4) {
     293        // Convert line from (point, point) form to ax+by=c
     294        double a1 = p2.getY() - p1.getY();
     295        double b1 = p1.getX() - p2.getX();
     296
     297        double a2 = p4.getY() - p3.getY();
     298        double b2 = p3.getX() - p4.getX();
     299
     300        // Solve the equations
     301        double det = a1 * b2 - a2 * b1;
     302        return Math.abs(det) < 1e-13;
     303    }
     304
     305    /**
     306     * Calculates closest point to a line segment.
     307     * @param segmentP1
     308     * @param segmentP2
     309     * @param point
     310     * @return segmentP1 if it is the closest point, segmentP2 if it is the closest point,
     311     * a new point if closest point is between segmentP1 and segmentP2.
     312     */
     313    public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point) {
     314
     315        double ldx = segmentP2.getX() - segmentP1.getX();
     316        double ldy = segmentP2.getY() - segmentP1.getY();
     317
     318        if (ldx == 0 && ldy == 0) //segment zero length
     319            return segmentP1;
     320
     321        double pdx = point.getX() - segmentP1.getX();
     322        double pdy = point.getY() - segmentP1.getY();
     323
     324        double offset = (pdx * ldx + pdy * ldy) / (ldx * ldx + ldy * ldy);
     325
     326        if (offset <= 0)
     327            return segmentP1;
     328        else if (offset >= 1)
     329            return segmentP2;
     330        else
     331            return new EastNorth(segmentP1.getX() + ldx * offset, segmentP1.getY() + ldy * offset);
     332    }
     333
     334    /**
     335     * This method tests if secondNode is clockwise to first node.
     336     * @param commonNode starting point for both vectors
     337     * @param firstNode first vector end node
     338     * @param secondNode second vector end node
     339     * @return true if first vector is clockwise before second vector.
     340     */
     341    public static boolean angleIsClockwise(EastNorth commonNode, EastNorth firstNode, EastNorth secondNode) {
     342        double dy1 = (firstNode.getY() - commonNode.getY());
     343        double dy2 = (secondNode.getY() - commonNode.getY());
     344        double dx1 = (firstNode.getX() - commonNode.getX());
     345        double dx2 = (secondNode.getX() - commonNode.getX());
     346
     347        return dy1 * dx2 - dx1 * dy2 > 0;
     348    }
     349
     350    /**
     351     * Tests if two polygons intersect.
     352     * @param first
     353     * @param second
     354     * @return intersection kind
     355     * TODO: test segments, not only points
     356     * TODO: is O(N*M), should use sweep for better performance.
     357     */
     358    public static PolygonIntersection polygonIntersection(List<Node> first, List<Node> second) {
     359        Set<Node> firstSet = new HashSet<Node>(first);
     360        Set<Node> secondSet = new HashSet<Node>(second);
     361
     362        int nodesInsideSecond = 0;
     363        int nodesOutsideSecond = 0;
     364        int nodesInsideFirst = 0;
     365        int nodesOutsideFirst = 0;
     366
     367        for (Node insideNode : first) {
     368            if (secondSet.contains(insideNode)) {
     369                continue;
     370                //ignore touching nodes.
     371            }
     372
     373            if (nodeInsidePolygon(insideNode, second)) {
     374                nodesInsideSecond ++;
     375            }
     376            else {
     377                nodesOutsideSecond ++;
     378            }
     379        }
     380
     381        for (Node insideNode : second) {
     382            if (firstSet.contains(insideNode)) {
     383                continue;
     384                //ignore touching nodes.
     385            }
     386
     387            if (nodeInsidePolygon(insideNode, first)) {
     388                nodesInsideFirst ++;
     389            }
     390            else {
     391                nodesOutsideFirst ++;
     392            }
     393        }
     394
     395        if (nodesInsideFirst == 0) {
     396            if (nodesInsideSecond == 0){
     397                if (nodesOutsideFirst + nodesInsideSecond > 0)
     398                    return PolygonIntersection.OUTSIDE;
     399                else
     400                    //all nodes common
     401                    return PolygonIntersection.CROSSING;
     402            } else
     403                return PolygonIntersection.FIRST_INSIDE_SECOND;
     404        }
     405        else
     406        {
     407            if (nodesInsideSecond == 0)
     408                return PolygonIntersection.SECOND_INSIDE_FIRST;
     409            else
     410                return PolygonIntersection.CROSSING;
     411        }
     412    }
     413
     414    /**
    261415     * Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
    262416     * @param polygonNodes list of nodes from polygon path.
    … …  
    265419     */
    266420    public static boolean nodeInsidePolygon(Node point, List<Node> polygonNodes) {
    267         if (polygonNodes.size() < 3)
     421        if (polygonNodes.size() < 2)
    268422            return false;
    269423
Note: See TracChangeset for help on using the changeset viewer.