python - 从我这边检查具有 is_valid 属性、错误或误解的 shapely.geometry.LinearRing 对象的有效状态？

Question

我目前正在开发一个软件，它正在做大量的空间分析并检查整体，如果用户做了一些不鼓励的事情。为了检查多边形(没有内部顶点的线性环)的有效性，我从多边形的内部表示生成了一个 shapely.geometry.LinearRing，然后调用 .is_valid 属性来验证多边形不是自相交的。但是现在我从有效性检查中得到了几次 True，而多边形肯定是自相交的。这是一些示例代码，其中包含在我的软件中生成的数据和有效性检查。它应该是无效的并返回 False 但 .is_valid 属性无论如何都会返回 True。

import matplotlib.pyplot as plt
import shapely.geometry as shapely
xys = [[-7044436.526761845, -6928508.258940633, -6815051.336244647, -6703146.966617885, -6592140.871335315, -6481544.595369964, -6370982.963770309, -6260161.781757496, -6148846.223836629, -6036848.864941996, -5924011.123964341, -5810207.045486253, -5695332.232988797, -5579294.784593624, -5462020.995414686, -5343449.26168384, -5223530.449028691, -5102219.968445868, -4979482.944336143, -4855291.198143884, -4729620.475452479, -4602456.880845431, -4473786.128288798, -4343600.958552312, -4211900.369990507, -4078680.8368744757, -3943941.855063559, -3807692.5335005377, -3669942.2995267734, -3530702.502766562, -3389982.314641361, -3247804.334497555, -3104183.650190802, -2959138.1871592007, -2812690.7664734926, -2664867.2753160493, -2515702.98447352, -2365205.043449827, -2213421.247560168, -2060376.979801979, -1906101.5838065075, -1750632.9673780655, -1594021.9919117908, -1436289.7298125022, -1277466.8240309744, -1117620.7984790565, -956764.2561020661, -794957.3389015212, -632235.1993619861, -608778.4652757145, -608778.4652757145, -498615.0087172238, -390343.8721459261, -283969.9808692351, -179491.81403265087, -76906.84001498313, 23789.16438893977, 122603.11572499777, 219546.20259760926, 314632.2755276574, 407880.389639708, 499313.0249901432, 588959.6186170948, 676853.9962477403, 763038.1954950078, 847564.5929742546, 900122.4450862339, 900122.4450862339, 773244.857264079, 644957.8478748687, 515241.9040373244, 384080.4993801354, 251465.0403807161, 117390.46387334542, -18144.613935300553, -155143.08731398365, -293598.59916417854, -433505.858928101, -574849.1980484114, -717619.2732907499, -861801.6256419313, -1007376.0516687161, -1154322.267946724, -1302619.8071193092, -1452247.8400125655, -1603178.2903836588, -1755381.7709605244, -1908827.2608568808, -2063481.7280579286, -2219316.6680430933, -2376293.8944586893, -2534378.8423033436, -2693533.1362545746, -2853713.9517778317, -3014887.7590718567, -3177008.2200262756, -3340029.770790889, -3503914.137425141, -3668607.8471818846, -3834077.3672738583, -4000264.8377933884, -4167130.117325533, -4334620.80497111, -4502685.250853787, -4671271.016928122, -4840323.23369933, -5009796.318895331, -5179637.942230399, -5349787.116153195, -5520197.80341782, -5690809.58225879, -5861582.238956066, -6032442.172659639, -6203351.398881212, -6374219.683394053, -6544993.348431234, -6715612.468467643, -6886024.901228572, -7056186.347791059, -7226030.481358414, -7395515.449918765, -7564580.268497791, -7733165.830237391, -7901234.76587282, -8068729.757425987, -8235599.992459818, -8401806.110255126, -8567289.786427954, -8732009.016404705, -8895913.87381616, -9058957.610693472, -9221100.445116611, -9382294.422314912, -9542502.492436972, -9701673.336689195, -9859782.668949654, -10016781.23029244, -10172644.25903544, -10327327.77500867, -10480797.41555577, -10633024.61834202, -10783976.164057229, -10933633.350773294, -10958012.37496287, -10958012.37496287, -10814327.087910742, -10672076.72500343, -10531282.707885368, -10391955.378111733, -10254112.876233086, -10117765.253983192, -9982919.57541135, -9849578.910908908, -9717744.07125275, -9587417.363683863, -9458587.33776393, -9331247.357100876, -9205385.001219783, -9080981.180053458, -8958009.355143448, -8836440.424477525, -8716237.855311519, -8597355.000616068, -8479736.881934078, -8363316.180173276, -8248015.718897091, -8133740.220146316, -8020376.669841812, -7907784.354567285, -7795798.454818091, -7684214.904192161, -7572779.825524098, -7461173.389270281, -7348985.694270999, -7235678.94763268, -7120521.339018975, -7044436.526761845], [3641536.513666382, 4075435.0564746237, 4483464.585515801, 4869847.343969373, 5237621.918244451, 5589080.84837953, 5926007.041227836, 6249819.870926301, 6561672.344699762, 6862509.887262063, 7153138.789568509, 7434229.30864993, 7706355.991836379, 7970026.918401042, 8225676.468494094, 8473685.449899241, 8714385.178733313, 8948077.288096355, 9175026.013586497, 9395467.077474907, 9609614.719098194, 9817652.7738721, 10019754.67279037, 10216072.368103156, 10406739.62954536, 10591885.833255, 10771628.018964808, 10946063.533998027, 11115283.763263868, 11279372.324263146, 11438410.068030007, 11592458.036754962, 11741581.79893609, 11885839.663325233, 12025281.388131073, 12159950.816786723, 12289881.074003158, 12415126.816033946, 12535705.5084883, 12651651.614695229, 12762993.847383985, 12869752.784863308, 12971939.514405122, 13069583.459019937, 13162704.96217311, 13251302.16629012, 13335403.329213142, 13415009.374509538, 13490133.54346173, 13500561.462382779, 13500561.462382779, 13261418.395199591, 13015733.715886055, 12763304.449193865, 12503897.997383105, 12237262.394138278, 11963123.081708971, 11681178.189125571, 11391091.123239528, 11092491.820565185, 10784965.17843093, 10468052.125596058, 10141232.386400146, 9803927.053889815, 9455477.365124423, 9095125.90048115, 8861020.31004521, 8861020.31004521, 9077082.631092394, 9286897.206493828, 9490650.069276033, 9688511.35386954, 9880629.169477722, 10067137.910536844, 10248159.01622917, 10423808.461090825, 10594183.404860727, 10759376.475941187, 10919462.799781717, 11074520.169628361, 11224615.899785472, 11369807.350477818, 11510148.411537807, 11645689.371865612, 11776476.7731109, 11902547.84503696, 12023936.477011891, 12140673.15614324, 12252784.93382456, 12360300.117055546, 12463238.366650142, 12561620.345158778, 12655462.794941416, 12744778.758346, 12829585.234923325, 12909891.07869414, 12985705.023524193, 13057038.236846052, 13123894.397249624, 13186284.600531755, 13244209.65576361, 13297676.375622686, 13346686.69152079, 13391242.58747428, 13431345.606201014, 13466996.591642585, 13498197.97928208, 13524950.21671903, 13547252.412358446, 13565105.611792633, 13578508.892881691, 13587462.594396902, 13591964.95158364, 13592015.558875483, 13587614.129824113, 13578761.545508161, 13565458.990361733, 13547707.136207346, 13525505.127890784, 13498854.64332302, 13467753.682925688, 13432203.085427992, 13392203.854504853, 13347751.428259624, 13298845.480031863, 13245483.873395007, 13187660.013406465, 13125373.138355374, 13058616.27197932, 12987384.800397633, 12911672.368054153, 12831468.534393102, 12746765.949049367, 12657550.755483333, 12563816.155195003, 12465538.441157172, 12362707.524267457, 12255296.254348202, 12143288.681802807, 12026661.0772235, 11905383.41124563, 11779427.26103856, 11648749.650505286, 11626900.612400476, 11626900.612400483, 11477428.382419439, 11323020.161298824, 11163617.044940721, 10999143.550739052, 10829528.649809506, 10654687.011683974, 10474523.922115441, 10288933.080397902, 10097798.05991723, 9900997.45808413, 9698380.977144761, 9489796.11617138, 9275071.373114077, 9054012.805114817, 8826400.311106827, 8591994.591663523, 8350526.417327361, 8101688.247136375, 7845134.3548644725, 7580468.464224364, 7307244.904019261, 7024944.345886712, 6732967.396070254, 6430600.440159499, 6117014.119117039, 5791209.497033343, 5451969.242376988, 5097785.351218174, 4726751.706809799, 4336396.514931011, 3923393.0373139796, 3641536.513666382]]
shape = shapely.LinearRing([(x,y) for x,y in zip(xys[0], xys[1])])
print(shape.is_valid) 
plt.plot(xys[0],xys[1])
plt.show()

Answer 1

这是一个 well-known bug它似乎不会在不久的将来修复。
但是，如果您想检查轮廓是否自相交，我可以推荐您 contour_self_intersects predicate的 bentley_ottmann package可以像这样使用

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Contour = context.point_cls, context.contour_cls
>>> contour = Contour([Point(x, y) in zip(*xys)])
>>> from bentley_ottmann.planar import contour_self_intersects
>>> contour_self_intersects(contour)
True

它基于 sweep line algorithm ，经过良好测试，应该可以在 O(n log n) 中工作哪里 n是顶点数。