两个旋转矩形的相交面积 [英] Area of Intersection of Two Rotated Rectangles

查看:34
本文介绍了两个旋转矩形的相交面积的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我有两个 2D 矩形,定义为 原点 (x,y)、大小(高度、宽度)和 旋转角度 (0-360°).我可以保证两个矩形的大小相同.

I have two 2D rectangles, defined as an origin (x,y) a size (height, width) and an angle of rotation (0-360°). I can guarantee that both rectangles are the same size.

我需要计算这两个矩形相交的近似面积.

I need to calculate the approximate area of intersection of these two rectangles.

计算不需要精确,尽管可以.我会将结果与其他相交区域进行比较,以确定一组矩形中最大的相交区域,因此它只需要相对于相同算法的其他计算准确即可.

The calculation does not need to be exact, although it can be. I will be comparing the result with other areas of intersection to determine the largest area of intersection in a set of rectangles, so it only needs to be accurate relative to other computations of the same algorithm.

我考虑过使用相交区域的边界框的面积,但由于所有不同的可能情况,我无法获取相交区域的顶点:

I thought about using the area of the bounding box of the intersected region, but I'm having trouble getting the vertices of the intersected region because of all of the different possible cases:

我正在 Cocoa 框架中用 Objective-C 编写这个程序,这是为了它的价值,所以如果有人知道使用 NSBezierPath 的任何快捷方式或其他东西,也欢迎你提出建议.

I'm writing this program in Objective-C in the Cocoa framework, for what it's worth, so if anyone knows any shortcuts using NSBezierPath or something you're welcome to suggest that too.

推荐答案

一个可以给出近似答案的简单算法是采样.

A simple algorithm that will give an approximate answer is sampling.

将其中一个矩形分成小方块网格.对于每个交点,检查该点是否在另一个矩形内.位于另一个矩形内的点数与重叠区域的面积相当接近.增加点的密度会提高计算的准确性,但会牺牲性能.

Divide one of your rectangles up into grids of small squares. For each intersection point, check if that point is inside the other rectangle. The number of points that lie inside the other rectangle will be a fairly good approximation to the area of the overlapping region. Increasing the density of points will increase the accuracy of the calculation, at the cost of performance.

这篇关于两个旋转矩形的相交面积的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