Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

algorithm - Area of Intersection of Two Rotated Rectangles

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. Rectangle intersection

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: So many possible intersection shapes

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

To supplement the other answers, your problem is an instance of line clipping, a topic heavily studied in computer graphics, and for which there are many algorithms available. If you rotate your coordinate system so that one rectangle has a horizontal edge, then the problem is exactly line clipping from there on.

You could start at the Wikipedia article on the topic, and investigate from there.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...