Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  java.awt.Polygon.contains() is broken?  (Read 2189 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Posted 2010-12-24 01:44:28 »

For my Java4k game I'm representing countries in the world with Polygons. For some reason, random Polygon formations don't respond to contains() correctly, whereas 95% of the countries work just fine. It seems like maybe this is caused by polygons that are the farthest away from being convex, but I don't know if that's really the case.

Has anyone else had issues with this? I'm basically just trying to make countries clickable and I can't just use bounding boxes given the weird shape countries have.

I can take a screenshot if people want. At this point I just want to understand if there's just some weird error in my code, even though it's dead simple...

See my work:
OTC Software
Offline oNyx

JGO Coder


Medals: 2


pixels! :x


« Reply #1 - Posted 2010-12-24 02:13:50 »

Got a test case like...

bsh % Polygon p = new Polygon(new int[]{-1, 1, 1, -1}, new int[]{1, 1, -1, -1}, 4);
bsh % print(p.contains(0, 0));
true

? :>

弾幕 ☆ @mahonnaiseblog
Offline CommanderKeith
« Reply #2 - Posted 2010-12-24 02:14:32 »

Hi Eli,
Maybe the winding rule is causing trouble? The best one is PathIterator.WIND_EVEN_ODD.
Keith

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #3 - Posted 2010-12-24 08:51:56 »

I'd be very surprised if Polygon.contains turns out to be broken after all these years, so I'd guess it's something to do with your outline data: what is the source of the data? Have you checked for self-intersection/duplicate edges/other weirdness?
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #4 - Posted 2010-12-25 02:03:28 »

I'd be very surprised if Polygon.contains turns out to be broken after all these years, so I'd guess it's something to do with your outline data: what is the source of the data? Have you checked for self-intersection/duplicate edges/other weirdness?
It's generated by creating a polygon of n points and then dragging them around. What's weird is that when I moved one of them manually to a different location (which changes all the points via a delta), and it seemed clickable. I'm wondering if there's something wrong with my overlap priority. I'll do some more tests later.

See my work:
OTC Software
Online pjt33
« Reply #5 - Posted 2010-12-25 09:18:45 »

I'd be very surprised if Polygon.contains turns out to be broken after all these years, so I'd guess it's something to do with your outline data: what is the source of the data? Have you checked for self-intersection/duplicate edges/other weirdness?
It's generated by creating a polygon of n points and then dragging them around. What's weird is that when I moved one of them manually to a different location (which changes all the points via a delta), and it seemed clickable. I'm wondering if there's something wrong with my overlap priority. I'll do some more tests later.
Could you please produce a simple test case as Onyx suggested?
Offline gouessej
« Reply #6 - Posted 2010-12-25 09:37:16 »

Please give us some precise values causing this trouble.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2010-12-26 21:10:26 »

Here's the offending Polygon:

1  
2  
3  
4  
5  
6  
Polygon p = new Polygon
(
    new int[]{410,419,431,452,471,486,477,462,464,481,478,460,451,444,442,431,406,401,390,386,397,404,406},
    new int[]{118,102,95,91,105,117,128,121,134,140,185,228,237,237,222,211,187,170,170,154,144,137,129},
    23
);


That's in an 800x600 JPanel. The following points are all direct from mousePressed and look like they should be inside.

1  
2  
3  
4  
5  
6  
437 174
427 112
452 199
474 160
397 162
474 114


I'm about to try plugging those points into a hit test from scratch to see what happens.

See my work:
OTC Software
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #8 - Posted 2010-12-26 21:16:03 »

Well that settles it. Something in my "very simple" code is wrong. Check this out.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
import java.awt.Polygon;

public class PolyTest
{
   public static void main(String[] args)
   {
      Polygon p = new Polygon
      (
          new int[]{410,419,431,452,471,486,477,462,464,481,478,460,451,444,442,431,406,401,390,386,397,404,406},
          new int[]{118,102,95,91,105,117,128,121,134,140,185,228,237,237,222,211,187,170,170,154,144,137,129},
          23
      );
     
      System.out.println("437 174 " + p.contains(437, 174));
      System.out.println("427 112 " + p.contains(427, 112));
      System.out.println("452 199 " + p.contains(452, 199));
      System.out.println("474 160 " + p.contains(474, 160));
      System.out.println("397 162 " + p.contains(397, 162));
      System.out.println("474 114 " + p.contains(474, 114));
      System.out.println("999 999 " + p.contains(999, 999));
   }
}


Prints:
1  
2  
3  
4  
5  
6  
7  
437 174 true
427 112 true
452 199 true
474 160 true
397 162 true
474 114 true
999 999 false


There must be something wrong in my Z-sorting. EDIT - or not. It's Serializable's fault I think. Check this out:

In mousePressed, a loop goes through all the Country objects (just simple structs) and finds if any are clicked. It was telling me none were, and I knew the problem "country" was Scandinavia so I basically added in a check in order to print out just info from Scandinavia. Interestingly enough, it cycles through that country just fine, and even further its coordinates are all normal. What's doubly wacky is that if I make a copy of that Polygon right within that function, the copy contains the mouse click but the original does not. My conclusion is that it got saved to the disk in some crapped out fashion. So I'll try not using ObjectOutputStream and see what happens.

Here's the code, it's pretty simple. I search backwards so that the last drawn item (the item on top) is what is clicked. You can see I added in that test if statement, and I make a new Polygon and all that right there. The regular code is the if statement just below - dead simple.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
for (int i = countries.size()-1; i >= 0; i--)
{
   if (countries.get(i).name.equals("Scandinavia"))
   {
      System.out.println("In Scandi " + e.getX() + " " + e.getY());
      System.out.print("new Polygon(new int[]{");
      int[] xs = new int[countries.get(i).polygon.npoints];
      int[] ys = new int[xs.length];
      for (int j = 0; j < countries.get(i).polygon.npoints; j++)
      {
         System.out.print(countries.get(i).polygon.xpoints[j] + (j < countries.get(i).polygon.npoints-1 ? "," : ""));
         xs[j] = countries.get(i).polygon.xpoints[j];
      }
      System.out.print("}, new int[]{");
      for (int j = 0; j < countries.get(i).polygon.npoints; j++)
      {
         System.out.print(countries.get(i).polygon.ypoints[j] + (j < countries.get(i).polygon.npoints-1 ? "," : ""));
         ys[j] = countries.get(i).polygon.ypoints[j];
      }
      System.out.println("}," + countries.get(i).polygon.npoints + ")");
      System.out.println(countries.get(i).polygon.contains(e.getX(),e.getY()));
      Polygon p = new Polygon(xs,ys,xs.length);
      System.out.print("new Polygon(new int[]{");
      for (int j = 0; j < p.npoints; j++)
      {
         System.out.print(p.xpoints[j] + (j < p.npoints-1 ? "," : ""));
      }
      System.out.print("}, new int[]{");
      for (int j = 0; j < p.npoints; j++)
      {
         System.out.print(p.ypoints[j] + (j < p.npoints-1 ? "," : ""));
      }
      System.out.println("}," + p.npoints + ")");
      System.out.println(p.contains(e.getX(), e.getY()));
   }
   if (countries.get(i).polygon.contains(e.getX(),e.getY()))
   {
      System.out.println("Selected something");
      selectedCountry = i;
      break;
   }
}


And here is the output:
1  
2  
3  
4  
5  
In Scandi 438 166
new Polygon(new int[]{410,419,431,452,471,486,477,462,464,481,478,460,451,444,442,431,406,401,390,386,397,404,406}, new int[]{118,102,95,91,105,117,128,121,134,140,185,228,237,237,222,211,187,170,170,154,144,137,129},23)
false
new Polygon(new int[]{410,419,431,452,471,486,477,462,464,481,478,460,451,444,442,431,406,401,390,386,397,404,406}, new int[]{118,102,95,91,105,117,128,121,134,140,185,228,237,237,222,211,187,170,170,154,144,137,129},23)
true


Interesting, no? I wonder if the winding rule is messed up or something like Keith suggested. I'm not worrying about it any further, though, because like I said this just generates code for my 4k game, which doesn't use serialization.

See my work:
OTC Software
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2010-12-26 21:46:52 »

Yeah, confirmed it's Serialization. After loading the Country objects, I've just added this code in:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
for (int i = 0; i < countries.size(); i++)
{
   Polygon p = countries.get(i).polygon;
   int[] xs = new int[p.npoints];
   int[] ys = new int[p.npoints];
   for (int j = 0; j < p.npoints; j++)
   {
      xs[j] = p.xpoints[j];
      ys[j] = p.ypoints[j];
   }
   countries.get(i).polygon = new Polygon(xs,ys,xs.length);
}


And it works as it should.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online pjt33
« Reply #10 - Posted 2010-12-26 23:40:32 »

It's not a trivial bug to reproduce (or has been fixed). The following works fine:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
import java.awt.Polygon;
import java.io.*;
 
public class PolyTest
{
    public static void main(String[] args) throws IOException, ClassNotFoundException
    {
        int[][] testCases = new int[][]{{437, 174}, {427, 112}, {452, 199}, {474, 160}, {397, 162}, {474, 114}, {999, 999}};

        Polygon p = new Polygon(
            new int[]{410,419,431,452,471,486,477,462,464,481,478,460,451,444,442,431,406,401,390,386,397,404,406},
            new int[]{118,102,95,91,105,117,128,121,134,140,185,228,237,237,222,211,187,170,170,154,144,137,129},
            23);

        for (int[] pt : testCases) System.out.println(pt[0] + " " + pt[1] + ": " + p.contains(pt[0], pt[1]));
        System.out.println("-----");

        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(baos);
        oos.writeObject(p);
        oos.close();
        byte[] bytes = baos.toByteArray();

        ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
        ObjectInputStream ois = new ObjectInputStream(bais);
        p = (Polygon)ois.readObject();
        ois.close();

        for (int[] pt : testCases) System.out.println(pt[0] + " " + pt[1] + ": " + p.contains(pt[0], pt[1]));
    }
}
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (36 views)
2014-09-24 16:13:29

Pippogeek (29 views)
2014-09-24 16:12:22

Pippogeek (18 views)
2014-09-24 16:12:06

Grunnt (41 views)
2014-09-23 14:38:19

radar3301 (24 views)
2014-09-21 23:33:17

BurntPizza (60 views)
2014-09-21 02:42:18

BurntPizza (30 views)
2014-09-21 01:30:30

moogie (35 views)
2014-09-21 00:26:15

UprightPath (48 views)
2014-09-20 20:14:06

BurntPizza (52 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!