查找具有旋转轴的旋转多边形的边界框

雅各布·甘瑟

我在这里浏览了其他一些接近的答案,但是找不到解决我问题的方法。

我有一个绕轴位置旋转的多边形,我需要找到该多边形的边界框。本质上,边界框对象应具有左上角xy位置width以及height框本身我可以使用此代码在不旋转的情况下计算多边形的框,但它也不考虑旋转。红色正方形是当前没有旋转的边界框,绿色圆圈是旋转轴,多边形是多边形本身。

带未旋转边界框的旋转多边形

Ideally, I don't want to re-compute each vertex position on each call to get the bounding box, I want it to be in the math itself. Here's an example of the polygon and the bounding box without rotation: https://i.imgur.com/MSOM9Q1.mp4

Here is my current code for finding bounding box for the non-rotated polygon:

const minX = Math.min(...this.vertices.map((vertex) => vertex.x));
const minY = Math.min(...this.vertices.map((vertex) => vertex.y));

return {
    x: minX + this.position.x,
    y: minY + this.position.y,
    width: Math.max(...this.vertices.map((vertex) => vertex.x)) - minX,
    height: Math.max(...this.vertices.map((vertex) => vertex.y)) - minY
};

Polygon object structure:

多边形对象结构

  • The position is the center of the polygon
  • The rotationAxis is a vector relative to the center of the polygon (position)
  • The vertices array is a list of vectors relative to the center of the polygon

Bounding box structure:

边界框对象结构

What do I need to do calculate the bounding box of the rotated polygon?

Spektre

if you do not want to recompute the axis aligned BBOX from all the vertexes of polygon after any rotation/translation then do it from OBB that is only 4 vertexes ...

  1. Compute OBB of unrotated/untranslated polygon

    this operation is slow but its done just once (unless your polygon is changing shape or size)

  2. At any transformation of polygon

    transform the OBB vertexes in the same way too. And then compute axis aligned BBOX from transformed OBB vertexes (just finding min/max coordinates as you do now).

This way you have to compute stuff from only 4 vertexes instead of Ntransforming the complexity from O(N) into O(1).

此外,拥有OBB可能会在以后派上用场,因为它可以加快某些操作甚至提高碰撞测试的精度等。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章