找到一组交叉点中的所有四边形
Dou*_*ell 3 language-agnostic theory math geometry
我想取一组线的所有交点,找到它们创建的所有凸四边形.我不确定是否有适合这种情况的算法,或者我需要循环创建自己的算法.
我有一系列线条和所有交叉点.
线和交叉点:
示例四边形1:
示例四边形2
在这种情况下,我会提出8个四边形.
我怎样才能做到这一点？如果没有我可以为此实现的算法,我如何检查每个交叉点与其他交叉点以确定它们是否形成凸四边形？
有一个简单的,非快速的,强力的全部算法来找到那些四边形.但是,首先你需要澄清一些定义,特别是"四边形"的定义.如果它的面积为零,你是否将其视为四边形,例如当所有顶点都是共线时？如果它自相交或交叉,你会把它算作四边形吗？如果它不凸出你算吗？如果两个相邻边是直的(包括连续的顶点相同),你算一算吗？如果多边形"双重"自身,那么结果看起来像三角形,一边延伸？
这是一个顶级算法:考虑一次四个线段的所有组合.如果有n线段,则有n*(n-1)*(n-2)*(n-3)/24组合.对于每个组合,请查看这些段对的交叉点:最多将有6个交叉点.现在看看你是否可以从这些交叉点和段中制作四边形.
这是暴力,但至少它是执行时间的多项式,O(n ^ 4).对于8个线段的例子,这意味着要考虑70个段的组合 - 不是太糟糕.这可以通过预先计算交点来加速:n*(n-1)/2在你的例子中,它们中最多只有28个.
这个整体算法是否满足您的需求？你的最后一个问题是"我怎样才能检查每个交叉路口与其他交叉路口是否能形成四边形？" 询问如何实施我的陈述"看看你是否可以从这些交叉点和段中制作四边形"？你还需要答案吗？在我回答这个问题之前,你需要澄清你对四边形的定义.
我将更多地解释"四边形"的定义.该图显示了"一般位置"的四个线段,其中每个线段与所有其他线段相交,并且没有三个线段在同一点相交.
这里是(一些)由这四个线段和六个交叉点产生的"四边形".
- 1简单和凸(ABDE)
- 1简单而不凸(ACDF)
- 1交叉(BCEF)
- 4个三角形,在三角形的一侧有一个额外的顶点(ABCE,ACDE,ABDF,ABFE).请注意,前两个定义具有不同顶点的相同区域,并且前两个定义相同.
- 4个"双背",看起来像一个三角形,一边延伸(ACEF,BCDF,BDEF,CDEF)
根据您定义"四边形"和"相等"的方式,您可以在该图中获得1到11个任意位置.维基百科的定义只包括我的列表中的第一个,第二个和第四个 - 我不确定这是如何计算我的第四组中的"重复".我甚至不确定我是否在图表中找到了所有可能性,因此可能会有更多.
我看到我们现在正在定义一个四边形,如四个不同的线段所示,它们是给定线段的子段,形成严格凸出的多边形 - 顶角都小于直角.这仍然会在一些边缘情况下留下一个模糊性 - 如果两个线段重叠超过一个点会怎么样 - 但是除了定义两个这样的线段没有交叉点之外,让我们把它放在一边.然后这个算法,基于Python的伪代码,应该工作.
我们需要一个函数intersection_point(seg1, seg2)来返回两个给定线段的交点,或者None如果没有或者段重叠.我们还需要一个函数polygon_is_strictly_convex(tuple of points)返回True或者False取决于如果点的元组定义了一个严格的凸多边形,而另外,如果任何一个点被None然后False返回.这两个函数都是计算几何中的标准函数.需要注意的是"组合"在以下意味着每个返回组合中的项目都在有序的,所以(seg1, seg2)和(seg2, seg1)我们会得到完全其中之一.Python itertools.combinations()很好地做到了这一点.
intersections = {} # empty dictionary/hash table
for each combination (seg1, seg2) of given line segments:
intersections[(seg1, seg2)] = intersection_point(seg1, seg2)
quadrilaterals = emptyset
for each combination (seg1, seg2, seg3, seg4) of given line segments:
for each tuple (sega, segb, segc, segc) in [
(seg1, seg2, seg3, seg4),
(seg1, seg2, seg4, seg3),
(seg1, seg3, seg2, seg4)]:
a_quadrilateral = (intersections[(sega, segb)],
intersections[(segb, segc)],
intersections[(segc, segd)],
intersections[(segd, sega)])
if polygon_is_strictly_convex(a_quadrilateral):
quadrilaterals.add(a_quadrilateral)
break # only one possible strictly convex quad per 4 segments
这是我实际测试的Python 3.6代码,它为您的段提供了八个多边形.首先,这里是实用程序,几何例程,收集到模块中rdgeometry.
def segments_intersection_point(segment1, segment2):
"""Return the intersection of two line segments. If none, return
None.
NOTES: 1. This version returns None if the segments are parallel,
even if they overlap or intersect only at endpoints.
2. This is optimized for assuming most segments intersect.
"""
try:
pt1seg1, pt2seg1 = segment1 # points defining the segment
pt1seg2, pt2seg2 = segment2
seg1_delta_x = pt2seg1[0] - pt1seg1[0]
seg1_delta_y = pt2seg1[1] - pt1seg1[1]
seg2_delta_x = pt2seg2[0] - pt1seg2[0]
seg2_delta_y = pt2seg2[1] - pt1seg2[1]
denom = seg2_delta_x * seg1_delta_y - seg1_delta_x * seg2_delta_y
if denom == 0.0: # lines containing segments are parallel or equal
return None
# solve for scalars t_seg1 and t_seg2 in the vector equation
# pt1seg1 + t_seg1 * (pt2seg1 - pt1seg1)
# = pt1seg2 + t_seg2(pt2seg2 - pt1seg2) and note the segments
# intersect iff 0 <= t_seg1 <= 1, 0 <= t_seg2 <= 1 .
pt1seg1pt1seg2_delta_x = pt1seg2[0] - pt1seg1[0]
pt1seg1pt1seg2_delta_y = pt1seg2[1] - pt1seg1[1]
t_seg1 = (seg2_delta_x * pt1seg1pt1seg2_delta_y
- pt1seg1pt1seg2_delta_x * seg2_delta_y) / denom
t_seg2 = (seg1_delta_x * pt1seg1pt1seg2_delta_y
- pt1seg1pt1seg2_delta_x * seg1_delta_y) / denom
if 0 <= t_seg1 <= 1 and 0 <= t_seg2 <= 1:
return (pt1seg1[0] + t_seg1 * seg1_delta_x,
pt1seg1[1] + t_seg1 * seg1_delta_y)
else:
return None
except ArithmeticError:
return None
def orientation3points(pt1, pt2, pt3):
"""Return the orientation of three 2D points in order.
Moving from Pt1 to Pt2 to Pt3 in cartesian coordinates:
1 means counterclockwise (as in standard trigonometry),
0 means straight, back, or stationary (collinear points),
-1 means counterclockwise,
"""
signed = ((pt2[0] - pt1[0]) * (pt3[1] - pt1[1])
- (pt2[1] - pt1[1]) * (pt3[0] - pt1[0]))
return 1 if signed > 0.0 else (-1 if signed < 0.0 else 0)
def is_convex_quadrilateral(pt1, pt2, pt3, pt4):
"""Return True if the quadrilateral defined by the four 2D points is
'strictly convex', not a triangle nor concave nor self-intersecting.
This version allows a 'point' to be None: if so, False is returned.
NOTES: 1. Algorithm: check that no points are None and that all
angles are clockwise or all counter-clockwise.
2. This does not generalize to polygons with > 4 sides
since it misses star polygons.
"""
if pt1 and pt2 and pt3 and pt4:
orientation = orientation3points(pt4, pt1, pt2)
if (orientation != 0 and orientation
== orientation3points(pt1, pt2, pt3)
== orientation3points(pt2, pt3, pt4)
== orientation3points(pt3, pt4, pt1)):
return True
return False
def polygon_in_canonical_order(point_seq):
"""Return a polygon, reordered so that two different
representations of the same geometric polygon get the same result.
The result is a tuple of the polygon's points. `point_seq` must be
a sequence of 'points' (which can be anything).
NOTES: 1. This is intended for the points to be distinct. If two
points are equal and minimal or adjacent to the minimal
point, which result is returned is undefined.
"""
pts = tuple(point_seq)
length = len(pts)
ndx = min(range(length), key=pts.__getitem__) # index of minimum
if pts[(ndx + 1) % length] < pts[(ndx - 1) % length]:
return (pts[ndx],) + pts[ndx+1:] + pts[:ndx] # forward
else:
return (pts[ndx],) + pts[:ndx][::-1] + pts[ndx+1:][::-1] # back
def sorted_pair(val1, val2):
"""Return a 2-tuple in sorted order from two given values."""
if val1 <= val2:
return (val1, val2)
else:
return (val2, val1)
这是我算法的代码.我添加了一点复杂性,只使用一对线段的"规范形式"和多边形,以减少交叉点和多边形容器的内存使用.
from itertools import combinations
from rdgeometry import segments_intersection_point, \
is_strictly_convex_quadrilateral, \
polygon_in_canonical_order, \
sorted_pair
segments = [(( 2, 16), (22, 10)),
(( 4, 4), (14, 14)),
(( 4, 6), (12.54, 0.44)),
(( 4, 14), (20, 6)),
(( 4, 18), (14, 2)),
(( 8, 2), (22, 16))]
intersections = dict()
for seg1, seg2 in combinations(segments, 2):
intersections[sorted_pair(seg1, seg2)] = (
segments_intersection_point(seg1, seg2))
quadrilaterals = set()
for seg1, seg2, seg3, seg4 in combinations(segments, 4):
for sega, segb, segc, segd in [(seg1, seg2, seg3, seg4),
(seg1, seg2, seg4, seg3),
(seg1, seg3, seg2, seg4)]:
a_quadrilateral = (intersections[sorted_pair(sega, segb)],
intersections[sorted_pair(segb, segc)],
intersections[sorted_pair(segc, segd)],
intersections[sorted_pair(segd, sega)])
if is_strictly_convex_quadrilateral(*a_quadrilateral):
quadrilaterals.add(polygon_in_canonical_order(a_quadrilateral))
break # only one possible strictly convex quadr per 4 segments
print('\nThere are {} strictly convex quadrilaterals, namely:'
.format(len(quadrilaterals)))
for p in sorted(quadrilaterals):
print(p)
打印出来的是:
There are 8 strictly convex quadrilaterals, namely:
((5.211347517730497, 5.211347517730497), (8.845390070921987, 2.8453900709219857), (11.692307692307693, 5.692307692307692), (9.384615384615383, 9.384615384615383))
((5.211347517730497, 5.211347517730497), (8.845390070921987, 2.8453900709219857), (14.666666666666666, 8.666666666666668), (10.666666666666666, 10.666666666666666))
((5.211347517730497, 5.211347517730497), (8.845390070921987, 2.8453900709219857), (17.384615384615387, 11.384615384615383), (12.769230769230768, 12.76923076923077))
((6.0, 14.8), (7.636363636363637, 12.181818181818182), (10.666666666666666, 10.666666666666666), (12.769230769230768, 12.76923076923077))
((6.0, 14.8), (7.636363636363637, 12.181818181818182), (14.666666666666666, 8.666666666666668), (17.384615384615387, 11.384615384615383))
((9.384615384615383, 9.384615384615383), (10.666666666666666, 10.666666666666666), (14.666666666666666, 8.666666666666668), (11.692307692307693, 5.692307692307692))
((9.384615384615383, 9.384615384615383), (11.692307692307693, 5.692307692307692), (17.384615384615387, 11.384615384615383), (12.769230769230768, 12.76923076923077))
((10.666666666666666, 10.666666666666666), (12.769230769230768, 12.76923076923077), (17.384615384615387, 11.384615384615383), (14.666666666666666, 8.666666666666668))