Part One
with matrix as (
SELECT split_part(line, ',', 1)::integer as _row, split_part(line, ',', 2)::integer as _col
FROM lance_input
)
SELECT (abs(a._row - b._row)+1)::bigint * (abs(a._col - b._col)+1)
FROM matrix a
JOIN matrix b
ON a._row != b._row
OR a._col != b._col
order by 1 desc limit 1;
Part Two
在这些坐标做成的一个大的多边形中，找到最大的图形内部的矩形。
内部点判断问题
又是一个判断点是否处于多边形内部的问题，参见之前的方式。
先判断每个顶点的拐角类型，是F7JL中的哪种
with matrix as (
SELECT row_number() over() as rn,
split_part(line, ',', 1)::integer as _row,
split_part(line, ',', 2)::integer as _col
FROM lance_input
), pre_next as (
SELECT x._row, x._col,
coalesce(pre_row, z._row) as pre_row,
coalesce(pre_col, z._col) as pre_col,
coalesce(next_row, y._row) as next_row,
coalesce(next_col, y._col) as next_col
FROM (
SELECT _row, _col,
lag(_row) over (order by rn) as pre_row,
lag(_col) over (order by rn) as pre_col,
lead(_row) over (order by rn) as next_row,
lead(_col) over (order by rn) as next_col
FROM matrix a
) x, (
SELECT _row, _col FROM matrix where rn = 1
) y, (
SELECT _row, _col FROM matrix where rn = (select max(rn) from matrix)
) z
), vertex as (
SELECT _row, _col,
case when pre_row < _row and next_col < _col then 'J'
when pre_col < _col and next_row < _row then 'J'
when pre_col > _col and next_row < _row then 'L'
when pre_row < _row and next_col > _col then 'L'
when pre_col < _col and next_row > _row then '7'
when pre_row > _row and next_col < _col then '7'
when pre_col > _col and next_row > _row then 'F'
when pre_row > _row and next_col > _col then 'F'
end as type
FROM pre_next
)
再根据某条边的两个顶角的类型，从而判断这条边是U型的。在判断*是否为内部点的时候，可以直接忽略。
#####
# #######
# #
* #######
这条边还有可能是Z型的，判断*是否内部点的时候，等价于经过了一条边。
#####
#
#
* #####
#
#
edge as (
SELECT least(a.pre_row, a._row) as start_row,
least(a.pre_col, a._col) as start_col,
greatest(a.pre_row, a._row) as end_row,
greatest(a.pre_col, a._col) as end_col,
case when a.pre_row = a._row then 'H'
when a.pre_col = a._col then 'V'
end as direction,
case when b.type = 'F' and c.type = '7' THEN 'U'
when b.type = '7' and c.type = 'F' THEN 'U'
when b.type = 'L' and c.type = 'J' THEN 'U'
when b.type = 'J' and c.type = 'L' THEN 'U'
when b.type = 'F' and c.type = 'J' THEN 'Z'
when b.type = 'J' and c.type = 'F' THEN 'Z'
when b.type = 'L' and c.type = '7' THEN 'Z'
when b.type = '7' and c.type = 'L' THEN 'Z'
end as type
FROM pre_next a
JOIN vertex b
ON a._row = b._row
AND a._col = b._col
JOIN vertex c
ON a.pre_row = c._row
AND a.pre_col = c._col
)
判断矩形是否越过边界
即使四个顶点都在多边形内部，但是整个矩形仍然有可能越过边界，比如
##########
# # #######
# * # # * #
# ############# #
# * * #
############################
因此需要额外判断矩形的四条边是否与边界线有交叉
最终的判断条件如下
candidates as (
SELECT least(a._row, b._row) as start_row,
least(a._col, b._col) as start_col,
greatest(a._row, b._row) as end_row,
greatest(a._col, b._col) as end_col
FROM matrix a
JOIN matrix b
ON a._row < b._row
AND a._col != b._col
), candidate_stats as (
SELECT a.start_row, a.start_col, a.end_row, a.end_col,
max(case when (b.direction = 'V' and a.start_col = b.start_col and a.start_row between b.start_row and b.end_row)
OR (b.direction = 'H' and a.start_row = b.start_row and a.start_col between b.start_col and b.end_col) then 1 end) as NW_edge,
max(case when (b.direction = 'V' and a.end_col = b.start_col and a.start_row between b.start_row and b.end_row)
OR (b.direction = 'H' and a.start_row = b.start_row and a.end_col between b.start_col and b.end_col) then 1 end) as NE_edge,
max(case when (b.direction = 'V' and a.start_col = b.start_col and a.end_row between b.start_row and b.end_row)
OR (b.direction = 'H' and a.end_row = b.start_row and a.start_col between b.start_col and b.end_col) then 1 end) as SW_edge,
max(case when (b.direction = 'V' and a.end_col = b.start_col and a.end_row between b.start_row and b.end_row)
OR (b.direction = 'H' and a.end_row = b.start_row and a.end_col between b.start_col and b.end_col) then 1 end) as SE_edge,
count(case when b.direction = 'V' and b.start_col > a.start_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.start_col and a.start_row = b.start_row then 1 end) as NW_E_CNT,
count(case when b.direction = 'V' and b.start_col < a.start_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.start_col and a.start_row = b.start_row then 1 end) as NW_W_CNT,
count(case when b.direction = 'V' and b.start_col > a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.end_col and a.start_row = b.start_row then 1 end) as NE_E_CNT,
count(case when b.direction = 'V' and b.start_col < a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.end_col and a.start_row = b.start_row then 1 end) as NE_W_CNT,
count(case when b.direction = 'V' and b.start_col > a.start_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.start_col and a.end_row = b.end_row then 1 end) as SW_E_CNT,
count(case when b.direction = 'V' and b.start_col < a.start_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.start_col and a.end_row = b.end_row then 1 end) as SW_W_CNT,
count(case when b.direction = 'V' and b.start_col > a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col > a.end_col and a.end_row = b.end_row then 1 end) as SE_E_CNT,
count(case when b.direction = 'V' and b.start_col < a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end)
+ count(case when b.direction = 'H' and b.type = 'Z' and b.start_col < a.end_col and a.end_row = b.end_row then 1 end) as SE_W_CNT,
count(case when b.direction = 'V' and b.start_col > a.start_col and b.start_col < a.end_col and a.start_row > b.start_row and a.start_row < b.end_row then 1 end) as n_cnt,
count(case when b.direction = 'V' and b.start_col > a.start_col and b.start_col < a.end_col and a.end_row > b.start_row and a.end_row < b.end_row then 1 end) as s_cnt,
count(case when b.direction = 'H' and b.start_row > a.start_row and b.start_row < a.end_row and a.start_col > b.start_col and a.start_col < b.end_col then 1 end) as w_cnt,
count(case when b.direction = 'H' and b.start_row > a.start_row and b.start_row < a.end_row and a.end_col > b.start_col and a.end_col < b.end_col then 1 end) as e_cnt
FROM candidates a
JOIN edge b
ON 1 = 1
GROUP BY a.start_row, a.start_col, a.end_row, a.end_col
), candidate_coordinates as (
SELECT a.start_row, a.start_col, a.end_row, a.end_col,
case when NW_edge = 1 then TRUE
when NW_E_CNT % 2 = 1 AND NW_W_CNT % 2 = 1 THEN TRUE
else false
end as nw_inside,
case when NE_edge = 1 then TRUE
when NE_E_CNT % 2 = 1 AND NE_W_CNT % 2 = 1 THEN TRUE
else false
end as ne_inside,
case when SW_edge = 1 then TRUE
when SW_E_CNT % 2 = 1 AND SW_W_CNT % 2 = 1 THEN TRUE
else false
end as sw_inside,
case when SE_edge = 1 then TRUE
when SE_E_CNT % 2 = 1 AND SE_W_CNT % 2 = 1 THEN TRUE
else false
end as se_inside,
n_cnt + s_cnt + w_cnt + e_cnt as intersect_cnt
FROM candidate_stats a
)
select (end_row - start_row + 1)::bigint * (end_col - start_col + 1)
from candidate_coordinates
where nw_inside and ne_inside and sw_inside and se_inside and intersect_cnt = 0
order by 1 desc limit 1;