Finding polygons in 2D area

Question

I have an two dimensional area which contains X amount of polygons. the only information I have is the edges of the polygons. The polygons are formed from Fortunes algorithm for Voronoi diagrams.

I am trying to form a list of polygons in java. My problem lies with figuring out the edges which belong to a polygon. I should add that I have a point inside each polygon too, this is what the Voronoi diagrams are formed around.

I have tried multiple methods. I've tried calculating the closest point to each edge but this gives errors. I've also tried doing a diagonal sweep trying to figure out the edges somehow, it didn't work either.

EDIT:

Each edge is a line, it has an x1, y1, x2 and y2. I have a list of edges and I have a list of points available, I am able to draw the Voronoi diagram. My desired output would be for every point I have a list of edges which form the shape of the polygon which the point is inside of.

http://www.cs.wustl.edu/~pless/546/lectures/f16_voronoi.jpg

Here's and example of what I have so far. I can produce this image only because I know the start and end point of each line. I know nothing about the polygons. My goal is to have a list of shapes so that I can choose which one I would like to draw.

EDIT 5:

Here are test points which I have set up. I'm looking to make a voronoi diagram based on them. I have the lines which separate the points which form the bases for the voronoi. I now need to make polygons from these lines.

vals = new double[2][6];
    vals[0][0] = 150;
    vals[1][0] = 250;
    vals[0][1] = 250;
    vals[1][1] = 275;
    vals[0][2] = 300;
    vals[1][2] = 300;
    vals[0][3] = 425;
    vals[1][3] = 425;
    vals[0][4] = 425;
    vals[1][4] = 125;
    vals[0][5] = 250;
    vals[1][5] = 500;

The points and code provided in the answer produce the following:

Currently your question sounds not very clear. It would be nice if you provide a sample input and desired output for your task and explain on the provided input data why simple algorithms don't work there. — Tagir Valeev, Aug 13 '15 at 10:21
if the edges are given, the solution is pretty forward: simply search the edges that belong to each other/have one end-point in common. apart from that this question is doesn't provide enough information to make clear what the **exact** problem is — , Aug 13 '15 at 10:23
@MauricePerry http://www.cs.wustl.edu/~pless/546/lectures/f16_voronoi.jpg — Michael Richardson, Aug 13 '15 at 10:42
It seems that all the polygons are convex. Is it a property of voronoi diagrams? — Maurice Perry, Aug 13 '15 at 10:48
Yes. I do have the co-ordinates of the enclosing rectangle (x1,x2,y1,y2). A thought I had would be to go around in a clockwise manner and when you get to a point you follow it. slowly eliminating polygons but it starts to get tricky when polygons sit in between others. — Michael Richardson, Aug 13 '15 at 10:49
Until someone comes up with a better answer, take each line, and make a tree connecting the line end point with another line start point. Any tree with 3 or more lines is a polygon. Eliminate the duplicate polygons, and save them. — Gilbert Le Blanc, Aug 13 '15 at 11:32
@GilbertLeBlanc Won't that potentially get polygons that contain multiple points? — GoldDragonTSU, Aug 13 '15 at 23:51
better if you give us a data file, it's much more useful than your provided code. — fronthem, Aug 16 '15 at 16:00

score 0 · Answer 1 · edited May 23 '17 at 12:14

Some observations about Voronoi diagrams (using good ole Wikipedia as a reference):

Let's call the interior point inside of a polygon the "seed".
Each polygon has one seed and the polygon itself represents the collection of all points that are closer to its seed than to any other seeds.
The edge segments on the border of the diagram are closest to only one seed.
The edge segments inside of the diagram (NOT the ones on the border of the diagram) are formed by segments that are the same distance from two seeds.
The polygon vertices on the border of the diagram are points the same distance from two or more seeds. A possible exception is one of the four corner points of the border, though even these can theoretically be equidistant to multiple seeds.
The polygon vertices inside of the diagram (i.e. those that are NOT on the border) are points the same distance from three or more seeds.

So my suggested approach would be to loop through the collection of edge segments, comparing the distance of each edge segment's end points to the seeds and locating the closest seed or seeds.

The following is not optimized, but should meet the requirements unless I misunderstood them. The List<SeedPoint> seeds will have the seed point itself as well as the edges that surround it.

BTW, I'm ignoring precision / decimal rounding issues that could affect the logic.

// Get the list of edges and seeds from wherever you are getting them.
List<GraphEdge> edges = ...
List<SeedPoint> seeds = ...    // Assume SeedPoint is a subclass of Point.

