带权值目标点的可见覆盖求解算法
대권치목표점적가견복개구해산법
An Algorithm for Visible Covering of the Weighed Target Points
  • 万方数据
    计算机辅助设计与图形学学报 계산궤보조설계여도형학학보
    JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
    2014年 3期 364-369 ,共6页

    董君%朱恒亮%曾璇

    동군%주항량%증선

    艺术画廊问题%可见多边形%带权值目标点%计算几何%整数线性规划 藝術畫廊問題%可見多邊形%帶權值目標點%計算幾何%整數線性規劃
    예술화랑문제%가견다변형%대권치목표점%계산궤하%정수선성규화
    art gallery problem%visibility polygon%weighed target point%computational geometry%integer linear programming (ILP)
    针对传统的艺术画廊模型及其模型的变形在实际应用中无法处理诸如可用守卫数受限、只需监控离散目标点等情形,提出一种基于带权值目标点的可见覆盖的变形模型及其求解算法.首先利用角扫描技术得到每个目标点的可见多边形,然后通过对这些可见多边形进行几何求交、几何求差操作来得到若干等价目标可见区域,再依据每个区域对应的可见目标点集将所提出的变形模型转化为经典的集合最大权值覆盖问题,最后利用整数线性规划方法对其求解,得到最终需要的守卫数及放置位置.大量的实验结果表明,该算法是正确和有效的.
    침대전통적예술화랑모형급기모형적변형재실제응용중무법처리제여가용수위수수한、지수감공리산목표점등정형,제출일충기우대권치목표점적가견복개적변형모형급기구해산법.수선이용각소묘기술득도매개목표점적가견다변형,연후통과대저사가견다변형진행궤하구교、궤하구차조작래득도약간등개목표가견구역,재의거매개구역대응적가견목표점집장소제출적변형모형전화위경전적집합최대권치복개문제,최후이용정수선성규화방법대기구해,득도최종수요적수위수급방치위치.대량적실험결과표명,해산법시정학화유효적.
    원문보기 원문다운로드 사이트로이동
저자의 최근 논문