4. 凸形直線環繞系統
好抽象@@
using System.Collections;
using System.Drawing.Drawing2D;
namespace Q4
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
Random rd = new Random();
List<Rectangle> blocks = new List<Rectangle>();
bool advance = false;
private void button3_Click(object sender, EventArgs e)
{
Close();
}
private void button1_Click(object sender, EventArgs e)
{
advance = false;
blocks.Clear();
for (int i = 0, v = rd.Next(3, 5); i < v; i++)
{
Rectangle rect;
do
{
int y = rd.Next(20, 81);
int ys = rd.Next(40, 201);
rect = new Rectangle(rd.Next(20, 81), 400 - ys - y, rd.Next(40, 201), ys);
}
while (blocks.Count != 0 && !blocks.Any(e => e.IntersectsWith(rect)));
blocks.Add(rect);
}
panel1.Refresh();
panel2.Refresh();
}
private void panel1_Paint(object sender, PaintEventArgs e)
{
for (int i = 0; i < blocks.Count; i++)
{
var r = blocks[i];
var p = new Pen(Brushes.Black, 2);
p.DashStyle = (DashStyle)i;
e.Graphics.DrawRectangle(p, r.X, r.Y, r.Width, r.Height);
}
}
//------------------------------------------------------------------
// ★★★ 正確：求凸形直線環繞系統（Convex Rectilinear Surround） ★★★
//------------------------------------------------------------------
public record Seg(Point A, Point B);
private List<Seg> GetConvexRectilinearSurround(List<Rectangle> blocks)
{
List<Seg> edges = new();
if (blocks.Count == 0) return edges;
// Step 1: 收集所有 X/Y 分界線，形成網格座標
// x/y 0 3 9 27
// 1
// ...
// 7
// ...
// 9
var xs = blocks.Select(b => b.Left)
.Concat(blocks.Select(b => b.Right))
.Distinct()
.OrderBy(v => v)
.ToList();
var ys = blocks.Select(b => b.Top)
.Concat(blocks.Select(b => b.Bottom))
.Distinct()
.OrderBy(v => v)
.ToList();
int W = xs.Count - 1;
int H = ys.Count - 1;
// cell[i,j] 表示 [xs[i], xs[i+1]) x [ys[j], ys[j+1]) 是否被覆蓋
bool[,] cell = new bool[W, H];
// Step 2: 將原本所有矩形打到 cell 中
foreach (var r in blocks)
{
for (int i = 0; i < W; i++)
{
if (xs[i + 1] <= r.Left || xs[i] >= r.Right) continue;
for (int j = 0; j < H; j++)
{
if (ys[j + 1] <= r.Top || ys[j] >= r.Bottom) continue;
cell[i, j] = true;
}
}
}
// Step 3: X 方向凸化（每一列）
for (int j = 0; j < H; j++)
{
int left = -1, right = -1;
for (int i = 0; i < W; i++)
{
if (cell[i, j])
{
if (left == -1) left = i;
right = i;
}
}
if (left != -1)
{
for (int i = left; i <= right; i++)
cell[i, j] = true;
}
}
// Step 4: Y 方向凸化（每一欄）
for (int i = 0; i < W; i++)
{
int top = -1, bottom = -1;
for (int j = 0; j < H; j++)
{
if (cell[i, j])
{
if (top == -1) top = j;
bottom = j;
}
}
if (top != -1)
{
for (int j = top; j <= bottom; j++)
cell[i, j] = true;
}
}
// Step 5: 從凸化後的 cell 中取真正外框（只取 true/false 的交界）
for (int x = 0; x < W; x++)
{
for (int y = 0; y < H; y++)
{
if (!cell[x, y]) continue;
int x0 = xs[x];
int x1 = xs[x + 1];
int y0 = ys[y];
int y1 = ys[y + 1];
// 上邊: y在邊邊 or 上方沒填滿
if (y == 0 || !cell[x, y - 1])
edges.Add(new Seg(new Point(x0, y0), new Point(x1, y0)));
// 下邊
if (y == H - 1 || !cell[x, y + 1])
edges.Add(new Seg(new Point(x0, y1), new Point(x1, y1)));
// 左邊
if (x == 0 || !cell[x - 1, y])
edges.Add(new Seg(new Point(x0, y0), new Point(x0, y1)));
// 右邊
if (x == W - 1 || !cell[x + 1, y])
edges.Add(new Seg(new Point(x1, y0), new Point(x1, y1)));
}
}
return edges;
}
//------------------------------------------------------------------
private void panel2_Paint(object sender, PaintEventArgs e)
{
if (!advance) return;
// 畫原本矩形
for (int i = 0; i < blocks.Count; i++)
{
Rectangle item = blocks[i];
var p = new Pen(Brushes.Black, 2);
p.DashStyle = (DashStyle)i;
e.Graphics.DrawRectangle(p, item.X, item.Y, item.Width, item.Height);
}
// ★ 取得凸形直線外框
var edges = GetConvexRectilinearSurround(blocks);
using (var pen = new Pen(Color.Red, 4))
{
foreach (var s in edges)
e.Graphics.DrawLine(pen, s.A, s.B);
}
}
private void button2_Click(object sender, EventArgs e)
{
advance = true;
panel2.Refresh();
}
}
}
Bug版，共線會有問題，但用的是題目的方法@@
Last updated