Algorithm to pick one Polygon which is selected from a User

Question

I can't figure out a proper algorithm to detect if the user had select a Polygon. This is my example:

• If the User clicks on polygon one then one is selected.
• If the User clicks on polygon two then two is selected.
• If the User clicks on the left Side of polygon three (I'm not sure what the best intuitive reaction for this is so actual is happens nothing)
• If the User clicks on the right side of polygon three three is selected.
• User clicks on five or four five or four would be selected.

And this is my implementation for the requirements:

// polygons - a List which contains all Polygons from a scene
Point position = input.getMouse();
List<ChangeablePolygon> selectedPolygons = new ArrayList<>();
for (ChangeablePolygon polygon : polygons) {
    polygon.setSelected(false);
    if (polygon.intersects(position))
        selectedPolygons.add(polygon);
}

if (selectedPolygons.size() == 1) {
    selectedPolygons.get(0).setSelected(true);
} else if (selectedPolygons.size() == 2) {
    ChangeablePolygon one = selectedPolygons.get(0);
    ChangeablePolygon two = selectedPolygons.get(1);
    if (Maths.isPolygonInPolygon(one, two)) {
        two.setSelected(true);
    } else if (Maths.isPolygonInPolygon(two, one)) {
        one.setSelected(true);
    } else if (one.getArea() < two.getArea()) {
        two.setSelected(true);
    } else {
        one.setSelected(true);
    }
}

/**
 * Polygon#intersects(Point):boolean
 *
 * true - if the Point is in the Polygon
 * false - otherwise 
 *
 * Polygon#getArea():double 
 * Returns the size auf the area from the Polygon 
 *
 * Maths#isPolygonInPolygon(Polygon polygon,Polygon inside):boolean
 *
 * true - if all Points from Polygon 'inside' are inside the Polygon 'Polygon'
 * false - otherwise
 */

But unfortunately it fails on the this test case. Because if a selected Polygon one I selected three Polygons and my algorithm can't handle this scenario.

Sure I can simply expand my 'two' scenario to something like this:

ChangeablePolygon one = selectedPolygons.get(0);
ChangeablePolygon two = selectedPolygons.get(1);
ChangeablePolygon three = selectedPolygons.get(2);

if (Maths.isPolygonInPolygon(one, two) && Maths.isPolygonInPolygon(two, three)) {
    three.setSelected(true);
} else if (Maths.isPolygonInPolygon(two, one)) {
    one.setSelected(true);
} else if (Maths.isPolygonInPolygon(one, two)) {
    two.setSelected(true);
}

But there has to be a better solution. I'm looking for some kind of loop how can handle more 'stacked' polygons without adding for every polygon amount a if-else-case. I don't came up with something useful.

I should mention that there is no fill in the engine I use. Unfortunately I can't use a graphical solution. Is there a possible only mathematical way to compute this? Efficient is less important. Here is an unedited Image direct from the engine

Answer 1

One of the approaches would be to sort the polygons in opposite order you draw them and then select the first one at given position.

For example you draw polygons in order 4, 2, 3, 1; you sort them in order: 1, 3, 2, 4

Then iterate over the polygons, only until you find any polygon contains given position.

Pseudocode:

Polygon getSelectedPolygon(mousePosition) {
    List polygons = ...
    sortInRenderingOrder(polygons)
    reverse(polygons)
    polygon selectedPolygon = NULL
    for(Polygon polygon : polygons) {
        if(polygon.intersects(mousePosition)) {
          selectedPolygon = polygon
          break
        }
    }
    return selectedPolygon // returns NULL if nothing was selected
}

Another apporach could be rendering approach: You want to draw the polygons into an image with color equal to their id.

Pseudocode:

int getSelectedPolygonID(mousePosition) {
    List polygons = ...
    sortInRenderingOrder(polygons)
    image tempImage = new image(WIDTH, HEIGHT)
    tempImage.fillWith(0)
    for(Polygon polygon : polygons) {
        polygon.renderOn(tempImage)
    }
    pixelColor = tempImage.getPixelColorAt(mousePosition)
    return pixelColor // returns 0 if nothing got selected
}

Edit: As mentioned in comments, if you want polygon A that is completely inside of another polygon B, that means size of A must be smaller than size of B. You can then pick your polygon like this: Pseudocode:

Polygon getSelectedPolygon(mousePosition) {
    List polygons = ...
    Polygon result = NULL
    resultSize = Infinity
    for(Polygon polygon : polygons) {
        if(polygon.intersects(mousePosition) && polygon.size() < resultSize) {
          result = polygon
          resultSize = polygon.size()
        }
    }
    return result // returns NULL if nothing was selected
}

Answer 2

One approach to this would be to chosse a weight for each polygon. Like in your first picture, the polygon whose fraction is the least visible (the one that is at the exreme back) that is polygon 2, will have the lowest weight.

When there is a MousePressEvent you must select the polygon with the highest weight and select the polygon.

Ideally I would use the weights in the range [0,1]. The layer having the lowest value and vice versa.

So the given code would be like this:

Point position = input.getMouse();

Polygon selected = new ChangeablePolygon();
selected.setWeight(0);// set the weight of this new polygon to be 0
for (ChangeablePolygon polygon : polygons) {

     polygon.setSelected(false);

     if (polygon.intersects(position)){
         if(polygon.getWeight()>=selected.getWeight())
        {
             selected.setSelected(false);
             selected = polygon;
             polygon.setSelected(true);
        }  
   }


     }
}

the recquired polgon will be stored in selected and that polygon will also return true in getSelected()