В чем причина этой странной проблемы вычитания площади?

Question

Пока я кодировал алгоритм обнаружения столкновений, я столкнулся с этой проблемой.Это что-то странное, что находится за пределами моего понимания.

Проблема здесь заключается в , что, если в моем алгоритме, представленном в функции tryMove(), я добавляю potentialArea к moveLineArea и выполняю обнаружение изменений в spaceTestArea(который создается из moveLineArea) после вычитания областей, взятых всеми юнитами, у меня есть столкновение с юнитом, который даже близко не находится x=280,y=120, где движущаяся единица находится в x=1880,y=120, и она движется к x=1914,y=126.

Я хотел бы знать что может быть причиной этой проблемы и что делать, чтобы избежать ее в будущем.

Я должен сказать, что у меня естьвременное решение (tryMove2()), но, пожалуйста, не позволяйте этому влиять на ваше мышление, т. е. мне не нравится это решение, и я твердо верю, что первое решение (tryMove()) должно сработать, и я должен был забыть о чем-то.

Пожалуйста, смотрите ниже код, представляющий проблему.

import java.awt.Point;
import java.awt.Polygon;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.util.ArrayList;
import java.util.List;

/**
 * Test showing some unexpected and weird behaviour of area subtraction.
 * @author Konrad Borowiecki
 */
public class TestTryMove {
    private static final List<Point> unitCenterPoints = new ArrayList<Point>();
    static{
        unitCenterPoints.add(new Point(1720, 120));
        unitCenterPoints.add(new Point(1880, 120));
        unitCenterPoints.add(new Point(1800, 200));
        unitCenterPoints.add(new Point(1720, 280));
        unitCenterPoints.add(new Point(1880, 280));
        unitCenterPoints.add(new Point(120, 120));
        unitCenterPoints.add(new Point(280, 120));
        unitCenterPoints.add(new Point(200, 200));
        unitCenterPoints.add(new Point(120, 280));
        unitCenterPoints.add(new Point(280, 280));
        unitCenterPoints.add(new Point(120, 1720));
        unitCenterPoints.add(new Point(280, 1720));
        unitCenterPoints.add(new Point(200, 1800));
        unitCenterPoints.add(new Point(120, 1880));
        unitCenterPoints.add(new Point(280, 1880));
    }
    public static void main(String[] args) {
        int[] xpointsOK = new int[]{1876, 1884, 1918, 1910};//for Move OK
        int[] ypointsOK = new int[]{139, 101, 108, 146};//for Move OK
        Polygon lineOK = new Polygon(xpointsOK, ypointsOK, xpointsOK.length);

        int[] xpointsFAIL = new int[]{1877, 1883, 1917, 1911};//for problem no move
        int[] ypointsFAIL = new int[]{139, 101, 107, 145};//for problem no move
        Polygon lineFAIL = new Polygon(xpointsFAIL, ypointsFAIL, xpointsFAIL.length);

        Point endPointCPOK = new Point(1914, 127);//Move OK
        Point endPointCPFAIL = new Point(1914, 126);//problem no move
        //where in both cases it should be move OK              
        System.out.println("******TEST for method tryMove()******");            
        System.out.println("TEST 1: this will FAIL");
        System.out.println("Result="+tryMove(endPointCPFAIL, lineFAIL)); 
        System.out.println("\nTEST 2: this will be OK");
        System.out.println("Result="+tryMove(endPointCPOK, lineOK));


        System.out.println("******TEST for method tryMove2()******");   
        System.out.println("TEST 1: this will be OK");
        System.out.println("Result="+tryMove2(endPointCPFAIL, lineFAIL)); 
        System.out.println("\nTEST 2: this will be OK");
        System.out.println("Result="+tryMove2(endPointCPOK, lineOK));
    }
    /**
     * Tests if a unit represented by point of index 1 in the list of 
     * unitCenterPoints (i.e. [1880, 120]) can make a move to the given endPointCP.
     * (Please notice we are ignoring this unit in the algorithm 
     * i.e. if(i != movingUnitIndexInTheArray)).
     * @param endPointCP the point where the unit moves to.
     * @param line the line of the move of the thickness equal to units width (mod=40), 
     * drawn between the current unit's center point and the endPointCP, 
     * represented as a polygon object.
     * @return true if move possible; false otherwise. 
     */
    private static boolean tryMove(Point endPointCP, Polygon line){
        Area potentialArea = getArea(endPointCP);
        Area moveLineArea = new Area(line);
        moveLineArea.add(potentialArea);
        //this area is used for testing if nothing stays on the way of the move
        Area spaceTestArea = new Area(moveLineArea);
        //the index of the unit making the move in the unitCenterPoints list
        int movingUnitIndexInTheArray = 1;
        //we are subtracting from spaceTestArea all areas of units
        for(int i = 0; i < unitCenterPoints.size(); i++)
            if(i != movingUnitIndexInTheArray) {
                Point p = unitCenterPoints.get(i);
                Area uArea = getArea(p);
                spaceTestArea.subtract(uArea);
                //we have intersection then return false, we cannot make this move  
                if(spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)) {
                    System.out.println("No move --- a unit is on the way. "
                            + "Conflicting point is="+p +"; for i="+i);
                    return false;
                }
            }
        System.out.println("Move OK.");
        return true;
    }

    private static boolean tryMove2(Point endPointCP, Polygon line){
        Area potentialArea = getArea(endPointCP);
        Area moveLineArea = new Area(line);
        //test if unit can move to the new position
        Area potentialTestArea = new Area(potentialArea);
        //this area is used for testing if nothing stays on the way of the move
        Area spaceTestArea = new Area(moveLineArea);
        //the index of the unit making the move in the unitCenterPoints list
        int movingUnitIndexInTheArray = 1;
        //we are subtracting from spaceTestArea all areas of units
        for(int i = 0; i < unitCenterPoints.size(); i++)
            if(i != movingUnitIndexInTheArray) {
                Point p = unitCenterPoints.get(i);
                Area uArea = getArea(p);
                spaceTestArea.subtract(uArea);
                potentialTestArea.subtract(uArea);
                //we have intersection then return false, we cannot make this move  
                if(spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)
                        || potentialTestArea.isEmpty() || !potentialTestArea.equals(potentialArea)) {
                    System.out.println("No move --- a unit is on the way. "
                            + "Conflicting point is="+p +"; for i="+i);
                    return false;
                }
            }
        System.out.println("Move OK.");
        return true;
    }
    /**
     * Gets the area taken by a unit given the unit's center point.
     * @param p the center point of a unit.
     * @return circle area.
     */ 
    private static Area getArea(Point p) {
        int mod = 40;//this is width and height of a unit
        Ellipse2D circle = new Ellipse2D.Double(p.x - mod / 2, p.y - mod / 2, mod, mod);
        return new Area(circle);
    }
}

