使用 C# 基于点对分割矩形
5.00/5 (1投票)
本文描述了如何根据用户定义的坐标将矩形分割成更小的部分。
本文描述了如何根据用户定义的坐标将矩形分割成更小的部分。
买者自负
在开始之前，我想指出的是，我将要向您展示的代码是概念验证代码。它没有使用诸如 Bentley–Ottmann 之类的算法，效率不高，并且可能有一百种更好的方法来实现它。但是，它能工作，这几乎是我目前最关心的！
入门
以下是将矩形分割成组成部分的规则：
- 线必须是直的，因此每对坐标将对齐在一个轴上。
- 坐标必须从边缘或另一对的交点开始。第二个坐标必须以类似的方式结束。任何未在另一条边/连接处开始/结束的“孤立”坐标都是非法的，应该被忽略。
- 只要它们遵循先前的规则，坐标就可以在画布边界内的任何点开始和结束。
为了实现这一点，我最终创建了许多支持类。
Segment- 此类定义了线的起始点、长度及其方向。最初，我只是通过存储两对坐标来开始，但最后，使用长度和方向更容易。SegmentPoint- 此类存储单个点的详细信息。对于由线段的开始和结束以及任何交点创建的每个唯一点，都会创建此类的实例。它还存储相邻点的方向。
internal class Segment
{
public Point EndLocation
{
get
{
int x;
int y;
switch (this.Orientation)
{
case SegmentOrientation.Vertical:
x = this.Location.X;
y = this.Location.Y + this.Size;
break;
default:
x = this.Location.X + this.Size;
y = this.Location.Y;
break;
}
return new Point(x, y);
}
}
public Point Location { get; set; }
public SegmentOrientation Orientation { get; set; }
public int Size { get; set; }
}
internal class SegmentPoint
{
public SegmentPointConnections Connections { get; set; }
public Point Location { get; set; }
public int X { get { return this.Location.X; } }
public int Y { get { return this.Location.Y; } }
}
有了这些辅助类，我现在可以构造代码来处理它们并提取矩形。
计算点
上图演示了第一个问题。四个线段相互交叉，导致生成一个不受任何用户定义点影响的矩形。但是，如果我们要找到该矩形，我们需要找到由多个线段相交生成的任何新点。
private void CalculatePoints()
{
List<Segment> segments;
segments = new List<Segment>();
this.Points = new Dictionary<Point, SegmentPoint>();
// add segments representing the edges
segments.Add(new Segment { Location = Point.Empty, Size = this.Size.Width,
Orientation = SegmentOrientation.Horizontal });
segments.Add(new Segment { Location = new Point(0, this.Size.Height),
Size = this.Size.Width, Orientation = SegmentOrientation.Horizontal });
segments.Add(new Segment { Location = Point.Empty, Size = this.Size.Height,
Orientation = SegmentOrientation.Vertical });
segments.Add(new Segment { Location = new Point(this.Size.Width, 0),
Size = this.Size.Height, Orientation = SegmentOrientation.Vertical });
// add the rest of the segments
segments.AddRange(this.Segments);
segments.Sort((a, b) =>
{
int result = a.Location.X.CompareTo(b.Location.X);
if (result == 0)
result = a.Location.Y.CompareTo(b.Location.Y);
return result;
});
foreach (Segment segment in segments)
{
Segment currentSegment;
// add the segment points
this.UpdatePoint(segment.Location, segment.Orientation == SegmentOrientation.Horizontal ?
SegmentPointConnections.Left : SegmentPointConnections.Top);
this.UpdatePoint(segment.EndLocation, segment.Orientation == SegmentOrientation.Horizontal ?
SegmentPointConnections.Right : SegmentPointConnections.Bottom);
// calculate any intersecting points
currentSegment = segment;
foreach (Segment otherSegment in segments.Where(s => s != currentSegment))
{
Point intersection;
intersection = Intersection.FindLineIntersection
(segment.Location, segment.EndLocation, otherSegment.Location, otherSegment.EndLocation);
if (!intersection.IsEmpty)
{
SegmentPointConnections flags;
flags = SegmentPointConnections.None;
if (intersection != segment.Location && intersection != segment.EndLocation)
{
if (segment.Orientation == SegmentOrientation.Horizontal)
flags |= ( SegmentPointConnections.Left | SegmentPointConnections.Right);
else
flags |= (SegmentPointConnections.Top | SegmentPointConnections.Bottom);
}
else if (intersection != otherSegment.Location && intersection != otherSegment.EndLocation)
{
if (otherSegment.Orientation == SegmentOrientation.Horizontal)
flags |= (SegmentPointConnections.Left | SegmentPointConnections.Right);
else
flags |= (SegmentPointConnections.Top | SegmentPointConnections.Bottom);
}
if (flags != SegmentPointConnections.None)
this.UpdatePoint(intersection, flags);
}
}
}
}
分解代码，我们执行以下操作：
- 创建另外四个表示画布边界的线段
- 按它们的起始位置对线段进行排序
- 循环每个线段并
- 为起始坐标创建一个点
- 为结束坐标创建一个点
- 循环每个其他线段，看看它是否与当前线段相交。如果相交，则在交点处创建一个新点
在以上任何声明要创建点的情况下，如果该点尚不存在，代码将创建该点，否则它将更新现有点的连接。
private void UpdatePoint(Point location, SegmentPointConnections connections)
{
SegmentPoint point;
if (!this.Points.TryGetValue(location, out point))
{
point = new SegmentPoint { Location = location, Connections = connections };
this.Points.Add(point.Location, point);
}
else if (!point.Connections.HasFlag(connections))
point.Connections |= connections;
}
上面的 CalculatePoints 方法效率很低，但它完成了这项工作。一旦运行完此例程，我们将得到一个坐标数组和连接点的方向。
计算矩形
现在我们有了所有点，包括用户定义的点和交点，我们可以使用它来生成实际的矩形。
private void CalculateRectangles()
{
SegmentPoint[] horizontalPoints;
SegmentPoint[] verticalPoints;
this.Rectangles = new HashSet<Rectangle>();
horizontalPoints = this.Points.Values.OrderBy(p => p.X).ToArray();
verticalPoints = this.Points.Values.OrderBy(p => p.Y).ToArray();
foreach (SegmentPoint topLeft in this.Points.Values.Where
(p => p.Connections.HasFlag(SegmentPointConnections.Left | SegmentPointConnections.Top)))
{
SegmentPoint topRight;
SegmentPoint bottomLeft;
topRight = horizontalPoints.FirstOrDefault(p => p.X > topLeft.X && p.Y == topLeft.Y &&
p.Connections.HasFlag(SegmentPointConnections.Right | SegmentPointConnections.Top));
bottomLeft = verticalPoints.FirstOrDefault(p => p.X == topLeft.X && p.Y > topLeft.Y &&
p.Connections.HasFlag(SegmentPointConnections.Left | SegmentPointConnections.Bottom));
if (topRight != null && bottomLeft != null)
{
SegmentPoint bottomRight;
bottomRight = horizontalPoints.FirstOrDefault(p => p.X == topRight.X &&
p.Y == bottomLeft.Y && p.Connections.HasFlag(SegmentPointConnections.Right |
SegmentPointConnections.Bottom));
if (bottomRight != null)
{
Rectangle rectangle;
rectangle = new Rectangle(topLeft.X, topLeft.Y, bottomRight.X - topLeft.X,
bottomRight.Y - topLeft.Y);
this.Rectangles.Add(rectangle);
}
}
}
}
在此方法中，我们循环遍历所有在左上角有连接的已定义点。
对于每个匹配的点，我们尝试找到符合以下条件的点
- 具有相同的 Y 坐标以及右或顶部连接。这为我们提供了右上角。
- 具有相同的 X 坐标以及左或底部连接。这为我们提供了左下角。
- 如果我们同时具有上述两个角，那么我们尝试找到一个点，该点的 X 坐标与右上角相同，Y 坐标与左下角相同，并且具有右或底部连接。这为我们提供了最后一个角，右下角。
- 如果我们有所有四个角，则为矩形。使用
HashSet确保不会添加两次相同的矩形。
就是这样。使用这两个例程，我现在可以通过定义点对将一个矩形分割成许多更小的部分。
闭幕词
我意识到该代码没有做几件事
- 如前所述（多次！），这些代码效率都不高。您添加的线段越多，它就会变得越慢。Gareth Rees 发布了一张很好的 图表，说明了我应该做的事情，实际上他的指针帮助我最初使此代码正常工作。
- 它不能很好地处理重叠的线段。它将重新运行这些点的生成，从而增加总时间。
- 输出矩形的顺序并不总是您期望的 - 它有点跳跃。
- 结束坐标必须等于或大于开始坐标（使用示例，提供负线段大小将触发此错误）。
与往常一样，此示例的源代码可以从 此链接 下载。