Searching and on-line recognition of star-shaped polygons
3
Citation
26
Reference
10
Related Paper
Citation Trend
Keywords:
Polygon (computer graphics)
Star (game theory)
Competitive Analysis
Line (geometry)
Rectilinear polygon
Visibility polygon
We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges and m concave regions, the algorithm decides in time O(n 2 + nm 2 + m 4 ) whether the polygon can be cleared by the two 1-searchers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.
Visibility polygon
Polygon (computer graphics)
Star-shaped polygon
Visibility
Rectilinear polygon
Clearance
Equiangular polygon
Clearing
Cite
Citations (18)
In this paper a new method is proposed to decide whether a point is in a simple polygon and a self-intersected polygon. A ray is rejected from the test point. According to the position between the edges of polygon and the ray, we define a position function of edges as to the ray, and then count the sum of the position function of all edges. We can decide whether the point is in the simple polygon and the self-intersected polygon by the sum. This method not only applies for simple polygon, but also for self-intersected polygon. Experiment result indicates that this method is simple, robust and fast.
Polygon (computer graphics)
Rectilinear polygon
Visibility polygon
Point in polygon
Position (finance)
Star-shaped polygon
Equiangular polygon
Cite
Citations (5)
We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and deletions to the simple polygon. A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point [Formula: see text] due to the insertion (resp. deletion) of vertex [Formula: see text] to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of [Formula: see text] due to the insertion (resp. deletion) of [Formula: see text]. An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point [Formula: see text] in [Formula: see text] amid vertex insertions and deletions to the simple polygon. If [Formula: see text] is not exterior to the current simple polygon, then the visibility polygon of [Formula: see text] is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of [Formula: see text]. An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment [Formula: see text] due to the insertion of vertex [Formula: see text] to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at [Formula: see text] and [Formula: see text] due to the insertion of [Formula: see text]. An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple polygon during the preprocessing phase.
Visibility polygon
Polygon (computer graphics)
Rectilinear polygon
Point in polygon
Star-shaped polygon
Visibility
Equiangular polygon
Visibility graph
Cite
Citations (5)
Nuclear of simple polygon is a set of points inside the polygon, any one of which can be seen from all the boundaries of the polygon. According to the fact that the nuclear of polygon only relates to the polygon pits, it only needs to deal with the pitsof the polygon.When there are continuous pits in one polygon, using the parallel ray method and linear intersection method can quickly determine whether the polygon has nuclear. When the polygon has nuclear, the time complexity of the node of polygon nuclear can be calculated.
Polygon (computer graphics)
Visibility polygon
Rectilinear polygon
Equiangular polygon
Star-shaped polygon
Point in polygon
Cite
Citations (0)
We are interested in the problem of guarding simple orthogonal polygons with the minimum number of $ r $-guards. The interior point $ p $ belongs an orthogonal polygon $ P $ is visible from $ r $-guard $ g $, if the minimum area rectangle contained $ p $ and $ q $ lies within $ P $. A set of point guards in polygon $ P $ is named guard set (as denoted $ G $) if the union of visibility areas of these point guards be equal to polygon $ P $ i.e. every point in $ P $ be visible from at least one point guards in $ G $. For an orthogonal polygon, if dual graph of vertical decomposition is a path, it is named path polygon. In this paper, we show that the problem of finding the minimum number of $ r $-guards (minimum guard set) becomes linear-time solvable in orthogonal path polygons. The path polygon may have dent edges in every four orientations. For this class of orthogonal polygon, the problem has been considered by Worman and Keil who described an algorithm running in $ O(n^{17} poly\log n) $-time where $ n $ is the size of the input polygon. The problem of finding minimum number of guards for simple polygon with general visibility is NP-hard, even if polygon be orthogonal. Our algorithm is purely geometric and presents a new strategy for $ r $-guarding orthogonal polygons and guards can be placed everywhere in the interior and boundary of polygon.
Visibility polygon
Polygon (computer graphics)
Star-shaped polygon
Rectilinear polygon
Guard (computer science)
Point in polygon
Equiangular polygon
Visibility graph
Cite
Citations (8)
We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and/or deletions to the simple polygon.
* A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point $q$ due to the insertion (resp. deletion) of vertex $v$ to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of $q$ due to the insertion (resp. deletion) of $v$.
* An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point $p$ in $\mathbb{R}^2$ amid vertex insertions and deletions to the simple polygon. If $p$ is not exterior to the current simple polygon then the visibility polygon of $p$ is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of $p$.
* An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon.
Each of these algorithms require preprocessing the initial simple polygon. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple polygon during the preprocessing phase.
Visibility polygon
Polygon (computer graphics)
Rectilinear polygon
Star-shaped polygon
Point in polygon
Visibility
Equiangular polygon
Visibility graph
Cite
Citations (1)
The relationship test of two polygons is algorithm for polygon in polygon.The prepared algorithm is complex;a new algorithm was given in this paper:every peak of two polygons was arranged a number in same direction,crossing points of polygon A and polygon B was calculated for every edge of A,these crossing points were ordered same direction as edge.The edges were divided into many segments by crossing points,every segments of polygon A located in polygon B was found out and put in a table lines;in the same way,segments of polygon B located in polygon A were founded out and put in table lines too.A segment in table lines was picked out as first segment,and a segment that can link with its endpoint in lines was found out and put into table points,it is done continuously till the segments is close,it is a new polygon,the common part of this two polygons A and B.Another common part could be found out like this method till lines are empty.The algorithm was proved simply and effectively by programming.
Rectilinear polygon
Polygon (computer graphics)
Visibility polygon
Star-shaped polygon
Point in polygon
Equiangular polygon
Table (database)
Cite
Citations (0)
In this paper, an algorithm to searching for the kernel of a simple polygon is proposed. The concave vertices of the polygon are merely deal with in the course of finding the kernel so the algorithm is efficient. The kernel of a polygon is found by cutting the polygon region using the lines passing by the edge which adjacent a concave vertex. In this course, a method is presented to determinate whether a ray intersect with a line segment by two special triangles' orientations which are identified by extremity vertices sequence. Not only can the algorithm judge whether the kernel of simple polygon is empty timely, but also get the vertexes of boundaries of the kernel. Test results show the high efficiency and stability of this algorithm.
Visibility polygon
Rectilinear polygon
Polygon (computer graphics)
Kernel (algebra)
Star-shaped polygon
Equiangular polygon
Cite
Citations (2)
The triangulation of a point-visible (star-shaped) polygon cannot be performed trivially if its kernel does not share a vertex with the polygon. The paper presents a triangulation algorithm that exploits point-and strong edge-visibility. It is through these two properties that the authors are able to triangulate in linear time. After classifying simple polygons by visibility, the authors show that strongly edge-visible polygons can be triangulated in linear time. A point-visible polygon is transformed into a strongly edge-visible polygon by the following steps: partitioning with a ray, partially triangulating both partitions, merging the two remaining polygons, and showing that the merged polygon is a strongly edge-visible polygon
Visibility polygon
Star-shaped polygon
Polygon (computer graphics)
Rectilinear polygon
Equiangular polygon
Point in polygon
Visibility
Cite
Citations (27)
We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and/or deletions to the simple polygon. * A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point $q$ due to the insertion (resp. deletion) of vertex $v$ to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of $q$ due to the insertion (resp. deletion) of $v$. * An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point $p$ in $\mathbb{R}^2$ amid vertex insertions and deletions to the simple polygon. If $p$ is not exterior to the current simple polygon, then the visibility polygon of $p$ is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of $p$. * An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment $pq$ due to the insertion of vertex $v$ to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at $p$ and $q$ due to the insertion of $v$. * An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon.
Visibility polygon
Polygon (computer graphics)
Rectilinear polygon
Point in polygon
Star-shaped polygon
Visibility
Equiangular polygon
Visibility graph
Line segment
Cite
Citations (0)