И это вывод, который он производит:

******TEST for method tryMove()******
TEST 1: this will FAIL
No move --- a unit is on the way. Conflicting point is=java.awt.Point[x=280,y=120]; for i=6; where moving unit point is=java.awt.Point[x=1880,y=120]; the unit is moving to=java.awt.Point[x=1914,y=126]
Result=false

TEST 2: this will be OK
Move OK.
Result=true
******TEST for method tryMove2()******
TEST 1: this will be OK
Move OK.
Result=true

TEST 2: this will be OK
Move OK.
Result=true

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

Если требуется более подробное описание, я отвечуСРОЧНО.Заранее всем спасибо.

EDIT1: Как подсказал @trashgod, я попробовал и реализовал решение, использующее метод intersect().Мне не нравится, что для каждого теста вы должны создать новый объект.Можете ли вы предложить некоторую оптимизацию для этого алгоритма.

private static boolean tryMove3(Point endPointCP, Polygon line){
    Area potentialArea = getArea(endPointCP);
    Area moveLineArea = new Area(line);
    moveLineArea.add(potentialArea);
    //this area is used for testing if nothing stays on the way of the move
    //the index of the unit making the move in the unitCenterPoints list
    int movingUnitIndexInTheArray = 1;
    //we are subtracting from spaceTestArea all areas of units
    for(int i = 0; i < unitCenterPoints.size(); i++)
        if(i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            Area spaceTestArea = new Area(moveLineArea);
            spaceTestArea.intersect(uArea);
            //we have intersection then return false, we cannot make this move  
            if(!spaceTestArea.isEmpty()) {
                System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is="+p +"; for i="+i
                        + "; where moving unit point is="
                        +unitCenterPoints.get(movingUnitIndexInTheArray)
                        +"; the unit is moving to="+endPointCP
                        +"; spaceTestArea.isEmpty()="+spaceTestArea.isEmpty());
                return false;
            }
        }
    System.out.println("Move OK.");
    return true;
}

