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

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

Заканчивать игре программирования вики на Polygon Столкновение:

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

Answer 2

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

Answer 3

Вы можете разбить свой холст на 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 4

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

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