查找由一组线创建的平面的所有分区

Question

我有一组线(形式为y = mx + b的线性函数)(其中120个!),如果我将它们全部绘制出来,那么它们会对R ^ 2平面进行分区.线条不一定经过原点.

查找由一组这样的行创建的所有分区的最有效方法是什么？就个人而言,我很难想出任何方式,更不用说有效率了.为了更清楚,我包括以下只有4行的图像:

分区的示例是集合{(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7},其是由第一象限中的红色,黄色和绿色线创建的分区.另一个例子是{(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2},第一象限中的三角形由蓝色,红色和绿色线界定.

非分区的一个例子是{(x,y)|5x+3 <= y <= -30x+28},由上面的绿线和下面的蓝线界定的集合.这不是分区,因为其中包含多个分区(例如,上面的第二个集合),或者重叠它.{(x,y)|5x+3 <= y <= -30x+28 && 90x+7 <= y}但是,该集合将是一个分区.

所需的输出将是这些集合的完整列表: {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2},{(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}...当然,它们不必以这种表示法给出.

我不确定如何处理这个问题,所以,不幸的是,不能提供我尝试过的方式.理想情况下,我想在R,Python,Mathematica或MATLAB中执行此操作,但此时我对任何选项都持开放态度.

编辑:由于似乎存在符号问题,我会稍微澄清一下.简单地获得点上的条件列表就足够了,这样满足该条件的所有点都将精确地定义分区.例如,一长串的交叉点就可以了:y <= 5x+3 && y >= 90x+7 && y<= -30x+28定义分区的输出非常好.当然,期望的输出是这种分区的完整列表(如上所定义).

Answer 1

这是 Mathematica 中的解决方案。该方法包括找到线的交点、线片段，然后是分区，同时跟踪这些点连接到哪些线。

\n\n

y[1] = 5 x + 3;\ny[2] = 90 x + 7;\ny[3] = -30 x + 28;\ny[4] = 60 x + 2;\n\nfindpoints[n_] := Module[{},\n  xp = DeleteCases[{{First[#1], First[#2]},\n       Solve[Last[#1] == Last[#2], x]} & @@@\n     DeleteCases[\n      Tuples[Array[{#, y[#]} &, n], 2],\n      {{x_, _}, {x_, _}}], {_, {}}];\n  yp = y[#[[1, 1]]] /. #[[2, 1]] & /@ xp;\n  MapThread[{#1, {#2, #3}} &,\n   {xp[[All, 1]], xp[[All, 2, 1, 1, 2]], yp}]]\n\nxyp = findpoints[4];\n\n{xmin, xmax} = Through[{Min, Max}@\n    xyp[[All, 2, 1]]] + {-0.7, 0.7};\n\nouters = Flatten[Array[Function[n,\n     MapThread[List[{{n, 0}, {##}}] &,\n      {{xmin, xmax}, y[n] /.\n    List /@ Thread[x -> {xmin, xmax}]}]], 4], 2];\n\nxyp = Join[outers, xyp];\n\nfindlines[p_] := Module[{},\n  pt = DeleteCases[\n    Cases[xyp, {{p[[1, 1]], _}, _}], p];\n  n = First@Cases[pt,\n     {_, First@Nearest[Last /@ pt, Last[p]]}];\n  {{First[p], First[n]}, {Last[p], Last[n]}}]\n\nlines = Map[findlines, xyp];\n\n(* boundary lines *)\n{ymin, ymax} = Through[{Min, Max}@outers[[All, 2, 2]]];\n{lbtm, rbtm, ltop, rtop} = {{xmin, ymin},\n   {xmax, ymin}, {xmin, ymax}, {xmax, ymax}};\nxminlines = Partition[Union@Join[{ymin, ymax},\n      Cases[xyp, {_, {xmin, _}}][[All, 2, 2]]], 2, 1] /.\n   x_Real :> {xmin, x};\nxmaxlines = Partition[Union@Join[{ymin, ymax},\n      Cases[xyp, {_, {xmax, _}}][[All, 2, 2]]], 2, 1] /. \n   x_Real :> {xmax, x};\nlines2 = Join[Last /@ lines, xminlines, xmaxlines,\n   {{lbtm, rbtm}}, {{ltop, rtop}}];\n\nListLinePlot[lines2]\n

\n\n

\n\n

(* add vertex points *)\nxyp2 = Join[xyp, {\n   {{SortBy[Cases[outers, {_, {xmin, _}}],\n       Last][[-1, 1, 1]], -1}, ltop},\n   {{SortBy[Cases[outers, {_, {xmax, _}}],\n       Last][[-1, 1, 1]], -1}, rtop},\n   {{SortBy[Cases[outers, {_, {xmin, _}}],\n       Last][[1, 1, 1]], -1}, lbtm},\n   {{SortBy[Cases[outers, {_, {xmax, _}}],\n       Last][[1, 1, 1]], -1}, rbtm}}];\n\nanglecalc[u_, v_] := Mod[(ArcTan @@ u) - (ArcTan @@ v), 2 \xcf\x80]\n\ngetlineangles[] := Module[{},\n  (* find the angles from current line\n     to all the linked lines *)\n  angle = Map[\n    anglecalc[{c, d} - {g, h}, # - {g, h}] &,\n    union = DeleteCases[Union@Join[\n        Last /@ Cases[lines2, {{g, h}, _}],\n        First /@ Cases[lines2, {_, {g, h}}]],\n      {c, d}]];\n  Sort[Transpose[{N@angle, union}]]]\n\ngetpolygon[pt_, dir_] := Module[{},\n  Clear[p];\n  p[n = 1] = {{a, b}, {c, d}} = pt;\n  (* find the angles from vector (0, -1) or (0, 1)\n     to all the linked lines *)\n\n  angle = Map[anglecalc[If[dir == 1, {0, -1}, {0, 1}], # - {c, d}] &,\n    union = Union@Join[\n       Last /@ Cases[lines2, {{c, d}, _}],\n       First /@ Cases[lines2, {_, {c, d}}]]];\n  lineangles = Sort[Transpose[{N@angle, union}]];\n  (* next point *)\n  p[++n] = {{e, f}, {g, h}} = First@\n     Cases[xyp2, {_, lineangles[[1, 2]]}];\n\n  While[Last[p[n]] != Last[p[1]],\n   lineangles = getlineangles[];\n   (* reset first point *)\n   {{a, b}, {c, d}} = {{e, f}, {g, h}};\n   (* next point *)\n   p[++n] = {{e, f}, {g, h}} = First@\n      Cases[xyp2, {_, lineangles[[1, 2]]}]];\n\n  Array[p, n]]\n\nlen = Length[xyp];\n\npolygons = Join[Array[(poly[#] = getpolygon[xyp[[#]], 1]) &, len],\n   Array[(poly[# + len] = getpolygon[xyp[[#]], 2]) &, len]];\n\ngraphics = DeleteDuplicates /@ Array[Last /@ poly[#] &, 2 len];\n\nsortedgraphics = Sort /@ graphics;\n\npositions = Map[Position[sortedgraphics, #] &,\n    DeleteDuplicates[sortedgraphics]][[All, 1, 1]];\n\nunique = poly /@ positions;\n\npoly2 = unique[[All, All, 2]];\n\npoly2 = Delete[poly2,\n   Array[If[Length[Intersection[poly2[[#]],\n         Last /@ Take[xyp2, -4]]] == 4, {#}, Nothing] &,\n    Length[poly2]]];\n\nlen2 = Length[poly2];\n\npoly3 = Polygon /@ Rest /@ poly2;\n\nArray[(centroid[#] = RegionCentroid[poly3[[#]]]) &, len2];\n\nShow[Graphics[Array[{ColorData[24][#],\n     poly3[[#]]} &, len2], AspectRatio -> 1/GoldenRatio],\n Graphics[Array[Text[#, centroid[#]] &, len2]]]\n

\n\n

\n\n

unique2 = Extract[unique,\n   Flatten[Position[unique[[All, All, 2]], #] & /@ poly2, 1]];\n\nmakerelations[oneconnection_, areanumber_] := Module[{i},\n  If[Intersection @@ oneconnection == {} ||\n    (i = First[Intersection @@ oneconnection]) < 1,\n   Nothing,\n   centroidx = First[centroid[areanumber]];\n   linepos = y[i] /. x -> centroidx;\n   relation = If[linepos < Last[centroid[areanumber]],\n     " >= ", " < "];\n   string = StringJoin["y", relation, ToString[y[i]]]]]\n\nfindrelations[n_] := Module[{},\n  areanumber = n;\n  onearea = unique2[[areanumber]];\n  connections = Partition[First /@ onearea, 2, 1];\n  strings = DeleteDuplicates@\n    Map[makerelations[#, areanumber] &, connections];\n  StringJoin["Area ", ToString[areanumber],\n   If[areanumber > 9, ": ", ":  "],\n   StringRiffle[strings, " &&\\n         "]]]\n\nShow[Plot[Evaluate@Array[y, 4], {x, -1, 1.5},\n  PlotLegends -> "Expressions", Axes -> None],\n Graphics[Array[Text[#, centroid[#]] &, len2]]]\n\nColumn@Array[findrelations, len2]\n

\n\n

\n\n

\n

Area 1:  y >= 28 - 30 x &&\n         y < 3 + 5 x\nArea 2:  y >= 2 + 60 x &&\n         y >= 28 - 30 x &&\n         y < 7 + 90 x\nArea 3:  y < 28 - 30 x &&\n         y < 7 + 90 x &&\n         y < 2 + 60 x &&\n         y < 3 + 5 x\nArea 4:  y >= 3 + 5 x &&\n         y >= 28 - 30 x &&\n         y < 2 + 60 x\nArea 5:  y < 3 + 5 x &&\n         y >= 2 + 60 x &&\n         y < 7 + 90 x\nArea 6:  y < 28 - 30 x &&\n         y >= 2 + 60 x &&\n         y >= 3 + 5 x &&\n         y < 7 + 90 x\nArea 7:  y < 28 - 30 x &&\n         y >= 3 + 5 x &&\n         y < 2 + 60 x\nArea 8:  y < 28 - 30 x &&\n         y >= 7 + 90 x &&\n         y >= 3 + 5 x\nArea 9:  y < 2 + 60 x &&\n         y >= 7 + 90 x\nArea 10: y >= 28 - 30 x &&\n         y >= 7 + 90 x\nArea 11: y < 3 + 5 x &&\n         y >= 7 + 90 x &&\n         y >= 2 + 60 x\n

\n

\n