匯東網


矩形重疊修正算法

[編輯] [转简体]
|
作者:huidong | 分類:【算法】雜項
[ 46 瀏覽 0 評論 14 贊 12 踩 ]

概要
問題雖小,猶有易錯之處。

正文

問題概述

現有兩個矩形,假設其中一個固定不動(rctMain),另一個可以移動(rctSub),它們如果存在重疊部分,則需要將 rctSub 移出 rctMain。

算法介紹

此算法分兩步。

  1. 判斷上述兩矩形是否相交

  2. 確定如何移出重疊的矩形

1. 判斷兩矩形是否相交

錯誤方案 1(頂點判據)

判斷 rctSub 的四個頂點是否在 rctMain 中,若有任一頂點在其中則認爲 rctMain 與 rctSub 相交,否則不交。

此方案錯誤,因爲相交的矩形不一定具有頂點的包含關係。如下圖,按照此方案,A 情況判斷正確,但 B 情況判斷錯誤。

錯誤方案 2(邊判據)

將 rctSub 的上下左右四條邊分別和 rctMain 中與之平行的兩條邊進行座標比較,例如 

if (rctMain.left < rctSub.left && rctSub.left < rctMain.right)
{
    // 認爲 rctSub.left 在 rctMain 內部
}

其餘三條邊以此類推。由此可以得到 rctSub 的上下左右四條邊陷入 rctMain 的情況,據此判斷 rctSub 和 rctMain 的重疊情況,如下圖:

對於 A,可以判斷出其右下兩條邊陷入 rctMain,因此確定相交,且可以考慮往左上移出;

對於 B,可以判斷出其下邊陷入 rctMain,因此確定相交,可以考慮向上移出;

對於 C,可以判斷出其上下兩條邊都陷入 rctMain,因此確定相交,但還需要進一步計算確定如何移出。

完整代碼如下:

// 標記 rctSub 的哪條邊陷入 rctMain 中
bool bT = false;
bool bB = false;
bool bL = false;
bool bR = false;

int t0 = rctMain.t();
int b0 = rctMain.b();
int l0 = rctMain.l();
int r0 = rctMain.r();

int t = rctSub.t();
int b = rctSub.b();
int l = rctSub.l();
int r = rctSub.r();

// 判定陷入時,只進行平行邊之間的判斷
if (t0 < t && t < b0) { bT = true; }
if (t0 < b && b < b0) { bB = true; }
if (l0 < l && l < r0) { bL = true; }
if (l0 < r && r < r0) { bR = true; }

// 無需修正的情況(任意一組文本平行邊完全沒有陷入,即說明文本與檢測箱相離)
if ((!bT && !bB) || (!bL && !bR))
    return;

// 完全陷入的情況
if (bT && bB && bL && bR)
    return;    // TODO ...

// 同一組平行邊都陷入時,不能作爲修正依據(因爲無法確定這個方向上如何移動)
if (bT && bB) {}
else if (bT) { rctTxt.alignT(b0); }
else if (bB) { rctTxt.alignB(t0); }

if (bL && bR) {}
else if (bL) { rctTxt.alignL(r0); }
else if (bR) { rctTxt.alignR(l0); }

此方案也錯誤,因爲只將 rctSub 的上下左右四條邊分別和 rctMain 中與之平行的兩條邊進行座標比較,相當於是忽略了另一個方向上的信息。例如,對於下面的情況將得出錯誤的結論:

對於 D,將被誤判爲左邊陷入 rctMain,導致被判定爲相交,且將被向右移出;

對於 E,將被誤判爲左右兩邊都陷入 rctMain,導致被判定爲相交。

這個方案在判斷相交時只在兩個矩形的平行邊之間進行座標比較,而忽略了矩形是二維形狀,必須同時研究其 x 和 y 兩個方向的邊界。此方案相當於是把矩形當成了下面的這種十字架圖形:

因此此方案亦不可取。

正確方案

直接計算出兩矩形的交集,若爲空集即表示不相交,否則表示相交。

在計算時,將矩形正交分解到 x, y 兩個方向分別取交集,如果結果都不是空集,即說明兩矩形相交,否則不相交。

代碼將在後面一併給出。

2. 確定如何移出 rctSub

在確定 rctSub 與 rctMain 相交後,需要將 rctSub 移出 rctMain。我們並不需要同時在 x 和 y 方向移動 rctSub,因爲在一個方向移動就可以將其移出 rctMain,倘若在兩個方向同時移動,則 rctSub 將總是和 rctMain 共一個頂點,這不是我想要的效果。

爲了確定究竟往哪個方向將 rctSub 移出 rctMain,我採用了如下公式進行計算。

分別表示 rctSub 和 rctMain 在 x 和 y 方向上的交集(閉區間),則有:



上面公式中,區間的 .left 和 .right 表示區間的左右端點。

只要 rctSub 與 rctMain 相交,那麼 必然非空,並且是 rctMain 在相應方向上投影區間的子集,因此上式中 的絕對值都小於 1,它們的絕對值代表在相應方向上移出 rctSub 的趨勢大小,而它們的正負指明了應該往相應方向的正方向還是負方向移出 rctSub(正即表示應從正方向移出,負即表示應從負方向移出)。因此我們只需要比較 的絕對值哪個大,就可以確定要從哪個方向移出 rctSub。

