Reputation: 15661

How to avoid overlapping polygon

I created a program to draw many polygons automatically everytimes user presses a button. The points of the polygon are generated automatically using the random function. The problem is that, since the points of the polygon were randomly generated, some of the polygon are overlap with other polygon. How can I avoid this, so that every polygon shown without being overlapped?

.....
List<Polygon> triangles = new LinkedList<Polygon>(); 
Random generator = new Random();

public void paintComponent(Graphics g) {

   for(int i = 0; i < 10; i++) {
      double xWidth = generator.nextDouble() * 40.0 + 10.0;
      double yHeight = generator.nextDouble() * 40.0 + 10.0;

      xCoord[0] = generator.nextInt(MAX_WIDTH);
      yCoord[0] = generator.nextInt(MAX_HEIGHT); 

      xCoord[1] = (int) (xCoord[0] - xWidth);
      xCoord[2] = (int) (xCoord[1] + (xWidth/2));       

      yCoord[1] = yCoord[0];
      yCoord[2] = (int) (yCoord[1] - yHeight);     

      triangles.add( new Polygon(xCoord,yCoord, 3));          
   }

   Graphics2D g2 = (Graphics2D) g;
   g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
   g2.setStroke(new BasicStroke(1)); 
   g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1.00f));
   g2.setPaint(Color.black);//set the polygon line 

   for (Polygon triangle : triangles)  g2.drawPolygon(triangle);

   Polygon[] triArray = triangles.toArray(new Polygon[triangles.size()]);
   for (Polygon p:triArray) triangles.remove (p);

}

Upvotes: 0

Answers (5)

Mahesh Kumar Prajapati

Reputation: 160

I have achieved this in Android Using Kotlin (See github project) by using JTS see here

Step-1: Add JTS library to your project

implementation group: 'org.locationtech.jts', name: 'jts-core', version: '1.15.0'

Step-2:

Create JTS polygon objects for both polygon

// create polygons One
        var polygoneOneArray: ArrayList<Coordinate> = ArrayList()
        for (points in polygonOnePointsList) {
            polygoneOneArray.add(Coordinate(points.latitude(), points.longitude()))
        }
        val polygonOne: org.locationtech.jts.geom.Polygon = GeometryFactory().createPolygon(
                polygoneOneArray.toTypedArray()
        )

// create polygons Two
        var polygoneTwoArray: ArrayList<Coordinate> = ArrayList()
        for (points in polygoneTwoPointsList) {
            polygoneTwoArray.add(Coordinate(points.latitude(), points.longitude()))
        }
        val polygonTwo: org.locationtech.jts.geom.Polygon = GeometryFactory().createPolygon(
                polygoneTwo.toTypedArray()
        )

Step-3:

Get Common Area of both Polygon

val intersection: org.locationtech.jts.geom.Geometry = polygonOne.intersection(polygonTwo)

Step-4:

Remove common Area from polygonTwo

 val difference: org.locationtech.jts.geom.Geometry = polygonTwo.difference(intersection)

Step-5:

Merge Both polygonOne and update polygonTwo

val union: org.locationtech.jts.geom.Geometry = mergePolygonList.get(0).polygons.union(difference)

Step-5:

Now pick points from Geometry and draw a final merged Polygon

   val array: ArrayList<Coordinate> = union.coordinates.toList() as ArrayList<Coordinate>
    val pointList: ArrayList<Point> = ArrayList()
    for (item in array) {
        pointList.add(Point.fromLngLat(item.y, item.x))
    }
    var list: ArrayList<List<Point>> = ArrayList<List<Point>>()
    list.add(pointList)
    style.addSource(
            GeoJsonSource(
                    "source-id${timeStamp}",
                    Feature.fromGeometry(Polygon.fromLngLats(list))
            )
    )

Upvotes: -1

Zed

Reputation: 57668

Create Area objects from your new polygon as well as for all existing polygons. Subtract the new polygon's area from the existing ones. If the subtract changed the area, the polygons overlap.

Area newArea = new Area(newPolygon);
Area existingArea = new Area(existingPolygon);
Area existingAreaSub = new Area(existingPolygon); existingAreaSub.subtract(newArea);
boolean intersects = existingAreaSub.equals(existingArea);

Upvotes: 1

akf

Reputation: 39495

You could break your canvas into 10 regions and constrain your polygons each to their own region. To do this, you could use your i value and a %100 (or other suitable magnitude) of your randomly generated value and apply them to your x coordinates and y coordinates as applicable. The result would be a grid of similarly constrained(no larger than the grid cell), but randomly shaped, Polygons.

EDIT:

Taking another look and fooling around a bit, I took the general concept as I described above and made a stab at an implementation:

public void paintComponent(Graphics g) {
    int[] xCoord = new int[3];
    int[] yCoord = new int[3];
    int colCnt = 5;
    int rowCnt = 2;
    int maxCellWidth = getWidth() / colCnt;
    int maxCellHeight = getHeight() / rowCnt;

    for (int i = 0; i < (colCnt * rowCnt); i++) {
        int xMultiple = i % colCnt;
        int yMultiple = i / colCnt;
        for (int j = 0; j < 3; j++) {
         xCoord[j] = generator.nextInt(maxCellWidth)
                   + (maxCellWidth * xMultiple);
             yCoord[j] = generator.nextInt(maxCellHeight)
                   + (maxCellHeight * yMultiple);
        }
        triangles.add(new Polygon(xCoord, yCoord, 3));
    }
    //... the rest of your method
}

As you can see, all of the Polygons have all points randomly generated, as opposed to your method of generating the first point and then making the rest relative to the first. There is a sense of randomness that is lost, however, as the Polygons are laid out in a grid-like pattern.

Upvotes: 1

tangens

Reputation: 39733

You could implement a method Polycon.containsPoint( x, y ) and repeat your random generation until this method returns false for all drawn Polygons.

Upvotes: 0

Mark P Neyer

Reputation: 1009

Check out the game programming wiki on Polygon Collision:

http://gpwiki.org/index.php/Polygon_Collision

Upvotes: 1

How to avoid overlapping polygon

Answers (5)

Related Questions