Multiple line segment intersection
કોમ્પ્યુટેશનલ ભૂમિતિમાં, બહુવિધ રેખા ખંડ આંતરછેદ સમસ્યા યુક્લિડિયન સમતલમાં રેખા વિભાગોની સૂચિ પૂરી પાડે છે અને પૂછે છે કે શું તેમાંથી કોઈપણ બે આંતરછેદ (ક્રોસ) કરે છે. સરળ અલ્ગોરિધમ્સ વિભાગોની દરેક જોડીની તપાસ કરે છે. જો કે, જો મોટી સંખ્યામાં સંભવતઃ આંતરછેદના સેગમેન્ટ્સની તપાસ કરવી હોય, તો આ વધુને વધુ બિનકાર્યક્ષમ બને છે કારણ કે સેગમેન્ટ્સની મોટાભાગની જોડીઓ લાક્ષણિક ઇનપુટ ક્રમમાં એકબીજાની નજીક હોતી નથી. મોટી સંખ્યામાં સેગમેન્ટ્સ માટે આ સમસ્યાનું સમાધાન કરવાની સૌથી સામાન્ય અને વધુ કાર્યક્ષમ રીત સ્વીપ લાઇન અલ્ગોરિધમનો ઉપયોગ કરવાનો છે, જ્યાં આપણે લાઇન સેગમેન્ટ્સમાં સ્લાઇડિંગ લાઇનની કલ્પના કરીએ છીએ અને બાયનરી સર્ચ ટ્રીઝ પર આધારિત ડાયનેમિક ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરીને દરેક સમયે તે કયા લાઇન સેગમેન્ટ્સને છેદે છે તે ટ્રેક કરીએ છીએ. શેમોસ-હોઇ અલ્ગોરિધમ લાઇન સેગમેન્ટ આંતરછેદ શોધવાની સમસ્યાને ઉકેલવા માટે આ સિદ્ધાંતને લાગુ કરે છે, ઉપર જણાવ્યા મુજબ, લાઇન સેગમેન્ટના સમૂહમાં આંતરછેદ છે કે નહીં તે નક્કી કરવા માટે; બેન્ટલી-ઓટમેન અલ્ગોરિધમ એ જ સિદ્ધાંત દ્વારા કામ કરે છે જે દરેક આંતરછેદ દીઠ લઘુગણક સમયમાં તમામ આંતરછેદોની યાદી આપે છે. બેન્ટલી-ઓટમેન અલ્ગોરિધમ સંદર્ભો વધુ વાંચન પ્રકરણ 2: લાઇન સેગમેન્ટ ઇન્ટરસેક્શન, પીપી. 19-44 પણ જુઓ. થોમસ એચ. કોર્મન, ચાર્લ્સ ઇ. લિસરસન, રોનાલ્ડ એલ. રિવેસ્ટ અને ક્લિફોર્ડ સ્ટેઇન. અલ્ગોરિધમ્સનો પરિચય, બીજી આવૃત્તિ. એમઆઇટી પ્રેસ અને મેકગ્રો-હિલ, 1990. વિભાગ 33.2: વિભાગોની કોઈપણ જોડી છેદે છે કે કેમ તે નક્કી કરવું, pp. 934-947. જે. એલ. બેન્ટલી અને ટી. ઓટમેન., ભૌમિતિક આંતરછેદોની જાણ અને ગણતરી માટેના અલ્ગોરિધમ્સ, IEEE ટ્રાન્સ. કોમ્પ્યુટ કરો. C28 (1979), 643-647. બાહ્ય કડીઓ ડેન સન્ડે રોબર્ટ પ્લેસના રેખાઓ અને વિમાનોના આંતરછેદો અલ્ગોરિધમ્સ અને નમૂના કોડ. વ્યાખ્યાન 4 નોંધો. સેન્ટ લૂઇસમાં વોશિંગ્ટન યુનિવર્સિટી, CS 506: કોમ્પ્યુટેશનલ ભૂમિતિ (કેશ કરેલી નકલ). સી. જી. એ. એલ. માં લાઇન સેગમેન્ટ આંતરછેદ, જેફ એરિકસન દ્વારા કોમ્પ્યુટેશનલ ભૂમિતિ અલ્ગોરિધમ્સ લાઇબ્રેરી "લાઇન સેગમેન્ટ ઇન્ટરસેક્શન" વ્યાખ્યાન નોંધે છે. સી કોડ સાથે રેખા-રેખા આંતરછેદ પદ્ધતિ નમૂના ડેરેલ રેક્સ ફિનલી ભૌમિતિક અલ્ગોરિધમ્સ ભૌમિતિક આંતરછેદ કોમ્પ્યુટેશનલ ભૂમિતિ