Answer 1

Полагаю, вы сталкиваетесь с одним из способов, которыми java.awt.geom.Area может стать пустым.Если это поможет, я сделал снимок ниже.В качестве альтернативы, вы могли бы использовать createTransformedShape() и contains()?

Приложение: tryMove3() выглядит правильно.Если профиль действительно хуже, я вижу несколько возможностей:

• Кэш любой статический Area, возможно, связанный с каждой центральной точкой.

• Выполните грубую проверку окрестности на основе getBounds() или квадри и пропустите удаленные пары.

JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.add(new JPanel(){

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        g2d.scale(10, 10);
        g2d.translate(-1875, -100);
        g2d.setColor(Color.green);
        g2d.draw(lineOK);
        g2d.setColor(Color.green.darker());
        g2d.drawRect(endPointCPOK.x, endPointCPOK.y, 1, 1);
        g2d.setColor(Color.red);
        g2d.draw(lineFAIL);
        g2d.setColor(Color.red.darker());
        g2d.drawRect(endPointCPFAIL.x, endPointCPFAIL.y, 1, 1);
    }
});
f.pack();
f.setSize(450, 500);
f.setLocationRelativeTo(null);
f.setVisible(true);

Answer 2

Каким-то образом 6-е вычитание меняет геометрию spaceTestArea, так что она не равна moveLineArea, и это можно увидеть визуально, используя exlusiveOr'ing of two.API области сообщает только то, что равно тестам, если две геометрии равны, но, к сожалению, не вдаваться в подробности.Например, если вы добавите отладочный код в вашу программу, вы увидите, что эта область exclusiveOr появляется только в 6-м вычитании.Я еще не понял, почему, но, возможно, если вы создадите образ эксклюзивного изображения, которое вы увидите.

Ваш код с моими операторами отладки (некоторые излишни, извините):

import java.awt.*;
import java.awt.geom.*;
import java.util.ArrayList;
import java.util.Formatter;
import java.util.List;

public class TestTryMove {
   private static final List<Point> unitCenterPoints = new ArrayList<Point>();
   static {
      unitCenterPoints.add(new Point(1720, 120));
      unitCenterPoints.add(new Point(1880, 120));
      unitCenterPoints.add(new Point(1800, 200));
      unitCenterPoints.add(new Point(1720, 280));
      unitCenterPoints.add(new Point(1880, 280));
      unitCenterPoints.add(new Point(120, 120));
      unitCenterPoints.add(new Point(280, 120));
      unitCenterPoints.add(new Point(200, 200));
      unitCenterPoints.add(new Point(120, 280));
      unitCenterPoints.add(new Point(280, 280));
      unitCenterPoints.add(new Point(120, 1720));
      unitCenterPoints.add(new Point(280, 1720));
      unitCenterPoints.add(new Point(200, 1800));
      unitCenterPoints.add(new Point(120, 1880));
      unitCenterPoints.add(new Point(280, 1880));
   }

   public static void main(String[] args) {
      int[] xpointsOK = new int[]{1876, 1884, 1918, 1910};// for Move OK
      int[] ypointsOK = new int[]{139, 101, 108, 146};// for Move OK
      Polygon lineOK = new Polygon(xpointsOK, ypointsOK, xpointsOK.length);

      int[] xpointsFAIL = new int[]{1877, 1883, 1917, 1911};// for problem no
                                                            // move
      int[] ypointsFAIL = new int[]{139, 101, 107, 145};// for problem no move
      Polygon lineFAIL = new Polygon(xpointsFAIL, ypointsFAIL,
               xpointsFAIL.length);

      Point endPointCPOK = new Point(1914, 127);// Move OK
      Point endPointCPFAIL = new Point(1914, 126);// problem no move
      // where in both cases it should be move OK
      System.out.println("******TEST for method tryMove()******");
      System.out.println("TEST 1: this will FAIL");
      System.out.println("Result=" + tryMove(endPointCPFAIL, lineFAIL));
      System.out.println("\nTEST 2: this will be OK");
      System.out.println("Result=" + tryMove(endPointCPOK, lineOK));

      System.out.println("******TEST for method tryMove2()******");
      System.out.println("TEST 1: this will be OK");
      System.out.println("Result=" + tryMove2(endPointCPFAIL, lineFAIL));
      System.out.println("\nTEST 2: this will be OK");
      System.out.println("Result=" + tryMove2(endPointCPOK, lineOK));
   }

