Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

究

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

to Draw Figures EÆciently

Takashi Amano

School of Information Science,

Japan Advanced Institute of Science and Technology

February 15, 2001

Keywords: group updates, data structure, chromatictree, thinking time.

Whenwesolveaproblemtreatinggeometricdata,theroleplayedbycomputersisvery

largeandthenecessityofdealingwiththeproblemconcerninggeometricgureseÆciently

by computers has increased more and more in recent years. Studies on data structures

tomanagegeometric dataare performedrigorously,and variousdata sutructuressuch as

anAVL tree and asegment tree are proposed.

Drawing tools, such as CAD, must be able to insert, delete and select required geo-

metric objects quickly while they treat geometric huge data. For that, we need suitable

algorithms and data structures. Moreover, it is important that a user does not feel un-

confortablewiththe processingtime. Now, generallywe usebalanced binarysearchtrees

represented byAVL treeforbasic datastructures inCAD. OnanAVL tree,adatastruc-

tureisupdatedforeveryinsertionordeletion. Geometricdataareoftenhuge. Thus,when

the updatingisperformedfrequently, processingtakesmuchtimeand the problemthat a

response may be overdue arises. Therefore, wealso need atechnique forcollectingmany

updates intoa group and performing insertions and deletionsat once. The technique of

collectingat once and updatingis called \groupupdates".

Inthisstudy,weconsidereectiveuseofthinkingtime(inputwaitingtime)madewhen

anoperator are drawing gures. We havedeveloped analgorithmand data structure for

practicalusesothatselection,insertionanddeletionaredonequicklyusinggroupupdates.

When an operatordraws gures,generally noone inputs continuously,but does after

considering gures to draw. A computer enters a state for waiting aninput in which no

gureisinput. Thatis,drawingtimecanbedividedintotimeforactuallyinputofgures

and thinking time of gures to draw. An operator draws gures by repeating the two

processes. We use eectively the waiting time of computers created by the characteristic

of the input by humanoperators. If acomputer does some updates duringwaiting time,

Copyrightc 2001byTakashiAmano

performed quickly. Although acomputer doesupdates during thinkingtime, acomputer

mustperformindispensableprocessingsimmediately. Foranoparatordoesn't understand

anymorewhatguresaredrawnwhere. Inthisstudy,whenanoperatorinputs,acomputer

performs indispensableprocessingsimmediately,and we tryto draw gureseÆciently by

updating the data structure whichneeds time later.

Weprepare threememorydomainstoaccumulatedataasdatastructuresforthetech-

nique. The main memory domain accumulate alldata, and others are memory domains

to accumulate data temporarily. They are a memory domainwhichaccumulates data to

beinserted, andamemorydomainwhichaccumulatesdatatobedeleted. Thedata tobe

inserted when an operator draws gures, or data to be deleted are saved to the memory

domainaccumulatedtemporarily. Next,duringthinkingtime,the dataaccumulatedtem-

porarilyuntil noware inserted inthe main memory domainordata are deleted fromthe

mainmemorydomain. Sincealldataare accumulatedtherewhen thenumberofmemory

domainsisone, theconventionaltechniquerequirestimeforupdates. Sincethetechnique

inthisstudy accumulates onlythepresent updatestemporarilyandupdates forthemain

are performedlater, time required for the present updates isshortened.

The updating operations accumulated temporarilyare not reected in the main data

structure by the simple technique, but we elaborate a device ongroup updatesso that it

can update more eÆciently than a simple technique. A simple technique inserts into or

deletesfromthe main memorydomain forevery data. We use achromatictree asadata

structure required toperform group updateseÆciently.

Inthisstudy,weexperimentedbyprogrammingthetoolwhichperformsgroupupdates

usingachromatictree. Weobtainedthe resultsthatthegroupupdatescanperformmore

quicklythantheconventionaltechniquebytheexperimentsofcomparingtheconventional

techniqueswithgroupupdatesinexecutiontime. Fromtheexperimentalresults,itisseen

that the technique of this study can be updated more eÆciently than the conventional

technique and it was shown that drawing of gurescan alsobe performedsmoothly.

Since updatingoperationdoes notupdate the main datastructure unlikethe conven-

tionaltechnique,wecanperforminputoperationssmoothly. Moreover, ingroupupdates,

sinceitisdividedintothemaindatastructureandthetemporarymemorydomains,when

a certain data are input and operations of deletion are performed immediately, there is

an advantage that oset of the data in a temporary memory domainscan be performed

quickly.

Althoughwehaverealizedameritofagroupupdatesusingachromatictree, wecould

use a skip list. In the future, we would like touse askip listinstead of a chromatictree.

Then,ascomparedwiththetechniqueproposedinthisstudy,wewillobtainaninteresting

result. Since achromatictree isa data structure alsoeÆcient for parallelproceccing, we

will alsoneed toprogram and compare the data structure to enable parallel proceccing.

In this data structure we have only dealt with segments. However, it became easier to

draw gures if the elements which form gures have basic elements, such as not only

segments but also points, circlesand polygons, and curves. Study on data structures for

accumulating suchbasic elementseÆciently has been left asa future subject.