选择一个从用户中选择的多边形的算法

Question

我想不出一个合适的算法来检测用户是否有 select 多边形。这是我的例子：

如果用户单击多边形一，那么会select编辑多边形。
如果用户点击多边形二，那么会select编辑二。
如果用户单击多边形三的左侧（我不确定对此的最佳直观反应是什么，所以实际上什么都没有发生）
如果用户单击多边形三的右侧，则三是 selected。
用户点击五个或四个五个或四个将被 selected。

这是我对要求的实现：

// 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
 */

但不幸的是，它在这个测试用例上失败了。因为如果一个 selected 多边形一个我 selected 三个多边形我的算法无法处理这种情况。

当然，我可以简单地将我的 'two' 场景扩展为如下所示：

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);
}

但必须有更好的解决方案。我正在寻找某种循环如何处理更多 'stacked' 多边形，而无需为每个多边形数量添加 if-else-case。我没有想出有用的东西。

我应该提到我使用的引擎没有填充。不幸的是我不能使用图形解决方案。有没有可能唯一的数学方法来计算这个？效率不太重要。这是直接来自引擎的未经编辑的图像

Answer 1

其中一种方法是以与绘制它们相反的顺序对多边形进行排序，然后 select 第一个位于给定位置。

例如，您按 4、2、3、1 的顺序绘制多边形；您按顺序对它们进行排序：1、3、2、4

然后遍历多边形，只有直到你找到任何包含给定位置的多边形。

伪代码：

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
}

另一种方法可能是渲染方法：您想将多边形绘制到图像中，颜色等于它们的 id。

伪代码：

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
}

编辑：如评论中所述，如果您想要完全位于另一个多边形 B 内部的多边形 A，则意味着 A 的大小必须小于 B 的大小。然后你可以像这样选择你的多边形：伪代码：

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

一种方法是为每个多边形选择一个权重。就像在您的第一张图片中一样，其分数最不可见的多边形（位于极端背面的多边形）即多边形 2，其权重最低。

当存在 MousePressEvent 时，您必须 select 具有最高权重的多边形和 select 多边形。

理想情况下，我会使用 [0,1] 范围内的权重。具有最低值的层，反之亦然。

所以给定的代码应该是这样的：

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);
        }  
   }


     }
}

所需的多边形将存储在 selected 中，该多边形也将 return true 存储在 getSelected()

中

选择一个从用户中选择的多边形的算法

Algorithm to pick one Polygon which is selected from a User

java

algorithm

2d

polygon

intersection