检测两个重合线段的重合子集

问题描述

这个问题与:

• 如何确定GDI+中两条线的交点?(很好的代数解释，但没有代码)
• 如何检测两条线的位置段相交?(接受的答案实际上不起作用)

• How do I determine the intersection point of two lines in GDI+? (great explanation of algebra but no code)
• How do you detect where two line segments intersect? (accepted answer doesn't actually work)

但请注意，一个有趣的子问题在大多数解决方案中都被完全掩盖了，即使存在三个子案例，它们也只为重合案例返回 null:

But note that an interesting sub-problem is completely glossed over in most solutions which just return null for the coincident case even though there are three sub-cases:

• 重合但不重叠
• 触摸点和重合
• 重叠/重合线子段

例如，我们可以设计一个这样的 C# 函数:

For example we could design a C# function like this:

public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2)

其中 (a1,a2) 是一条线段，(b1,b2) 是另一条线段.

where (a1,a2) is one line segment and (b1,b2) is another.

此功能需要涵盖大多数实现或解释所掩盖的所有奇怪情况.为了解释重合线的怪异，该函数可以返回一个 PointF 数组:

This function would need to cover all the weird cases that most implementations or explanations gloss over. In order to account for the weirdness of coincident lines, the function could return an array of PointF's:

• 如果线平行或不相交(无限条线相交但线段不相交，或线平行)，则结果点为零(或null)
• 如果它们确实相交或如果它们在某一点重合，则为一个结果点(包含相交位置)
• 如果两条线重合
，则两个结果点(用于线段的重叠部分)

• zero result points (or null) if the lines are parallel or do not intersect (infinite lines intersect but line segments are disjoint, or lines are parallel)
• one result point (containing the intersection location) if they do intersect or if they are coincident at one point
• two result points (for the overlapping part of the line segments) if the two lines are coincident

推荐答案

听起来你有你的解决方案，这很棒.我有一些改进它的建议.

Sounds like you have your solution, which is great. I have some suggestions for improving it.

该方法有一个主要的可用性问题，因为很难理解 (1) 输入的参数是什么意思，以及 (2) 出来的结果是什么意思.如果你想使用这个方法，这两个都是你必须弄清楚的小谜题.

The method has a major usability problem, in that it is very confusing to understand (1) what the parameters going in mean, and (2) what the results coming out mean. Both are little puzzles that you have to figure out if you want to use the method.

我更倾向于使用类型系统来更清楚地说明这个方法的作用.

I would be more inclined to use the type system to make it much more clear what this method does.

我首先定义一个类型——也许是一个结构，特别是如果它是不可变的——称为 LineSegment.LineSegment 由两个表示终点的 PointF 结构组成.

I'd start by defining a type -- perhaps a struct, particularly if it was going to be immutable -- called LineSegment. A LineSegment consists of two PointF structs representing the end point.

其次，如果您需要表示作为两个或多个基因座联合的轨迹，我将定义一个抽象基类型Locus"和派生类型 EmptyLocus、PointLocus、LineSegmentLocus 以及可能的 UnionLocus.空轨迹只是单例，点轨迹只是单点，以此类推.

Second, I would define an abstract base type "Locus" and derived types EmptyLocus, PointLocus, LineSegmentLocus and perhaps UnionLocus if you need to represent the locus that is the union of two or more loci. An empty locus is just a singleton, a point locus is just a single point, and so on.

现在您的方法签名变得更加清晰:

Now your method signature becomes much more clear:

static Locus Intersect(LineSegment l1, LineSegment l2)

此方法采用两条线段并计算作为它们交点的点的轨迹——空的、单个点或线段.

This method takes two line segments and computes the locus of points that is their intersection -- either empty, a single point, or a line segment.

请注意，您可以推广此方法.计算线段与线段的交点很棘手，但计算线段与点的交点，或点与点的交点，或任何与空轨迹的交点容易.并且不难将交叉点扩展到任意位点联合.因此，您实际上可以这样写:

Note that you can then generalize this method. Computing the intersection of a line segment with a line segment is tricky, but computing the intersection of a line segment with a point, or a point with a point, or anything with the empty locus is easy. And it's not hard to extend intersection to arbitrary unions of loci. Therefore, you could actually write:

static Locus Intersect(Locus l1, Locus l2)

嘿，现在很明显，Intersect 可能是轨迹上的扩展方法:

And hey, now it becomes clear that Intersect could be an extension method on locus:

static Locus Intersect(this Locus l1, Locus l2)

添加从 PointF 到 PointLocus 和 LineSegment 到 LineSegmentLocus 的隐式转换，你可以这样说

Add an implicit conversion from PointF to PointLocus and LineSegment to LineSegmentLocus, and you can say things like

var point = new PointF(whatever);
var lineseg = new LineSegment(somepoint, someotherpoint);
var intersection = lineseg.Intersect(point);
if (intersection is EmptyLocus) ...

使用好类型系统可以大大提高程序的可读性.

Using the type system well can massively improve the readability of a program.

这篇关于检测两个重合线段的重合子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！