l*****c
发帖数: 52 | 1 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
by any angle.
2. How to determine if two given rectangle overlap with each other?
大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
应该还有更好的办法，当时也只能想出来这么多了。。。
估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
… |
f******s
发帖数: 17 | 2 graphics的背景？
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
|
l*****c
发帖数: 52 | 3 不是 面的都是kernel偏上一点的组……
【在 f******s 的大作中提到】
: graphics的背景？
:
: rotated
|
f******s
发帖数: 17 | 4 不是graphics考这个太偏了，是的话，考的又太简单。
【在 l*****c 的大作中提到】
: 不是 面的都是kernel偏上一点的组……
|
c********p
发帖数: 1969 | |
r*********n
发帖数: 4553 | 6 "While, if the given rectangles are rotated by any angle, my solution is to
check the corners of each rectangle. If one of them is inside of another
rectangle, these two rectangles overlap. Otherwise, they are not."
不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
里面，但是这两个长方形仍然相交。
我觉得判定不相交比判定相交容易些：
求出长方形A的四条边的直线方程，这四条边组成两组平行线
用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
同一侧（带入直线方程，符号一样），那么不相交。
否则互换A，B，然后再测试一下。
如果两次测试其中任何一次是“不相交”，那么A，B就不相交，否则A，B相交。
rotated
【在 l*****c 的大作中提到】
: 前两周去onsite面的一家公司，其中一道题是（签了disclosure，不好全发出来）
: 1. How to represent a rectangle in a 2D plane? The rectangle can be rotated
: by any angle.
: 2. How to determine if two given rectangle overlap with each other?
: 大概说思路+写代码用了半个小时，回来稍微整理了一下，下面是地址
: http://blog.theliuy.com/determine-if-two-rotated-rectangles-ove
: 应该还有更好的办法，当时也只能想出来这么多了。。。
: 估计下周出结果，求bless，本人新手还不知道包子怎么给（也不知道自己有没有）…
: …
|
l*****c
发帖数: 52 | 7 哦对 忘了这个情况了……
to
【在 r*********n 的大作中提到】
: "While, if the given rectangles are rotated by any angle, my solution is to
: check the corners of each rectangle. If one of them is inside of another
: rectangle, these two rectangles overlap. Otherwise, they are not."
: 不对吧，比如两个长方形组成十字架的形状，虽然没有任何一个角落在另外一个长方形
: 里面，但是这两个长方形仍然相交。
: 我觉得判定不相交比判定相交容易些：
: 求出长方形A的四条边的直线方程，这四条边组成两组平行线
: 用长方形B的四个角和A的两组平行线比较，如果存在一组平行线使得B的四个角都在其
: 同一侧（带入直线方程，符号一样），那么不相交。
: 否则互换A，B，然后再测试一下。
|
f****y
发帖数: 307 | 8 本人非码工，随便扯两句。
是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
（检查定点到中心点距离小的那个长方形）。 |
l*****c
发帖数: 52 | 9 非常感谢 感觉当时想的不够 所以给的解法也有不少问题
【在 f****y 的大作中提到】
: 本人非码工，随便扯两句。
: 是我的话长方形的表示是一个中心点，任意两个相邻顶点。根据这个能求出长方形四条
: 边方程。如果两个长方形有重合那要么是边有相交（求线段交点是否在线段内），要么
: 是一个长方型完全被包在另一个内部。可以通过看中心点是否在另一个长方形内来判断
: （检查定点到中心点距离小的那个长方形）。
|
c******o
发帖数: 534 | |
g**G
发帖数: 767 | |
l*****c
发帖数: 52 | 12 当时的想法和你的很类似，但六楼提了一个特例。
【在 c******o 的大作中提到】
: 看矩形a中的顶点是否在矩形b内
|
c******o
发帖数: 534 | 13 那把矩形按4个直线表示。
矩形a的4个顶点都应该在矩形b的4个直线的同一侧
【在 l*****c 的大作中提到】
: 当时的想法和你的很类似，但六楼提了一个特例。
|