   private static boolean tryMove(Point endPointCP, Polygon line) {
      Area potentialArea = getArea(endPointCP);
      Area moveLineArea = new Area(line);
      System.out.println(showBounds("moveLine before add", moveLineArea));
      moveLineArea.add(potentialArea);
      System.out.println(showBounds("moveLine after add ", moveLineArea));
      // this area is used for testing if nothing stays on the way of the move
      Area spaceTestArea = new Area(moveLineArea);
      System.out.println(showBounds("spaceTest", spaceTestArea));
      Area xOr = (Area)spaceTestArea.clone();
      xOr.exclusiveOr(moveLineArea);
      System.out.printf("Pre   %s  %s  %s%n", showBounds("STA", spaceTestArea), showBounds("MLA", moveLineArea), 
               showBounds("xOr", xOr)); 

      // the index of the unit making the move in the unitCenterPoints list
      int movingUnitIndexInTheArray = 1;
      // we are subtracting from spaceTestArea all areas of units
      for (int i = 0; i < unitCenterPoints.size(); i++) {
         if (i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            spaceTestArea.subtract(uArea);
            xOr = (Area)spaceTestArea.clone();
            xOr.exclusiveOr(moveLineArea);
            System.out.printf("i: %02d %s  %s  %s  %s%n", i, 
                     showBounds("STA", spaceTestArea), 
                     showBounds("MLA", moveLineArea), 
                     showBounds("uA", uArea),
                     showBounds("xOr", xOr));         
            // we have intersection then return false, we cannot make this move
            if (spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)) {
               System.out.println("spaceTestArea.isEmpty()? " + spaceTestArea.isEmpty());
               System.out.println("!spaceTestArea.equals(moveLineArea)? " + !spaceTestArea.equals(moveLineArea));
               System.out.println("moveLineArea bounds: " + moveLineArea.getBounds());
               System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is=" + p + "; for i=" + i);

               return false;
            }
         }
      }
      System.out.println("Move OK.");
      return true;
   }

   public static String showBounds(String name, Area area) {
      Rectangle rect = area.getBounds();
      StringBuilder resultSB = new StringBuilder();
      Formatter formatter = new Formatter(resultSB);
      formatter.format("%5s [%04d, %04d, %04d, %04d]", name, rect.x, rect.y, rect.width, rect.height);

      return resultSB.toString();
   }

   private static boolean tryMove2(Point endPointCP, Polygon line) {
      Area potentialArea = getArea(endPointCP);
      Area moveLineArea = new Area(line);
      // test if unit can move to the new position
      Area potentialTestArea = new Area(potentialArea);
      // this area is used for testing if nothing stays on the way of the move
      Area spaceTestArea = new Area(moveLineArea);
      // the index of the unit making the move in the unitCenterPoints list
      int movingUnitIndexInTheArray = 1;
      // we are subtracting from spaceTestArea all areas of units
      for (int i = 0; i < unitCenterPoints.size(); i++)
         if (i != movingUnitIndexInTheArray) {
            Point p = unitCenterPoints.get(i);
            Area uArea = getArea(p);
            spaceTestArea.subtract(uArea);
            potentialTestArea.subtract(uArea);
            // we have intersection then return false, we cannot make this move
            if (spaceTestArea.isEmpty() || !spaceTestArea.equals(moveLineArea)
                     || potentialTestArea.isEmpty()
                     || !potentialTestArea.equals(potentialArea)) {
               System.out.println("No move --- a unit is on the way. "
                        + "Conflicting point is=" + p + "; for i=" + i);
               return false;
            }
         }
      System.out.println("Move OK.");
      return true;
   }

   /**
    * Gets the area taken by a unit given the unit's center point.
    * 
    * @param p
    *           the center point of a unit.
    * @return circle area.
    */
   private static Area getArea(Point p) {
      int mod = 40;// this is width and height of a unit
      Ellipse2D circle = new Ellipse2D.Double(p.x - mod / 2, p.y - mod / 2,
               mod, mod);
      return new Area(circle);
   }
}