Article View: comp.graphics.algorithms
Article #52Re: BSP tree question
From: Jose Flores
Date: Fri, 01 Sep 1995 17:49
Date: Fri, 01 Sep 1995 17:49
25 lines
1610 bytes
1610 bytes
No it's not the easiest. The a simpler (and not that inefficient) would
be to test the slopes of the 2 lines in question and if m1 <= m2 then the
segment is on the right...the only catch is if the slope is negative; is
it the numerator positive and the denominator negative or vic versa? To
elimate this (and to eliminate a nasty divide) do if (dx1*dy2) <=
(dy2*dx2) then the line is on the right of the partion line. EX:
int OnRight( short Index){
long x1 = Nodes[Index].x;
long y1 = Nodes[Index].y;
long x2 = x1 + Nodes[Index].dx;
long y2 = y1 + Nodes[Index].dy;
if ( ((x1-x2)*(py-y2)) <= ((y1-y2)*(px-x2)) )
return 1;
else return 0;
}
more intuative that dot or cross product in my opinion but almost
certainly not the best. I remember glancing at a recent issue of DD
sourcebook and Abrash mentioning a *very* simple test but I may be
mistaken.
--
Those who danced were thought to be quite insane by those who could not
hear the music.
Technical Details
Message-ID:
<427h2r$a8i@spock.asic.sc.ti.com>Path:
arc1-ca.pugleaf.net!spock.asic.sc.ti.com!usenetReferences:
<DE70Io.AG6@corsair.daytonoh.attgis.com>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!spock.asic.sc.ti.com!usenet From: Jose Flores <jflore@asictest.sc.ti.com> Newsgroups: comp.graphics.algorithms,comp.sys.amiga.programmer,rec.games.programmer Subject: Re: BSP tree question Date: 1 Sep 1995 17:49:15 GMT Organization: Texas Instruments Message-ID: <427h2r$a8i@spock.asic.sc.ti.com> References: <DE70Io.AG6@corsair.daytonoh.attgis.com> NNTP-Posting-Host: tkieschnick.asic.sc.ti.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 1.1N (Windows; I; 16bit) To: tim.wendt@daytonoh.ncr.com