W*********y
发帖数: 481 | 1 平面上一个polygon，用point的数组表示，顺序链接而成。
一条平面线段，用两个point表示。
求这条线段包含在polygon interior内部的所有segment部分。 注意可能有多段
segment的情况。
看下图的例子，输入线段为A B 坐标，应该返回 [[C,D], [E,F]] 的坐标
http://tinyurl.com/lbcmxrp |
d******e
发帖数: 2265 | 2 算出线段的角度，然后算夹角，二分找到两个相交的线段。
最后判断是否相交。
否则可以用简单o(n) naive算法。
谷歌这些小trick真没劲。
【在 W*********y 的大作中提到】
: 平面上一个polygon，用point的数组表示，顺序链接而成。
: 一条平面线段，用两个point表示。
: 求这条线段包含在polygon interior内部的所有segment部分。 注意可能有多段
: segment的情况。
: 看下图的例子，输入线段为A B 坐标，应该返回 [[C,D], [E,F]] 的坐标
: http://tinyurl.com/lbcmxrp
|
C****t
发帖数: 53 | 3 两个线段四个端点。一个线段两个端点到另一线段距离的乘积小于等于0，反过来另一
条线段两个端点到第一条距离的乘积也要保证小于等于0。
【在 W*********y 的大作中提到】
: 平面上一个polygon，用point的数组表示，顺序链接而成。
: 一条平面线段，用两个point表示。
: 求这条线段包含在polygon interior内部的所有segment部分。 注意可能有多段
: segment的情况。
: 看下图的例子，输入线段为A B 坐标，应该返回 [[C,D], [E,F]] 的坐标
: http://tinyurl.com/lbcmxrp
|
W*********y
发帖数: 481 | 4 不好意思，我语文太差了，给您题意说错了。要求的是这条线段在polygon内部的所有
子部分。
我update了原帖，附上了个图例。
【在 d******e 的大作中提到】
: 算出线段的角度，然后算夹角，二分找到两个相交的线段。
: 最后判断是否相交。
: 否则可以用简单o(n) naive算法。
: 谷歌这些小trick真没劲。
|
W*********y
发帖数: 481 | 5 不好意思，我给您说错题意了。我更新了原帖附上了图例。抱歉！
【在 C****t 的大作中提到】
: 两个线段四个端点。一个线段两个端点到另一线段距离的乘积小于等于0，反过来另一
: 条线段两个端点到第一条距离的乘积也要保证小于等于0。
|
C****t
发帖数: 53 | 6 Then every segment to be checked. O(n)
for example, segment p1--p2, check if there is t in [0,1], such that p1*t+p2
*(1-t) is located on the given segment. Finally, might need to sort
regarding x or y. And still need to check whether the number of intersection
points is odd or even.
【在 W*********y 的大作中提到】
: 不好意思，我给您说错题意了。我更新了原帖附上了图例。抱歉！
|
t**r
发帖数: 3428 | |
W*********y
发帖数: 481 | 8 多谢，还有一种情况是输入的AB与某一段 p_i, p_{i+1} 共线，也不应该算作内部。
p2
intersection
【在 C****t 的大作中提到】
: Then every segment to be checked. O(n)
: for example, segment p1--p2, check if there is t in [0,1], such that p1*t+p2
: *(1-t) is located on the given segment. Finally, might need to sort
: regarding x or y. And still need to check whether the number of intersection
: points is odd or even.
|
