hlines.cpp

浏览该文件的文档.

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