for ( GraphEdge edge : edges )
{
  List<SeedPoint> closestSeeds = new ArrayList<>(2);

  // These can safely be instantiated to the diagram's hypotenuse + 1
  double closestStartDistance = ...
  double closestEndDistance = ...

  // Compare the distance of all seeds to the current edge's endpoints:
  for( SeedPoint seed : seeds )
  {
    double startEdgeToSeed = seed.distanceFrom( edge.getStartPoint() );
    double endEdgeToSeed   = seed.distanceFrom( edge.getEndPoint() );

    /* For a seed to be tracked as closest to the edge, BOTH the edge
       end points must be as close or closer to the seed than the
       current known closest edge.

       CAUTION: Update this to consider decimal precision issues! */

    if ( startEdgeToSeed == closestStartDistance &&
         endEdgeToSeed   == closestEndDistance )
    {
      // Same closeness to the currently known closest seed.
      closestSeeds.add(seed);
    }
    else if ( startEdgeToSeed <= closestStartDistance &&
              endEdgeToSeed   <= closestEndDistance )
    {
      /* Current seed is closer than the currently known closest seed.
         Clear previous seeds and track the current. */
      closestSeeds.clear();
      closestSeeds.add( seed );
      closestStartDistance = startEdgeToSeed;
      closestEndDistance   = endEdgeToSeed;
    }

  }

  /* At the end of the iteration, closestSeeds should have size
     of either 1 or 2.  Associate the edge to the seed or seeds
     to which it is closest. */
  for ( SeedPoint closestSeed : closestSeeds )
  {
    closestSeed.addPolygonEdge( edge );
  }

}

For convenience, you probably want a method somewhere that takes two points as parameters and calculates the distance between them. In the above code, that's what somePoint.distanceFrom(someOtherPoint) is.

There might be other approaches that are better, and there are likely ways to optimize the example above...

score 0 · Answer 2 · answered Aug 16 '15 at 15:47

I eventually came up with a solution, it doesn't work 100% yet but most of the time it does. There is an odd bug that causes one or two line to be misplaced, I'm still working on that. the code pretty much takes each line and when it gets to a vertex it goes right, thus landing up at the starting point or at a border point. Once the sort of polygons have been made, the border function places all the missing borders in the polygons. My plan after this is to get rid of the duplicate polygons as it is redundant having them and slows the method down.

