您现在的位置是：首页 > Python

当前栏目

python中交集_Python中的区域交集

Python

2023-02-26 12:36:42 时间

![Image 1][]

I have a code that takes a condition C as an input, and computes the solution to my problem as an 'allowed area' A on the (x,y) space. This area is made of several 'tubes', which are defined by 2 lines that can never cross.

The final result I'm looking for must satisfy k conditions \{C1, .., Ck\}, and is therefore an intersection S between k areas \{A1, .. , Ak\}.

Here is an example with 2 conditions (A1: green, 3 tubes. A2: purple, 1 tube); the solution S is in red.

![Image 1][]

How can I find S when I'm dealing with 4 areas of around 10 tubes each? (The final plot is awful!)

I would need to be able to plot it, and to find the mean coordinate and the variance of the points in S (variance of each coordinate). \[If there is an efficient way of knowing whether a point P belongs to S or not, I’ll just use a Monte Carlo method\].

Ideally, I’d also like to be able to implement “forbidden tubes” that I would remove from S \[it might be a bit more complicated than intersecting S with the outside of my forbidden area, since two tubes from the same area can cross (even if the lines defining a tube never cross)\].

Note:

The code also stores the arc length of the lines.

The lines are stored as arrays of points (around 1000 points per line). The two lines defining a tube do not necessarily have the same number of points, but Python can interpolate ALL of them as a function of their arc length in 1 second.

The lines are parametric functions (i.e. we cannot write y = f(x), since the lines are allowed to be vertical).

The plot was edited with paint to get the result on the right... Not very efficient!

Edit:

I don't know how I can use plt.fill\_between for a multiple intersection (I can do it here for 2 conditions, but I need the code to do it automatically when there are too many lines for eye judgement).

For now I just generate the lines. I didn’t write anything for finding the final solution since I absolutely don’t know which structure is the most adapted for this. \[However, a previous version of the code was able to find the intersection points between the lines of 2 different tubes, and I was planning to pass them as polygons to shapely, but this implied several other problems..\]

I don't think I can do it with sets: scanning the whole (x,y) area at required precision represents around 6e8 points... \[The lines have only 1e3 points thanks to a variable step size (adapts to the curvature), but the whole problem is quite large\]

解决方案

Problem solved with Shapely!

I defined each tube as a Polygon, and an area A is a MultiPolygon object built as the union of its tubes.

The intersection method then computes the solution I was looking for (the overlap between all areas).

The whole thing is almost instantaneous. I didn't know shapely was so good with large objects \[around 2000 points per tube, 10 tubes per area, 4 areas\].

Thank you for your help! :)

Edit:

A working example.

import matplotlib.pyplot as plt

import shapely

from shapely.geometry import Polygon

from descartes import PolygonPatch

import numpy as np

def create\_tube(a,height):

x\_tube\_up = np.linspace(-4,4,300)

y\_tube\_up = a\*x\_tube\_up\*\*2 + height

x\_tube\_down = np.flipud(x\_tube\_up) \#flip for correct definition of polygon

y\_tube\_down = np.flipud(y\_tube\_up - 2)

points\_x = list(x\_tube\_up) + list(x\_tube\_down)

points\_y = list(y\_tube\_up) + list(y\_tube\_down)

return Polygon(\[(points\_x\[i\], points\_y\[i\]) for i in range(600)\])

def plot\_coords(ax, ob):

x, y = ob.xy

ax.plot(x, y, '+', color='grey')

area\_1 = Polygon() \#First area, a MultiPolygon object

for h in \[-5, 0, 5\]:

area\_1 = area\_1.union(create\_tube(2, h))

area\_2 = Polygon()

for h in \[8, 13, 18\]:

area\_2 = area\_2.union(create\_tube(-1, h))

solution = area\_1.intersection(area\_2) \#What I was looking for

\#\#\#\#\#\#\#\#\#\# PLOT \#\#\#\#\#\#\#\#\#\#

fig = plt.figure()

ax = fig.add\_subplot(111)

for tube in area\_1:

plot\_coords(ax, tube.exterior)

patch = PolygonPatch(tube, facecolor='g', edgecolor='g', alpha=0.25)

ax.add\_patch(patch)

for tube in area\_2:

plot\_coords(ax, tube.exterior)

patch = PolygonPatch(tube, facecolor='m', edgecolor='m', alpha=0.25)

ax.add\_patch(patch)

for sol in solution:

plot\_coords(ax, sol.exterior)

patch = PolygonPatch(sol, facecolor='r', edgecolor='r')

ax.add\_patch(patch)

plt.show()

And the plot :

![Image 1][]

[Image 1]:

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

python中交集_Python中的区域交集

相关文章