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

Question

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

• 如果用户点击多边形一，那么一就被选中了。
• 如果用户点击多边形二，那么二被选中。
• 如果用户点击左边的多边形三（我不知道什么是最好的直观反应，所以实际是什么都没有发生）。
• 如果用户点击右边的多边形三三会被选中。
• 用户点击五或四五或四会被选中。

这就是我对需求的实现。

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

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

当然，我可以简单地将我的 "二 "方案扩展为这样的方案。

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

但一定有更好的解决方案 我正在寻找某种循环，如何处理更多的 "堆叠 "多边形，而不为每个多边形的数量添加if-else-case。我没有想到有用的东西。

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

Answer 1

其中一个方法是将多边形按相反的顺序排列，然后在给定的位置选择第一个多边形。

例如，你按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
}

编辑:正如评论中提到的，如果你想让多边形A完全位于另一个多边形B的内部，这意味着A的大小必须小于B的大小，然后你可以像这样选择你的多边形：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

一种方法是选择一个... 重量 就像在你的第一张图片中，多边形的分数是最不可见的（在最后面的那个），也就是多边形2，将有最低的权重。

当有一个 MousePressEvent 你必须选择权重最高的多边形，然后选择多边形。

理想情况下，我会使用权重在[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 而该多边形也将返回 true 在 getSelected()