private void constructPolygons() {
    listRoots = new ArrayList<>();
    int poly = 0;
    for (GraphEdge edge : edges) {

        List<GraphEdge> prevEdges = new ArrayList<>();

        prevEdges.add(edge);

        int count = 0;

        Point forward = edge.getEnd();
        Point reverse = edge.getStart();

        GraphEdge currentForward = edge;
        GraphEdge currentReverse = edge;

        List<GraphEdge> tempArray = new ArrayList<>();
        tempArray.add(edge);

        System.out.println("#############################################");
        System.out.printf("### Line %d is the start #####################\n", poly);
        System.out.println("#############################################");

        for (int ii = 0; ii < edges.size(); ii++) {

            GraphEdge compEdge = edges.get(ii);

            System.out.println("line: " + ii);

            System.out.println("forward: " + forward.xCord + " " + forward.yCord);
            System.out.println("reverse: " + reverse.xCord + " " + reverse.yCord);

            System.out.println("compEdge: " + compEdge.getStart().xCord + " " + compEdge.getStart().yCord + " " + compEdge.getEnd().xCord + " " + compEdge.getEnd().yCord);

            System.out.println("tempArray size: " + tempArray.size());

            // Check to see whether polygon is closed. If true, break and continue with other points.
            if( ((Math.abs(forward.xCord - reverse.xCord) <= tolerance) && (Math.abs(forward.yCord - forward.yCord) <= tolerance)) ) {
                System.out.println("POLYGON MUST CLOSE");
                break;
            }

            // Check to see whether point is on one of the borders
            if( (((Math.abs(forward.xCord - mapMaxX) <= tolerance) || (Math.abs(forward.yCord - mapMaxY) <= tolerance)) ||
                    ((Math.abs(forward.xCord - mapMinX) <= tolerance) || (Math.abs(forward.yCord - mapMinY) <= tolerance))) &&  (tempArray.size() > 1) ) {
                System.out.println("POLYGON MUST CLOSE");
                break;
            }
            // Check to see if edge has already been used
            if (!tempArray.contains(compEdge)) {

                double compStartX = compEdge.getStart().xCord;
                double compStartY = compEdge.getStart().yCord;
                double compEndX = compEdge.getEnd().xCord;
                double compEndY = compEdge.getEnd().yCord;

                if( ((Math.abs(forward.xCord - mapMinX) <= tolerance || Math.abs(forward.xCord - mapMaxX) <= tolerance) || (Math.abs(forward.yCord - mapMinY) <= tolerance || Math.abs(forward.yCord - mapMaxY) <= tolerance)) && (tempArray.size() <= 1)){
                    System.out.println(tempArray.size() < 1);
                    System.out.println("Swap values around");
                    Point temp = forward;
                    forward = reverse;
                    reverse = temp;
                }

                // If end of currentForward == start of compEdge
                // Start -- End --> Start -- End
                if ((Math.abs(forward.xCord - compStartX) <= tolerance) && (Math.abs(forward.yCord - compStartY) <= tolerance)) {
                    System.out.println("end -> start");

                    double sign1 = isPointLeft( currentForward.x1, currentForward.y1, forward.xCord, forward.yCord, compEndX, compEndY );
                    double sign2 = isPointLeft( currentForward.x2, currentForward.y2, forward.xCord, forward.yCord, compEndX, compEndY );
                    System.out.println("sign: " + sign1);
                    System.out.println("sign: " + sign2);

                    // End point must be on the right side of the line
                    if (sign1 > 0 || sign2 > 0) {
                        ii = -1;
                        forward = compEdge.getEnd();
                        currentForward = compEdge;
                        tempArray.add(compEdge);
                        System.out.println("added: " + compEdge.getStart().xCord + " " + compEdge.getStart().yCord + " " + compEdge.getEnd().xCord + " " + compEdge.getEnd().yCord);
                    }
                }
                // If end of currentForward == end of compEdge
                // Start -- End --> End -- Start
                else if ((Math.abs(forward.xCord - compEndX) <= tolerance) && (Math.abs(forward.yCord - compEndY) <= tolerance)) {
                    System.out.println("end -> end");

                    double sign1 = isPointLeft( currentForward.x1, currentForward.y1, forward.xCord, forward.yCord, compStartX, compStartY );
                    double sign2 = isPointLeft( currentForward.x2, currentForward.y2, forward.xCord, forward.yCord, compStartX, compStartY );
                    System.out.println("sign: " + sign1);
                    System.out.println("sign: " + sign2);

                    // Start point must be on the right side of the line
                    if (sign1 > 0 || sign2 > 0) {
                        ii = -1;
                        forward = compEdge.getStart();
                        currentForward = compEdge;
                        tempArray.add(compEdge);
                        System.out.println("added: " + compEdge.getStart().xCord + " " + compEdge.getStart().yCord + " " + compEdge.getEnd().xCord + " " + compEdge.getEnd().yCord);
                    }
                }
            } else {
                System.out.println("already in list");
            }
            count++;
            prevEdges.add(compEdge);
            System.out.println("------------------------------------------");

        }
        if (tempArray.size() > 1) {
            listRoots.add(tempArray);
            poly++;
        }
    }

        for (List<GraphEdge> list : listRoots) {
        boolean point1 = false, point2 = false;

        Point bp1 = new Point(), bp2 = new Point();

         //            System.out.println("---------------------------------");

        for (GraphEdge ge : list) {

        //                System.out.println("Points: " + ge.x1 + "," + ge.y1 + "," + ge.x2 + "," + ge.y2);

            if (ge.x1 == mapMinX || ge.x1 == mapMaxX || ge.y1 == mapMinY || ge.y1 == mapMaxY) {

                if (point1) {
                    point2 = true;
                    bp2.setPoint(ge.x1, ge.y1);
                } else {
                    point1 = true;
                    bp1.setPoint(ge.x1, ge.y1);
                }

            } else if (ge.x2 == mapMinX || ge.x2 == mapMaxX || ge.y2 == mapMinY || ge.y2 == mapMaxY) {

                if (point1) {
                    point2 = true;
                    bp2.setPoint(ge.x2, ge.y2);
                } else {
                    point1 = true;
                    bp1.setPoint(ge.x2, ge.y2);
                }
            }
        }

        if (point1 && point2) {
        //                System.out.println("Add border");
            System.out.println(bp1.xCord + "," + bp1.yCord + "," + bp2.xCord + "," + bp2.yCord);
            insertBorderLine(bp1, bp2, list);
        }
    }


}

Finding polygons in 2D area

2 Answers2