В чем причина этой странной проблемы вычитания площади?
Пока я кодировал алгоритм обнаружения столкновений, я столкнулся с этой проблемой. Это что-то странное, что находится за пределами моего понимания.
Проблема здесь в том, что если в моем алгоритме, представленном в функции 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 когда все в порядке.
Если нужно больше описания, я отвечу как можно скорее. Спасибо всем заранее.
РЕДАКТИРОВАТЬ1: Как предложил @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;
}
2 ответа
Решение
Я предполагаю, что вы сталкиваетесь с одним из способов java.awt.geom.Area может стать пустым. Если это поможет, я сделал снимок ниже. Или вы могли бы использовать createTransformedShape() а также contains()?
Приложение: tryMove3() кажется правильным. Если это действительно профили хуже, я вижу несколько возможностей:
Кешировать любой статический
Areaвозможно те, которые связаны с каждой центральной точкой.Сделайте грубую проверку окрестности на основе
getBounds()или quadtree и пропустить удаленные пары.
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);
Каким-то образом 6-е вычитание изменяет геометрию spaceTestArea, так что она не равна moveLineArea, и это можно увидеть визуально, используя exlusiveOr'ing of the two. API области утверждает только то, что равно тестам, если две геометрии равны, но, к сожалению, не вдаваться в подробности. Например, если вы добавите отладочный код в вашу программу, вы увидите, что эта область exclusiveOr появляется только в шестом вычитании. Я еще не понял, почему, но, возможно, если вы создадите образ эксклюзивного изображения, которое вы увидите.
Ваш код с моими операторами отладки (некоторые излишни, извините):
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);
}
}