參考代碼

以下是參考代碼,是我在 BSch3V 項目中寫的,因此用的是此項目的矩形類型 SRect,但它和一般的 RECT 類型區別並不大。

rectoperation.h

/****************************************************************************
    BSch3V schematic capture
    Copyright (C) 1997-2014 H.Okada

    此文件爲匯東增入,用於處理矩形位置相關問題

*****************************************************************************/

#ifndef RECTOPERATION_H
#define RECTOPERATION_H

#include "coord.h"    // 提供 SRect


// 對重疊的矩形進行位置修正
void CorrectOverlappingRect(const SRect& rctMain, SRect& rctSub);

// 將相離的兩個矩形吸附在一起
void AdsorbRect(const SRect& rctBox, SRect& rctTxt);

#endif


rectoperation.cpp

#include "stdafx.h"
#include "rectoperation.h"

//(閉)區間
struct Range
{
    int left;
    int right;

    // 判斷此區間是否爲空
    bool IsEmpty() const
    {
        return right < left;
    }

    // 獲取區間長度
    int Length() const
    {
        return right - left;
    }
};

// 獲取相交區間(可能返回 right 小於 left 的區間,即表示空區間)
Range GetIntersectingRange(const Range& a, const Range& b)
{
    Range r = {
        max(a.left, b.left),
        min(a.right, b.right)
    };
    return r;
}

// 函數功能:
//   檢測兩個矩形是否發生相交
// 
// 參數說明:
//   [in]  rctA, rctB    待判定的矩形
//   [out] _rX, _rY        如果矩形的確相交,則傳出在 x, y 方向的相交區間
//
// 返回值:
//   返回 true 表示兩矩形相交,否則返回 false
//
bool checkIntersection(const SRect& rctA, const SRect& rctB, Range& _rX, Range& _rY)
{
    Range rX = GetIntersectingRange(
        { rctA.l(), rctA.r() },
        { rctB.l(), rctB.r() }
    );
    Range rY = GetIntersectingRange(
        { rctA.t(), rctA.b() },
        { rctB.t(), rctB.b() }
    );

    // 如果 rX 和 rY 都非空,則說明兩個矩形有交集
    if (!rX.IsEmpty() && !rY.IsEmpty())
    {
        _rX = rX;
        _rY = rY;
        return true;
    }
    else
    {
        return false;
    }
}

// 計算推力的標準向量
//
// 備註:
//   rMain 爲固定矩形正交分解的一個區間,rSub 爲其子集。
//   rSub 代表需要修正的矩形與固定矩形在某個方向(x / y)上的交集。
//   計算出的推力帶正負,絕對值小於 1,表示在該方向上將 rSub 推出 rMain 所用力量的大小。
//
double CalcForceStdVec(const Range& rMain, const Range& rSub)
{
    return (double)((rSub.left - rMain.left) + (rSub.right - rMain.right)) / rMain.Length();
}

// 函數功能:
//   對重疊的矩形進行位置修正
//
// 參數說明:
//   [in]      rctMain    固定矩形
//   [in, out] rctSub    待修正矩形
//
void CorrectOverlappingRect(const SRect& rctMain, SRect& rctSub)
{
    // 兩矩形相交的區間(正交分解後)
    Range rX, rY;

    // 若不相交,則不必修正
    if (!checkIntersection(rctMain, rctSub, rX, rY))
        return;

    // x, y 方向的標準推力(帶正負,絕對值小於 1)
    double vX = CalcForceStdVec({ rctMain.l(),rctMain.r() }, rX);
    double vY = CalcForceStdVec({ rctMain.t(),rctMain.b() }, rY);

    // 只需要在 x 或 y 一個方向修正矩形位置即可,此處哪個方向力大就選用哪個方向
    if (fabs(vX) > fabs(vY))
    {
        if(vX < 0) { rctSub.alignR(rctMain.l()); }    // 左推
        else { rctSub.alignL(rctMain.r()); }        // 右推
    }
    else
    {
        if (vY < 0) { rctSub.alignB(rctMain.t()); }    // 上推
        else { rctSub.alignT(rctMain.b()); }        // 下推
    }
}

// 函數功能:
//   將相離的兩個矩形吸附在一起
//
// 參數說明:
//   [in]      rctMain    固定矩形
//   [in, out] rctSub    待修正矩形
//
void AdsorbRect(const SRect& rctMain, SRect& rctSub)
{
    // 固定矩形位置
    int t0 = rctMain.t();
    int b0 = rctMain.b();
    int l0 = rctMain.l();
    int r0 = rctMain.r();

    // 待修正矩形位置
    int t = rctSub.t();
    int b = rctSub.b();
    int l = rctSub.l();
    int r = rctSub.r();

    // 磁性吸附
    if (t > b0) { rctSub.alignT(b0); }
    if (b < t0) { rctSub.alignB(t0); }
    if (l > r0) { rctSub.alignL(r0); }
    if (r < l0) { rctSub.alignR(l0); }
}


[ 14] [ 12]


 評論區  0 條評論

+ 添加評論