11 Replies Latest reply: Aug 21, 2009 8:21 AM by 800025 RSS

    get the outer border of the unordered point of polygon

    843853
      Hi all,

      I meet some problem regarding about polygon with unordered points of polygon. I got some Point of polygon from source data (ENC file format) that cannot be changed. So, i want to look some help from you all. how to get the outer border of polygon?
      Here is the paint function that i had created :
       public void paint(Graphics g) {
              super.paint(g);
              Polygon p = new Polygon();
              String point = "3331,2305;3317,2332;3317,2356;3310,2356;3302,2355;3331,2305;3317,2286;3317,2281;3392,2281;3392,2356;3317,2356;" 
      +                             "3317,2332;3331,2305;3303,2278;3312,2281;3317,2281;3317,2286;3303,2278;3254,2313;3249,2309;3249,2281;"+ 
                                   "3295,2281;3303,2278;3295,2281;3249,2281;3242,2241;3242,2206;3317,2206;3317,2281;3312,2281;3249,2309;" 
      +                             "3233,2159;3344,2079;3317,2102;3317,2131;3275,2131;3242,2156;3242,2206;3242,2241;3249,2281;3344,2079;"+ 
                                   "3349,2078;3352,2074;3361,2093;3385,2078;3392,2078;3392,2131;3317,2131;3317,2102;3344,2079;3352,2074;" 
      +                             "3349,2078;3361,2093;3390,2070;3650,2070;3656,2078;3617,2078;3542,2078;3467,2078;3392,2078;3385,2078;"+ 
                                   "3650,2070;3731,2143;3722,2141;3714,2131;3620,2131;3617,2131;3617,2078;3656,2078;3731,2143;3565,2249;" 
      +                             "3617,2211;3617,2206;3624,2206;3620,2131;3714,2131;3722,2141;3565,2249;3494,2296;3513,2281;3467,2281;"+ 
                                   "3467,2206;3542,2206;3542,2261;3565,2249;3542,2261;3542,2206;3617,2206;3617,2211;3494,2296;3465,2315;" 
      +                             "3467,2310;3467,2281;3513,2281;3465,2315;3390,2365;3313,2365;3302,2355;3310,2356;3317,2356;3392,2356;"+ 
                                   "3398,2356;3396,2281;3467,2281;3467,2310;3392,2356;3392,2281;3396,2281;3398,2356;3392,2281;3317,2281;" 
      +                             "3317,2206;3392,2206;3392,2281;3392,2206;3467,2206;3467,2281;3396,2281;3317,2206;3242,2206;3242,2156;"+ 
                                   "3275,2131;3317,2131;3317,2206;3317,2131;3392,2131;3392,2206;3392,2206;3392,2131;3467,2131;3467,2206;" 
      +                             "3542,2206;3467,2206;3467,2131;3542,2131;3542,2206;3542,2131;3617,2131;3617,2206;3624,2206;3617,2206;"+ 
                                   "3617,2131;3620,2131;3392,2131;3392,2078;3467,2078;3467,2131;3542,2131;3467,2131;3467,2078;3542,2078;" +
                                   "3542,2131;3542,2078;3617,2078;3617,2131";
      
              Scanner read = new Scanner(point).useDelimiter("[;,]");        
      
              Graphics2D g2 = (Graphics2D)g;
              g2.setColor(Color.BLACK);
      
              while (read.hasNextInt()) {
                   int x = (int)read.nextInt()/10;
                   int y = (int)read.nextInt()/10;
                   p.addPoint(x,y);
              }
              read.close();
      
              g2.drawPolygon(p1);        
          }
      Thanks in advance..

      regards,

      tenlee

      Edited by: tenly on Aug 18, 2009 10:46 PM
        • 1. Re: get the outer border of the unordered point of polygon
          800282
          tenly wrote:
          Hi all,

          I meet some problem regarding about polygon with unordered points of polygon. I got some Point of polygon from source data (ENC file format) that cannot be changed. So, i want to look some help from you all. how to get the outer border of polygon?
          There can be different definitions of "outer border of polygon". Do you mean the [convex hull|http://mathworld.wolfram.com/ConvexHull.html] of a set of points?
          • 2. Re: get the outer border of the unordered point of polygon
            843853
            Hi prometheuzz,

            sorry for my bad choosen word, so make you become confused.
            yeah you right, i mean how to get CONVEX HULL of some of point? is java already give such API or i need to create it ?

            thank you for your reply.

            regards,

            tenlee
            • 3. Re: get the outer border of the unordered point of polygon
              843853
              Hi prometheuzz,

              sorry for my bad chosen word, so make you become confused.
              yeah you right, i mean how to get CONVEX HULL of some of point? is java already give such API or i need to create it ?

              thank you for your reply.

              regards,

              tenlee
              • 4. Re: get the outer border of the unordered point of polygon
                800282
                tenly wrote:
                Hi prometheuzz,

                sorry for my bad choosen word, so make you become confused.
                yeah you right, i mean how to get CONVEX HULL of some of point? is java already give such API or i need to create it ?

                thank you for your reply.

                regards,

                tenlee
                No problem.
                No, the standard API does not contain such a method. You might want to Google for "Graham scan" or "3 coins algorithm" for a O(n*log(n)) algorithm for finding the convex hull.
                You could also checkout: [http://www.big-o.nl/demos/computationalgeometry/convexhull]. Although the "download source" does not work (yet), I am still working on that website, it does give a brief overview of the algorithm and some pseudo code for you to work with. Feel free to post specific questions here.

                Good luck.
                • 5. Re: get the outer border of the unordered point of polygon
                  843853
                  prometheuzz wrote:

                  No problem.
                  No, the standard API does not contain such a method. You might want to Google for "Graham scan" or "3 coins algorithm" for a O(n*log(n)) algorithm for finding the convex hull.
                  You could also checkout: [http://www.big-o.nl/demos/computationalgeometry/convexhull]. Although the "download source" does not work (yet), I am still working on that website, it does give a brief overview of the algorithm and some pseudo code for you to work with. Feel free to post specific questions here.

                  Good luck.
                  Hi prometheuzz,

                  I had tried the open source convex hull for my problem. The result not like what I want (sorry I didn't mention clearly about what i want). here I try to describe it with image, hopefully it become clear. :)

                  when I run the previous code that I posted. the program will produce shape of polygon like this.
                  [http://img37.imageshack.us/i/47840595.jpg/]
                  what I want is to get the point that create the border of shape of polygon.
                  [http://img193.imageshack.us/i/77900475.jpg/|http://img193.imageshack.us/i/77900475.jpg/]

                  is it possible prometheuzz ?
                  I really stuck for this one :(

                  Thank you for your kindness.

                  warm regards,

                  Tenlee
                  • 6. Re: get the outer border of the unordered point of polygon
                    800282
                    tenly wrote:
                    what I want is to get the point that create the border of shape of polygon.
                    [http://img193.imageshack.us/i/77900475.jpg/|http://img193.imageshack.us/i/77900475.jpg/]

                    is it possible prometheuzz ?
                    Probably, but only if you explain how these red points differ from the other points.
                    • 7. Re: get the outer border of the unordered point of polygon
                      843853
                      Hi prometheuzz,

                      I plan to solve that problem using this way. first time, i generate the list of line that make the polygon and then I choose 1 point as a starting point with the maximum X value. Then I travel to the possible line (counter clockwise) base on the previous list with constraint most right line must be chosen. And repeated until found starting point.

                      but i still not yet figure out how to determine which line is most right then the other one. Do you have any idea or suggestion about this prometheuzz ?

                      warm regards,

                      Tenlee
                      • 8. Re: get the outer border of the unordered point of polygon
                        800282
                        I'm sorry, but I still have no idea what exactly you're trying to do, so I cannot help you with this.
                        I'm assuming that the input is not just a set of points, but the order of the points is important to you? If so, please elaborate.
                        And again: what make the points you highlighted special? From the two images you posted a link to, I cannot extract this information: you will need to clarify.
                        Also, your remark "how to determine which line is most right then the other one" can mean an awful lot. This also needs some clarification.
                        • 9. Re: get the outer border of the unordered point of polygon
                          843853
                          >
                          I'm sorry, but I still have no idea what exactly you're trying to do, so I cannot help you with this.
                          I'm assuming that the input is not just a set of points, but the order of the points is important to you? If so, please elaborate.
                          And again: what make the points you highlighted special? From the two images you posted a link to, I cannot extract this information: you will need to clarify.
                          Also, your remark "how to determine which line is most right then the other one" can mean an awful lot. This also needs some clarification.>
                          Hi prometheuzz,

                          I try to clarify what i need. base on the list of input Point, I draw the Line between 2 Point sequentially. Line1 construct from Point1 and Point2, Line2 construct from Point2 and Point3, and so on.. The result is become like first image.
                          What I want to find is getting which line is border of the polygon like second image.
                          prometheuzz wrote:what make the points you highlighted special?
                          this is what i want to find out: List of Point that become the border of Polygon base on input list of lines.
                          prometheuzz wrote:Also, your remark "how to determine which line is most right then the other one" can mean an awful lot. This also needs some clarification.
                          what in my head is like this :
                          if there is 4 Points (-2,3) , (1,6) , (0,0) , (2,3) we currently at Point(0,0) so we have 3 Lines (0,0)->(-2,3) , (0,0)->(1,6) and (0,0)->(2,3).
                          we can judge that the most right line then the other is Line (0,0)->(2,3). but i don't have any idea how computer judge it.
                          i am thinking to use angle to determined it but the next question if i use angle is which Point become the base Point to get the angel.

                          thanks for your reply

                          warm regards,

                          Tenlee
                          • 10. Re: get the outer border of the unordered point of polygon
                            800282
                            tenly wrote:
                            >
                            I'm sorry, but I still have no idea what exactly you're trying to do, so I cannot help you with this.
                            I'm assuming that the input is not just a set of points, but the order of the points is important to you? If so, please elaborate.
                            And again: what make the points you highlighted special? From the two images you posted a link to, I cannot extract this information: you will need to clarify.
                            Also, your remark "how to determine which line is most right then the other one" can mean an awful lot. This also needs some clarification.>
                            Hi prometheuzz,

                            I try to clarify what i need. base on the list of input Point, I draw the Line between 2 Point sequentially. Line1 construct from Point1 and Point2, Line2 construct from Point2 and Point3, and so on.. The result is become like first image.
                            Okay, last time I'm going to try.
                            Those images are not too clear to me. And one of the points you highlighted don't look like it's on the border of your polygon. So, it's still not clear to me.

                            Say you have the following polygon:
                            A -> B -> C -> D -> E -> F -> G -> H -> A
                            where the points are:
                            A = (0,0)
                            B = (5,0)
                            C = (7,2)
                            D = (5,4)
                            E = (5,1)
                            F = (9,3)
                            G = (5,5)
                            H = (2,2)
                            Question 1: what points (or line segments) are you interested in?

                            Now change point F from (9,3) to (9,2) and let the rest of the polygon be the same.
                            Question 2: what points (or line segments) are you interested in now?
                            if there is 4 Points (-2,3) , (1,6) , (0,0) , (2,3) we currently at Point(0,0) so we have 3 Lines (0,0)->(-2,3) , (0,0)->(1,6) and (0,0)->(2,3).
                            we can judge that the most right line then the other is Line (0,0)->(2,3). but i don't have any idea how computer judge it.
                            i am thinking to use angle to determined it but the next question if i use angle is which Point become the base Point to get the angel.
                            Okay but what about the line going through (0,0) and (-5,1)? That has a negative slope, but can be considered "more straight" than the line going through (0,0) and (2,3).
                            • 11. Re: get the outer border of the unordered point of polygon
                              800025
                              Hi,

                              Just out of curiosity I gave it a shot. It seems that only on the upper left side the result is a bit different than the result that you expect (according to the picture with the red dots).
                              import java.awt.Color;
                              import java.awt.Graphics;
                              import java.awt.Graphics2D;
                              import java.awt.Polygon;
                              import java.awt.Shape;
                              import java.awt.geom.Area;
                              import java.awt.geom.Path2D;
                              import java.awt.geom.PathIterator;
                              import java.util.Scanner;
                              
                              import javax.swing.JFrame;
                              import javax.swing.JPanel;
                              import javax.swing.SwingUtilities;
                              
                              public class OuterShape extends JPanel {
                              
                                  public static void main(String[] args) {
                                   SwingUtilities.invokeLater(new Runnable() {
                              
                                       @Override
                                       public void run() {
                                        new OuterShape().createGUI();
                                       }
                                   });
                                  }
                              
                                  private final Shape outerShape;
                              
                                  private final Polygon polygon;
                              
                                  {
                                   outerShape = createOuterShape();
                                   polygon = createPolygon();
                                   this.setOpaque(true);
                                   this.setBackground(Color.GREEN);
                                  }
                              
                                  private static final long serialVersionUID = 1L;
                              
                                  private static String point = "3331,2305;3317,2332;3317,2356;3310,2356;3302,2355;3331,2305;3317,2286;3317,2281;3392,2281;3392,2356;3317,2356;"
                                       + "3317,2332;3331,2305;3303,2278;3312,2281;3317,2281;3317,2286;3303,2278;3254,2313;3249,2309;3249,2281;"
                                       + "3295,2281;3303,2278;3295,2281;3249,2281;3242,2241;3242,2206;3317,2206;3317,2281;3312,2281;3249,2309;"
                                       + "3233,2159;3344,2079;3317,2102;3317,2131;3275,2131;3242,2156;3242,2206;3242,2241;3249,2281;3344,2079;"
                                       + "3349,2078;3352,2074;3361,2093;3385,2078;3392,2078;3392,2131;3317,2131;3317,2102;3344,2079;3352,2074;"
                                       + "3349,2078;3361,2093;3390,2070;3650,2070;3656,2078;3617,2078;3542,2078;3467,2078;3392,2078;3385,2078;"
                                       + "3650,2070;3731,2143;3722,2141;3714,2131;3620,2131;3617,2131;3617,2078;3656,2078;3731,2143;3565,2249;"
                                       + "3617,2211;3617,2206;3624,2206;3620,2131;3714,2131;3722,2141;3565,2249;3494,2296;3513,2281;3467,2281;"
                                       + "3467,2206;3542,2206;3542,2261;3565,2249;3542,2261;3542,2206;3617,2206;3617,2211;3494,2296;3465,2315;"
                                       + "3467,2310;3467,2281;3513,2281;3465,2315;3390,2365;3313,2365;3302,2355;3310,2356;3317,2356;3392,2356;"
                                       + "3398,2356;3396,2281;3467,2281;3467,2310;3392,2356;3392,2281;3396,2281;3398,2356;3392,2281;3317,2281;"
                                       + "3317,2206;3392,2206;3392,2281;3392,2206;3467,2206;3467,2281;3396,2281;3317,2206;3242,2206;3242,2156;"
                                       + "3275,2131;3317,2131;3317,2206;3317,2131;3392,2131;3392,2206;3392,2206;3392,2131;3467,2131;3467,2206;"
                                       + "3542,2206;3467,2206;3467,2131;3542,2131;3542,2206;3542,2131;3617,2131;3617,2206;3624,2206;3617,2206;"
                                       + "3617,2131;3620,2131;3392,2131;3392,2078;3467,2078;3467,2131;3542,2131;3467,2131;3467,2078;3542,2078;"
                                       + "3542,2131;3542,2078;3617,2078;3617,2131";
                              
                                  public void createGUI() {
                                   JFrame frame = new JFrame();
                                   frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                                   frame.add(this);
                                   frame.setSize(600, 600);
                                   frame.setLocationRelativeTo(null);
                                   frame.setVisible(true);
                                  }
                              
                                  private Shape createOuterShape() {
                                   Scanner read = new Scanner(point).useDelimiter("[;,]");
                                   Path2D pathOne = new Path2D.Double(Path2D.WIND_NON_ZERO), pathTwo = new Path2D.Double(
                                        Path2D.WIND_EVEN_ODD);
                                   boolean opened = false;
                                   while (read.hasNextInt()) {
                                       int x = (int) read.nextInt();
                                       int y = (int) read.nextInt();
                                       if (opened) {
                                        pathOne.lineTo(x, y);
                                        pathTwo.lineTo(x, y);
                                       } else {
                                        pathOne.moveTo(x, y);
                                        pathTwo.moveTo(x, y);
                                        opened = true;
                                       }
                                   }
                                   pathOne.closePath();
                                   pathTwo.closePath();
                                   read.close();
                                   Area area = new Area(pathOne);
                                   area.add(new Area(pathTwo));
                              
                                   if (!area.isSingular()) {
                                       Area newArea = new Area();
                                       Path2D singlePath = new Path2D.Double();
                                       PathIterator pi = area.getPathIterator(null);
                                       double[] coords = new double[6];
                                       while (!pi.isDone()) {
                                        int type = pi.currentSegment(coords);
                                        switch (type) {
                                        case PathIterator.SEG_MOVETO:
                                            newArea.add(new Area(singlePath));
                                            newArea = new Area();
                                            singlePath.moveTo(coords[0], coords[1]);
                                            break;
                                        case PathIterator.SEG_CLOSE:
                                            singlePath.closePath();
                                            break;
                                        case PathIterator.SEG_CUBICTO:
                                            singlePath.curveTo(coords[0], coords[1], coords[2],
                                                 coords[3], coords[4], coords[5]);
                                            break;
                                        case PathIterator.SEG_LINETO:
                                            singlePath.lineTo(coords[0], coords[1]);
                                            break;
                                        case PathIterator.SEG_QUADTO:
                                            singlePath.quadTo(coords[0], coords[1], coords[2],
                                                 coords[3]);
                                            break;
                                        }
                                        newArea.add(new Area(singlePath));
                                        pi.next();
                                       }
                                       area = newArea;
                                   }
                                   return area;
                                  }
                              
                                  private Polygon createPolygon() {
                                   Polygon polygon = new Polygon();
                                   Scanner read = new Scanner(point).useDelimiter("[;,]");
                                   while (read.hasNextInt()) {
                                       int x = (int) read.nextInt();
                                       int y = (int) read.nextInt();
                                       polygon.addPoint(x, y);
                                   }
                                   read.close();
                              
                                   return polygon;
                                  }
                              
                                  @Override
                                  protected void paintComponent(Graphics g) {
                                   super.paintComponent(g);
                                   Graphics2D g2 = (Graphics2D) g.create();
                                   g2.translate(-3200, -2000);
                              
                                   g2.setColor(Color.WHITE);
                                   g2.fill(outerShape);
                              
                                   g2.setColor(Color.BLACK);
                                   g2.draw(polygon);
                                  }
                              
                              }
                              Piet