Shortest path solves edge-to-edge visibility in a polygon

Godfried T. Toussaint

doi:10.1016/0167-8655(86)90015-2

Shortest path solves edge-to-edge visibility in a polygon

Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Given a simple polygon P = (p₁, p₂, ..., p_n) consisting of n edges e_i = [p_ip_i+1], i = 1,2, ..., n, two edges e_i and e_j are said to be visible if there exists a point χε{lunate}e_i and a point yε{lunate}e_j such that the line segment [χ y] lies in P. An edge-to-edge visibility query asks for whether a specified pair of edges of P is visible. It is shown that with O(n log n) preprocessing of P, an edge-to-edge visibility query can be answered in O(n) time. The algorithm also reports a line-of-sight if the answer is in the affirmative.

Original language	English (US)
Pages (from-to)	165-170
Number of pages	6
Journal	Pattern Recognition Letters
Volume	4
Issue number	3
DOIs	https://doi.org/10.1016/0167-8655(86)90015-2
State	Published - Jul 1986

Keywords

Weak-visibility
computational geometry
edge-visibility graph
geodesic distance
graphics
image processing
polygon triangulation
shortest path

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0167-8655(86)90015-2

Cite this

@article{d19eec9d437f4e5aa33575d80f60d6fe,

title = "Shortest path solves edge-to-edge visibility in a polygon",

abstract = "Given a simple polygon P = (p1, p2, ..., pn) consisting of n edges ei = [pipi+1], i = 1,2, ..., n, two edges ei and ej are said to be visible if there exists a point χε{lunate}ei and a point yε{lunate}ej such that the line segment [χ y] lies in P. An edge-to-edge visibility query asks for whether a specified pair of edges of P is visible. It is shown that with O(n log n) preprocessing of P, an edge-to-edge visibility query can be answered in O(n) time. The algorithm also reports a line-of-sight if the answer is in the affirmative.",

keywords = "Weak-visibility, computational geometry, edge-visibility graph, geodesic distance, graphics, image processing, polygon triangulation, shortest path",

author = "Toussaint, {Godfried T.}",

note = "Funding Information: This research was supported by grants FCAC-EQI678, NSERC-A9293 and a Killam Senior Research Fellowship from the Canada Council.",

year = "1986",

month = jul,

doi = "10.1016/0167-8655(86)90015-2",

language = "English (US)",

volume = "4",

pages = "165--170",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Shortest path solves edge-to-edge visibility in a polygon

AU - Toussaint, Godfried T.

N1 - Funding Information: This research was supported by grants FCAC-EQI678, NSERC-A9293 and a Killam Senior Research Fellowship from the Canada Council.

PY - 1986/7

Y1 - 1986/7

N2 - Given a simple polygon P = (p1, p2, ..., pn) consisting of n edges ei = [pipi+1], i = 1,2, ..., n, two edges ei and ej are said to be visible if there exists a point χε{lunate}ei and a point yε{lunate}ej such that the line segment [χ y] lies in P. An edge-to-edge visibility query asks for whether a specified pair of edges of P is visible. It is shown that with O(n log n) preprocessing of P, an edge-to-edge visibility query can be answered in O(n) time. The algorithm also reports a line-of-sight if the answer is in the affirmative.

AB - Given a simple polygon P = (p1, p2, ..., pn) consisting of n edges ei = [pipi+1], i = 1,2, ..., n, two edges ei and ej are said to be visible if there exists a point χε{lunate}ei and a point yε{lunate}ej such that the line segment [χ y] lies in P. An edge-to-edge visibility query asks for whether a specified pair of edges of P is visible. It is shown that with O(n log n) preprocessing of P, an edge-to-edge visibility query can be answered in O(n) time. The algorithm also reports a line-of-sight if the answer is in the affirmative.

KW - Weak-visibility

KW - computational geometry

KW - edge-visibility graph

KW - geodesic distance

KW - graphics

KW - image processing

KW - polygon triangulation

KW - shortest path

UR - http://www.scopus.com/inward/record.url?scp=0022858292&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022858292&partnerID=8YFLogxK

U2 - 10.1016/0167-8655(86)90015-2

DO - 10.1016/0167-8655(86)90015-2

M3 - Article

AN - SCOPUS:0022858292

SN - 0167-8655

VL - 4

SP - 165

EP - 170

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 3

ER -

Shortest path solves edge-to-edge visibility in a polygon

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this