What is the reason of this weird area subtraction issue?
While I was coding an algorithm of collision detection I have come up at this problem. It is something weird which is beyond my understanding.
The problem here is that if in my algorithm, presented in function tryMove(), I add potentialArea to moveLineArea and I am doing detection of change in the spaceTestArea (which is created from the moveLineArea) after subtracting areas taken by all units, I have a collision with a unit that is not even close x=280,y=120, where moving unit is at x=1880,y=120, and it is moving to x=1914,y=126.
I would like to know what might be the reason of this issue and what to do in order to avoid it in future.
I must say I have a temporary solution (tryMove2()) but please do not let it influence your thinking, i.e. I do not like this solution and I strongly believe that the first solution (tryMove()) should work and it must be me who forgot about something.
Please see below the code presenting the problem.
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));
unitCenterPoin开发者_如何学JAVAts.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);
}
}
And this is the output it is producing:
******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
In order for you to see the problem better I have two images presenting it for two endPoints, first 1914, 126 when the method fails, and second 1914, 127 when it is OK.
If more description is needed I will answer ASAP. Thank you all in advance.
EDIT1:
As suggested by @trashgod I did tried and implemented a solution which uses intersect() method. I do not like that for every test you must create a new object. Can you suggest some optimization for this algorithm.
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;
}
I'm guessing you're running afoul of one of the ways java.awt.geom.Area can become empty. If it helps, I took a picture, below. Alternatively, could you use createTransformedShape() and contains()?
Addendum: tryMove3() appears correct. If it really profiles worse, I see several possibilities:
Cache any static
Area, perhaps those associated with each center point.Do a rough vicinity check based on
getBounds()or a quadtree and skip remote pairs.
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);
Somehow the 6th subtraction is changing the geometry of spaceTestArea so that it is not equal to moveLineArea and this may be seen visually by exlusiveOr'ing the two. The Area API states only that equals tests if the two geometries are equal but unfortunately doesn't go into further detail. For instance if you add debug code to your program, you'll see that this exclusiveOr area only pops up in the 6th subtraction. I've not yet figured out why, but perhaps if you create an image of the excluxiveOr image you'll see.
Your code with my debug statements (some a bit redundant, sorry):
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);
}
}
加载中,请稍侯......
精彩评论