Pohang University of Science and Technology Foundation

Hee Kap Ahn

Tae Kang Eom

Hwi Kim

Min Cheol Kim

Hyo Jeong An

Mook Kwon Jung

Disclosed are embodiments of shortest path search in an obstacle environment. Provided is a shortest path search method including: creating an epsilon graph; and determining k closest points from a query point on the basis of the graph, wherein the creating of the graph includes: creating a node group of nodes on the basis of a point group of arrival points; creating an edge group of edges on the basis of the created nodes; setting, on the basis of an obstacle group of at least one obstacle, whether each of the nodes is a valid node or a non-valid node; setting, on the basis of the obstacle group, whether each of the edges is a valid or non-valid edge; and including, for each of the arrival points, a particular arrival point on an anchor list of a valid node closest from the particular arrival point among the valid nodes.

Shortest path search in obstacle environment

The present disclosure relates to a method for searching for the shortest path having a minimum link between buildings in a rectilinear polygon obstacle environment, which has been implemented to calculate the shortest path having a minimum link, among the shortest paths based on a Manhattan distance from one building to another building, when buildings are given in a rectilinear polygon obstacle environment. According to the present disclosure, in searching for the shortest path having a minimum link between two buildings, a more efficient data structure can be used in terms of an execution time and memory. A building-building minimum link and shortest path search problem can be solved through only the addition of very small operations by using the segment-point minimum link and shortest path search algorithm which can be easily expanded to the building-building minimum link and shortest path search problem.

Growing community of inventors

Pohang-si, South Korea

Hee Kap Ahn