Prevent Overlap of Polygon onto itself

Question

I am creating a polygon using Google Maps V3 API. It starts off with a 4 sided polygon which is a square.

Problem: Now when a new point is added to the polygon, it is possible for the polygon to overlap itself in a weird shape instead of forming a pentagon. This is because the polygon is drawn in the order the points are added to the array. Is it possible to rearrange the polygon points so no 2 lines overlap each other?

Answer 1

I have successfully implemented Blazemonger's suggestion above, and it works for me.

Here was his novel suggestion:

Another approach, which seems simpler to me: If the new point is (a) NOT in the interior of the existing polygon and (b) creates an interior angle greater than 180 degrees, then it must be invalid. There are many existing algorithms for testing whether a point is in the interior of a polygon (stackoverflow.com/q/471962/901048) and measuring the interior angle is a matter of finding the difference between the arctangents of each slope

To determine if the point is in the polygon, I used the polygon.Contains function from Mike Williams' updated epoly.js, found here: http://www.geocodezip.com/scripts/v3_epoly.js.

If the point is not in the polygon (see above), we: 1.) Determine if the interior angle of the last two vectors is greater than 180 degrees. To do so we need to implement the below equation to find the angle of last two vectors of the polygon:

angleRadians = Math.acos((vx1 * vx2 + vy1 * vy2) / ( Math.sqrt( vx1*vx1 + vy1*vy1 ) * Math.sqrt( vx2*vx2 + vy2*vy2 ) ));

this is using the Dot product of the vectors.

But that does not take into account the 'winding direction', first you must get the cross product and, if the cross product is positive, it was a left turn, if negative--a right turn.

I have included my JS code here, as a gist: https://gist.github.com/3741816.

BTW, I'm a newbie here at StackOverflow -- it's been such a great resource to me thanks thanks to all who have contributed!

Answer 2

We can detect overlapping of two polygons.But i just code in js and then we can prevent overlapping of polygon by alert of errors.

1. Includes cdns of libraries.
2. Existing polygon are in polygons shapes in js variable or js array.(i.e)
3. Make new polygon.
4. Search second polygon to first polygon. Both polygon same so you can change them. These cdn of libraries you must use them.

https://maps.googleapis.com/maps/api/js?v=3 https://code.jquery.com/jquery-1.11.1.min.js https://bl.ocks.org/christophermanning/raw/4450188/javascript.util.min.js https://bl.ocks.org/christophermanning/raw/4450188/jsts.min.js https://cdnjs.cloudflare.com/ajax/libs/wicket/1.1.0/wicket.js https://cdnjs.cloudflare.com/ajax/libs/wicket/1.1.0/wicket-gmap3.js

          var values=[ new google.maps.LatLng(59.73858,10.24296), new 
           google.maps.LatLng(59.74879,10.26459), new 
           google.maps.LatLng(59.73858,10.28965), new 
           google.maps.LatLng(59.7192,10.28965), new 
           google.maps.LatLng(59.7192,10.24296), new 
           google.maps.LatLng(59.73858,10.24296)];
          var new_shape=[ new google.maps.LatLng(59.73858,10.24296), new 
           google.maps.LatLng(59.74879,10.26459), new 
           google.maps.LatLng(59.73858,10.28965), new 
            google.maps.LatLng(59.7192,10.28965), new 
            google.maps.LatLng(59.7192,10.24296), new 
            google.maps.LatLng(59.73858,10.24296)];


           var existing_polygon = new google.maps.Polygon({
                         paths: values,
                         strokeColor: #000000,
                         strokeOpacity: 0.8,
                         strokeWeight: 1.5,
                         fillColor: #ff0000,
                         fillOpacity: 0.35,
                           });

              var polygone_new_shape= new google.maps.Polygon({
                     paths: [new_shape],
                     strokeColor: '#000000',
                     strokeOpacity: 0.8,
                     strokeWeight: 1,
                     fillColor: '#00FF00',
                     fillOpacity: 0.35
                     });


         var wkt = UseWicketToGoFromGooglePolysToWKT(existing_polygon, polygone_new_shape);
         var result= UseJstsToTestForIntersection(wkt,wkt);
                if(result==true){
                   alert("Polygon are overlapping existing polygon");
                   }

       function UseWicketToGoFromGooglePolysToWKT(poly1, poly2) {

                 var wicket = new Wkt.Wkt();
                  wicket.fromObject(poly1);
                  var wkt1 = wicket.write();
                  wicket.fromObject(poly2);
                  var wkt2 = wicket.write();
                    return [wkt1, wkt2];
                  }
         function UseJstsToTestForIntersection(wkt1, wkt2) {

                  var wktReader = new jsts.io.WKTReader();
                  var geom1 = wktReader.read(wkt1);
                  var geom2 = wktReader.read(wkt2);
                  var result;
                 if (geom2.intersects(geom1)) {
                   result=true;
                  }else{
                  result=false;
                  }
                 return result;
                }