vlines.cpp

浏览该文件的文档.

/*
 * @Description:    竖线列表实现
 * @Version:
 * @Autor: LL
 * @date: 2023-12-05
 * @LastEditors: dreamy-xay
 * @LastEditTime: 2024-06-06
 */
#include "common/feature/vlines.h"
 
namespace cm {
/* 横线列表成员方法实现 */
 
inline VLines::VLines(const std::initializer_list<Line>& vlines) {
    this->assign(vlines.begin(), vlines.end());
}
 
inline int VLines::FindNearLine(int postion, RelativePosition rp) {
    auto& this_lines = *this;
 
    int num_lines = this_lines.size();
 
    if (num_lines == 0)
        return -1;
 
    // 定位数组中最大的上下边界，超出此边界的位置必定不在线数组之中
    int upper = std::max(this_lines[num_lines - 1].pt1.x, this_lines[num_lines - 1].pt2.x);
    int lower = std::min(this_lines[0].pt1.x, this_lines[0].pt2.x);
    if (postion < lower || num_lines == 1)  // 越界
        return 0;
    else if (postion > upper)  // 最后一根线就是所要定位的最近的线，不需要考虑函数指定的是之前还是之后的那根线
        return num_lines - 1;
 
    // 遍历全部线，寻找首根线的位置大于所给位置 postion 的线
    for (int i = 0; i < num_lines; ++i) {
        int this_distance = (this_lines[i].pt1.x + this_lines[i].pt2.x) / 2 - postion;
        if (this_distance > 0) {
            // 根据所所给的位置类型判定是要指定在这根线之前还是之后的线
            if (i == 0)  // 如果索引为零，就是索引为0的线，不需要考虑函数指定的是之前还是之后的那根线
                return 0;
            else if (abs(this_distance) > abs((this_lines[i - 1].pt1.x + this_lines[i - 1].pt2.x) / 2 - postion)) {
                if (rp == NEAR || rp == BEFORE)
                    return i - 1;  // 返回最近的线或者函数指定的后面面的线
                else
                    return i;  // 返回函数指定的之前的线
            } else {
                if (rp == NEAR || rp == AFTER)
                    return i;  // 返回最近的线或者函数指定的前面的线
                else
                    return i - 1;  // 返回函数指定的之后的线
            }
        }
    }
}
 
inline int VLines::FindNearLine(const Line& line, RelativePosition rp) {
    auto& this_lines = *this;
    int num_lines = this_lines.size();
    if (num_lines == 0)
        return -1;
 
    int upper = std::max(this_lines[num_lines - 1].pt1.x, this_lines[num_lines - 1].pt2.x);
    int lower = std::min(this_lines[0].pt1.x, this_lines[0].pt2.x);
 
    int postion = (line.pt1.x + line.pt2.x) / 2;  // 寻找到所给线的位置，再用重载函数
 
    if (postion < lower || num_lines == 1)  // 越界
        return 0;
    else if (postion > upper)
        return num_lines - 1;
 
    return this->FindNearLine(postion, rp);
}
 
VLines& VLines::ExtendLines(const HLines& hlines, Position extend_direction, size_t start_vline_index, double threshold, size_t max_num_misaligned_lines, bool strict_inspect) {
    Cm_Assert(extend_direction == TOP || extend_direction == BOTTOM, "The vertical line \"extend direction\" only supports \"cm::TOP\" or \"cm::BOTTOM\" types!");
 
    auto& vlines = *this;
 
    int num_hlines = hlines.size();
    int num_vlines = vlines.size();
 
    // 如果横线数量小于2或者竖线列表数量小于2则返回
    if (num_hlines < 2 || num_vlines < 2)
        return vlines;
 
    // 计算横线平均距离：
    double vlines_avg_len = this->Reduce([](double sum, const Line& line) { return sum + line.Length(); }, 0.0) / num_vlines;
 
    Point2i top_pt, bottom_pt;
    const auto& first_hline = hlines.front();
    const auto& last_hline = hlines.back();
 
    switch (extend_direction) {
        case TOP:
            for (int i = start_vline_index; i < num_vlines; ++i) {
                top_pt = first_hline.Intersect(vlines[i]);
                bottom_pt = last_hline.Intersect(vlines[i]);
 
                // 如果竖线两边都没有对齐边界，则直接不处理该竖线
                if (strict_inspect && std::abs(vlines[i].pt1.y - top_pt.y) > 5 && std::abs(bottom_pt.y - vlines[i].pt2.y) > 5)
                    continue;
 
                // 如果竖线长度 < 平均竖线长度 * 阈值，则直接不处理该竖线
                if (vlines[i].Length() < threshold * vlines_avg_len)
                    continue;
 
                // 如果竖线未上对齐
                if (std::abs(vlines[i].pt1.y - top_pt.y) > 5) {
                    // 该竖线右侧是否存在竖线上对齐了最上方横线
                    bool right_vline_is_aligned = false;
 
                    // 查看在”最大允许连续未对齐的竖线的数量“的条件下，该竖线右侧是否存在竖线上对齐了最上方横线
                    for (int j = 1; j <= max_num_misaligned_lines && i + j < num_vlines; ++j)
                        if (vlines[i + j].IsAligned(first_hline, TOP)) {  // 查看竖线 i + j 是否上对齐了最上方横线
                            right_vline_is_aligned = true;
                            break;
                        }
 
                    // 如果当前竖线的右侧存在竖线上对齐了最上方横线，并且左侧竖线上对齐了最上方横线，则直接延伸该竖线
                    if (right_vline_is_aligned && (i < 1 || vlines[i - 1].IsAligned(first_hline, TOP)))
                        vlines[i].pt1.y = top_pt.y;
                }
            }
            break;
        case BOTTOM:
            for (int i = start_vline_index; i < num_vlines; ++i) {
                top_pt = first_hline.Intersect(vlines[i]);
                bottom_pt = last_hline.Intersect(vlines[i]);
 
                // 如果竖线两边都没有对齐边界，则直接不处理该竖线
                if (strict_inspect && std::abs(vlines[i].pt1.y - top_pt.y) > 5 && std::abs(bottom_pt.y - vlines[i].pt2.y) > 5)
                    continue;
 
                // 如果竖线长度 < 平均竖线长度 * 阈值，则直接不处理该竖线
                if (vlines[i].Length() < threshold * vlines_avg_len) {
                    continue;
                }
 
                // 如果竖线未下对齐
                if (std::abs(bottom_pt.y - vlines[i].pt2.y) > 5) {
                    // 该竖线右侧是否存在竖线下对齐了最下方横线
                    bool right_vline_is_aligned = false;
 
                    // 查看在”最大允许连续未对齐的竖线的数量“的条件下，该竖线右侧是否存在竖线下对齐了最下方横线
                    for (int j = 1; j <= max_num_misaligned_lines && i + j < num_vlines; ++j)
                        if (vlines[i + j].IsAligned(last_hline, BOTTOM)) {  // 查看竖线 i + j 是否下对齐了最下方横线
                            right_vline_is_aligned = true;
                            break;
                        }
 
                    // 如果当前竖线的右侧存在竖线下对齐了最下方横线，并且左侧竖线下对齐了最下方横线，则直接延伸该竖线
                    if (right_vline_is_aligned && (i < 1 || vlines[i - 1].IsAligned(last_hline, BOTTOM)))
                        vlines[i].pt2.y = bottom_pt.y;
                }
            }
            break;
 
        default:
            throw Exception("The horizontal line \"extend direction\" only supports \"cm::LEFT\" or \"cm::RIGHT\" types!");
    }
}
 
VLines& VLines::OptimizeIntersections(const HLines& hlines, size_t threshold) {
    // 当前竖线列表
    auto& vlines = *this;
 
    // 计算横竖线的数量
    int num_hlines = hlines.size();
    int num_vlines = vlines.size();
 
    // 如果横线或竖线数量为 0 则返回
    if (num_hlines == 0 || num_vlines == 0)
        return vlines;
 
    // 临时变量
    Point2d pt1, pt2;
    Line new_vline;
 
    // 新线列表
    VLines new_vlines;  // 新竖线列表
 
    // 优化所有竖线交点
    for (auto& vline : vlines) {
        new_vline = vline;  // 复制一份
 
        // * 优化上端点
        // 查找y坐标大于竖线上端点横线
        size_t index = std::upper_bound(hlines.begin(), hlines.end(), vline, [](const Line& line1, const Line& line2) { return line1.pt1.y < line2.Y(MINIMUM); }) - hlines.begin();
 
        // 如果存在横线
        if (index < num_hlines) {
            if (index > 0) {
                pt1 = vline.Intersect(hlines[index - 1]);
                pt2 = vline.Intersect(hlines[index]);
 
                // 相较于端点下方第一根横线，上端点和交点垂直距离
                double beyond_distance = std::abs(pt2.y - vline.pt1.y);
 
                if (threshold)  // 垂直距离大于等于该阈值，则强制延长竖线到端点上方第一根横线，否则就近延长
                    new_vline.pt1 = beyond_distance >= threshold ? pt1 : (std::abs(vline.pt1.y - pt1.y) <= beyond_distance ? pt1 : pt2);
                else  // 就近延长
                    new_vline.pt1 = std::abs(vline.pt1.y - pt1.y) <= beyond_distance ? pt1 : pt2;
            } else
                new_vline.pt1 = vline.Intersect(hlines[index]);
        } else  // 如果不存在横线，即所有横线都在竖线上端点上边
            new_vline.pt1 = vline.Intersect(hlines.back());
 
        // * 优化下端点
        // 查找y坐标大于竖线下端点横线
        index = std::upper_bound(hlines.begin(), hlines.end(), vline, [](const Line& line1, const Line& line2) { return line1.pt2.y < line2.Y(MINIMUM); }) - hlines.begin();
 
        // 如果存在横线
        if (index < num_hlines) {
            if (index > 0) {
                pt1 = vline.Intersect(hlines[index - 1]);
                pt2 = vline.Intersect(hlines[index]);
 
                // 相较于端点上方第一根横线，交点和下端点垂直距离
                double beyond_distance = std::abs(vline.pt2.y - pt1.y);
 
                if (threshold)  // 垂直距离大于等于该阈值，则强制延长竖线到端点下方第一根横线，否则就近延长
                    new_vline.pt2 = beyond_distance >= threshold ? pt2 : (beyond_distance <= std::abs(pt2.y - vline.pt2.y) ? pt1 : pt2);
                else  // 就近延长
                    new_vline.pt2 = beyond_distance <= std::abs(pt2.y - vline.pt2.y) ? pt1 : pt2;
            } else
                new_vline.pt2 = vline.Intersect(hlines[index]);
 
        } else  // 如果不存在横线，即所有横线都在竖线下端点下边
            new_vline.pt2 = vline.Intersect(hlines.back());
 
        // 加入新竖线
        if (!new_vline.IsPoint())
            new_vlines.emplace_back(new_vline);
    }
 
    // 更新竖线列表并返回
    return vlines = std::move(new_vlines);
}
 
VLines& VLines::RmFreeVLines(const HLines& hlines, int threshold) {
    auto& vlines = *this;  // 竖线本身
 
    // 如果横线或竖线数量为 0 则返回
    if (hlines.empty() || vlines.empty())
        return vlines;
 
    // 新竖线列表
    VLines new_vlines;
 
    // 遍历全部竖线
    for (auto& vline : vlines) {
        Interval y_range(vline.pt1.y - threshold, vline.pt2.y + 1 + threshold);  // 交点y坐标范围区间
        auto vline_ge = vline.GECoefficients();                                  // 竖线一般方程
 
        // 是否不是游离竖线
        bool is_not_free = false;
 
        // 遍历所有横线
        for (auto& hline : hlines) {
            Interval x_range(hline.pt1.x - threshold, hline.pt2.x + 1 + threshold);  // 交点x坐标范围区间
            Point2d intersection = hline.Intersect(vline_ge);                        // 横竖线交点
 
            if (x_range.Include(intersection.x) && y_range.Include(intersection.y)) {  // 如果交点x和y坐标在范围内，表示横竖线是相交的
                is_not_free = true;                                                    // 竖线不是游离竖线
                break;
            }
        }
 
        // 如果竖线不是游离竖线，则加入新竖线列表
        if (is_not_free)
            new_vlines.emplace_back(vline);
    }
 
    // 更新竖线列表
    vlines = std::move(new_vlines);
 
    return vlines;
}
 
}  // namespace cm