Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Self-intersection elimination algorithm using graph

IP.com Disclosure Number: IPCOM000013983D
Original Publication Date: 2000-May-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 3 page(s) / 52K

Publishing Venue

IBM

Abstract

Disclosed is an algorithm for self-intersection elimination of closed loop. In this algorithm, topology of self-intersections is presented using a graph structure. Then eliminate all self-intersections by traversing the graph. A topology of self-intersections in loop is presented using a graph as Fig.1. Fig.1 a graph for the topology of self-intersections Pseudo code to build a graph is shown below.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Self-intersection elimination algorithm using graph

Disclosed is an algorithm for self-intersection elimination of closed loop. In this algorithm,
topology of self-intersections is presented using a graph structure. Then eliminate all
self-intersections by traversing the graph.

A topology of self-intersections in loop is presented using a graph as Fig.1.

Fig.1 a graph for the topology of self-intersections

Pseudo code to build a graph is shown below.

start from segment containing self-intersection
create new node and do si_build recursively

proc si_build(startSelfInt,currentNode,currentSegment){
loop for continuous segments of loop{
currentSegment <- NextSegment(currentSegment)
if(currentSegment contains self-intersection si){
if(si == startSelfInt)
return
else{
if(check_forward(si,currentSegment) == SUCCESS){
create new node -> newNode
si_build(si,newNode,currentSegment)

}

}

}

}

}

proc check_forward(startSelfInt,currentSegment){
loop for continuous segments of loop{
currentSegment <- NextSegment(currentSegment)
if(currentSegment contains self-intersection si){
if(si == startSelfInt)
return SUCCESS
else{
if(si has been already traversed){
return FAIL
}

}

}

}

}

Procedure check_forward in pseudo code is needed for knot removal of loop. If there are knots in
the loop topology, they cause closed circuit in the graph structure shown in Fig.2. Closed
circuit removal is needed because following algorithm to eliminate self-intersections don't
support graphs with closed circuits.

1

[This page contains 2 pictures or other non-text objects]

Page 2 of 3

Fig.2 knot causes closed circuit

Wi...