Mathematica:不相交的线段 [英] Mathematica: Non-intersecting line segments

问题描述

我们如何告诉 Mathematica 给我们一组非相交的线?在这种情况下，如果两条线有一个共同点(不是端点)，则它们相交.考虑以下简单情况:

How can we tell Mathematica to gives us a set of non-intersecting lines? In this case two lines intersect if they have a point (not an endpoint) in common. Consider this simple case:

l1 = {{-1, 0}, {1, 0}};
l2 = {{0, -1}, {0, 1}};
lines = {l1, l2};

这个想法是创建一个给定一组线的函数，该函数返回一组不相交的线.如果存在这样的功能，请说split，然后输出

The idea is to create a function which, given a set a lines, returns a set of non-intersecting lines. If such function exists say split then the output of

split[lines]

将会

{
 {{-1, 0}, {0,0}},
 {{ 0, 0}, {1,0}}, 
 {{ 0,-1}, {0,0}}, 
 {{ 0, 0}, {0,1}}
}

该函数检测到{0,0}是集合中两条线之间的交点，并且为了具有不相交的线，该函数在交点处断开了线段，因此又产生了2条线.如果原始输入包含更多行，则此过程将变得更加复杂.有谁知道如何在 Mathematica 中有效地执行此操作而不使用循环?了解一种算法来查找两行相交.

The function detected that {0,0} is the intersection between the two lines in the set and in order to have non-intersecting lines it broke the line segments at the intersections thus generating 2 more lines. This process gets more complicated if the original input contains more lines. Does anyone know how to do this efficiently in Mathematica without using loops? It might help to know an algorithm to find if two lines are intersecting.

注意

这个问题是我尝试找出如何在中制作线框的第二部分Mathematica (具有隐藏线删除功能).请随时添加更多合适的标签.

This question is the second part of my attempt to find out how to make wire frames in Mathematica with hidden line removal. Please feel free to add more appropriate tags.

推荐答案

如果假定存在拆分，则需要将其应用于所有对；这些可能是由

if you assume that split exists, you then need to apply it to all pairs; these may be produced by

ClearAll[permsnodups];
permsnodups[lp_] := DeleteDuplicates[Permutations[lp, {2}],
   ((#1[[1]] == #2[[1]]) &&(#1[[2]] == #2[[2]]) || 
   (#1[[1]] == #2[[2]]) && (#1[[2]] == #2[[1]])) &]

执行此操作:permsnodups[{a, b, c, d}]给出{{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}，您可以在其上映射split函数(即，这些都是成对的，请确保如果{a,b}存在，则{b,a}从那时起不存在)正在无缘无故地做两倍的工作-就像做$ \ sum_ {i，j> i} $而不是$ \ sum_ {i，j} $).

which does this: permsnodups[{a, b, c, d}] gives {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}, over which you could map your split function (ie these are all pairs, making sure that if {a,b} is there then {b,a} is not since then you are doing twice the work for no reason--it's like doing $\sum_{i,j>i}$ as opposed to $\sum_{i,j}$).

这是split的实现(我半个小时都无法上网，所以手工计算了相关方程，这不是基于您给出的链接，也不是优化或漂亮):

Here is an implementation of split (I was stuck with no internet access for half an hour or so, so worked out the relevant equations by hand, and this is not based on the link you gave nor is it optimized or pretty):

ClearAll[split2]
split2[{{ai_, bi_}, {ci_, di_}}] := Module[
{g1, g2, a, b, c, d, x0, y0, alpha, beta},
(*make sure that a is to the left of b*)

If[ai[[1]] > bi[[1]], {a, b} = {bi, ai}, {a, b} = {ai, bi}];
If[ci[[1]] > di[[1]], {c, d} = {di, ci}, {c, d} = {ci, di}];
g1 = (b[[2]] - a[[2]])/(b[[1]] - a[[1]]);
g2 = (d[[2]] - c[[2]])/(d[[1]] - c[[1]]);
If[g2 \[Equal] g1,
    {{a, b}, {c, d}},(*they're parallel*)

alpha = a[[2]] - g1*a[[1]];
    beta = c[[2]] - g2*c[[1]];
    x0 = (alpha - beta)/(g2 - g1);(*intersection x*)

If[(a[[1]] < x0 < b[[1]]) && (c[[1]] < x0 < 
   d[[1]]),(*they do intersect*)
            y0 = alpha + g1*x0;
            {{a, #}, {#, b}, {c, #}, {#, d}} &@{x0, y0},
            {{a, b}, {c, d}}(*they don't intersect after all*)]]]

(实际上，它的运行速度很慢且很丑陋).无论如何，您可以看到它的工作方式如下:

(in fact it's atrociously slow and ugly). Anyway, you can see that it works like this:

Manipulate[
Grid[{{Graphics[{Line[{p1, p2}, VertexColors \[Rule] {Red, Green}], 
  Line[{p3, p4}]},
        PlotRange \[Rule] 3, Axes \[Rule] True],
        (*Reap@split2[{{p1,p2},{p3,p4}}]//Last,*)
        If[
            Length@split2[{{p1, p2}, {p3, p4}}] \[Equal] 2,
            "not intersecting",
            "intersecting"]}}],
{{p1, {0, 1}}, Locator}, {{p2, {1, 1}}, Locator},
{{p3, {2.3, -.1}}, Locator}, {{p4, {2, 1}}, Locator}]

产生类似

和

(您可以移动定位器).请注意，只要其中一条线是垂直的，我的split2就会被零除(可以固定，但我还没有这样做).

(you can move the locators around). Mind you, my split2 divides by zero whenever one of the lines is vertical (this can be fixed but I haven't done it).

无论如何，这都是非常缓慢和丑陋的.通过编译并使其可列出列表(并使用您提供的链接)可以使其变得更快，但是我当前的茶歇时间已经结束(或超过半小时).稍后，我将尝试重新讨论.

In any case this is all very slow and ugly. It could be made faster by compiling and making listable (and using the link you gave), but my current coffee break is over (or was over half an hour ago). I'll try to get back to this later.

同时，请问是否有任何具体问题(例如，如果看不到垂直线的中断).并注意，尽管这样做确实可以满足您的要求，但是如果您确实在行列表上进行映射，则最终将得到一个参差不齐的列表，您必须将其展平.但是，这就是您要的:)

Meanwhile, do ask if there are any concrete questions (eg, if you can't see what breaks for vertical lines). And note that while this does what you ask, if you do map over a list of lines you'll end up with a ragged list which you will have to flatten. But, this is what you asked for :)

这篇关于Mathematica:不相交的线段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！