Как избежать наложения многоугольника

Question

Я создал программу для автоматического рисования многих полигонов каждый раз, когда пользователь нажимает кнопку. Точки многоугольника генерируются автоматически с использованием случайной функции. Проблема в том, что, поскольку точки многоугольника были сгенерированы случайным образом, некоторые из многоугольников перекрываются с другими многоугольниками. Как можно этого избежать, чтобы каждый полигон показывался без наложения?

.....
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);

}

Answer 1

Создание объектов Area из вашего нового многоугольника, а также для всех существующих многоугольников. Вычтите площадь нового многоугольника из существующих. Если вычитание изменило область, полигоны перекрываются.

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

Answer 2

Вы можете разбить свой холст на 10 областей и ограничить каждый полигон своим собственным регионом. Для этого вы можете использовать ваше значение i и %100 (или другую подходящую величину) вашего случайно сгенерированного значения и применить их к вашим координатам x и y, в зависимости от ситуации. Результатом будет сетка с аналогичным ограничением (не больше ячейки сетки), но произвольной формы, полигонов.

EDIT:

Взглянув по-другому и немного дурачась, я взял общую концепцию, как описано выше, и сделал попытку реализации:

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
}

Как видите, все полигоны имеют все точки, сгенерированные случайным образом, в отличие от вашего метода генерации первой точки, а затем создания остальных точек относительно первой. Однако возникает ощущение случайности, поскольку полигоны расположены в виде сетки.

Answer 3

Ознакомьтесь с вики по программированию игр на Polygon Collision:

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

Answer 4

Вы можете реализовать метод Polycon.containsPoint( x, y ) и повторять случайную генерацию, пока этот метод не вернет false для всех нарисованных полигонов.