考虑一个“生活”在 2D 空间中且当前位于(0;0)的对象。
对象被两条主要限制线x=0和y=0包围，还被一堆附加线A x+B y=C包围（三元组A,B,C包含在一些N×3数组中。）
是否有一种简单的算法来删除多余的行？我在 MatLab 中有我的数据，它有一堆花哨的本机函数，但我仍然不太确定从哪里开始。
例如，在所有线A x+B y=C下方显示为蓝色，冗余线标记为红色。
.
问问题
94 次
2 回答
2
您需要简单还是高效？
最直接的算法将简单地构建对象，并排。在每一步，你都有一个点 p 和方向 v（一个向量）；假设您从 p = (0, 0) 和方向 v = (0, 1) 开始顺时针构建对象。在每一步，通过比较值 q 对所有线进行排序，使得 p + q * v 是线与 v 线相交的点（忽略平行线）。复杂度为 O(n^2 log n)。
于 2013-04-28T17:26:07.400 回答
1
扩展我的评论：对于每个非主线 Ax + By = C，让 A' = A/C 和 B' = B/C 以便线方程可以写成 A'x + B'y = 1。 （C = 0 需要一个我将忽略的特殊情况。）
现在计算对 (A', B') 的 2D 凸包。MATLABconvhull为此提供了；设置simplify为真。保留与船体右上四分之一点相对应的线。（逆时针方向，这一节的第一个点是最右边的，如果平局选择最上面。最后一个是最上点，如果平局则选择最右边。）
于 2013-04-28T20:40:29.953 回答