3. Clipping of Line Segments

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : Clipping of line segments exercices

Reference: Werner Van Belle; Clipping of Line Segments;

Info

Het bepalen aan welke kant van een rechte een punt ligt is een cruciale zaak in computer graphics. Wiskundig wordt dit gedaan door te kijken hoe goed de eigenlijke vergelijking voldoet aan de gewenste vergelijking.

(x-x1)(y2-y1)  (y-y1)(x2-x1)

Als we in deze vergelijking voor x en y, respectievelijk a en b invullen moet de vergelijking een gelijkheid worden als het punt op de rechte licht. Als het punt (a,b) links ligt van de rechte zal het linkerlid groter zijn dan het rechterlid en als het punt rechts ligt van de rechte zal de gelijkheid overhellen naar de andere kant.

Oef 1: Clipping van lijnen; bepalen of 2 lijnen snijden

Door gebruik te maken van deze kennis kunnen we snel bepalen of een lijnsegment snijdt met een ander lijnsegment of niet. Implementeer een algoritme dat bepaalt of twee lijnen snijden of niet snijden. Dit algoritme moet in alle gevallen werken. Zorg dat de randgevallen (geen snijpunt of veel te veel snijpunten) ook werken.

Oef 2: Clipping van lijnen; bepalen van het snijpunt

Het bepalen van het snijpunt van 2 rechten gebeurt op de aloude wiskundige methode. Diegene die dit willen uitrekenen kunnen nut hebben aan

Implementeer het algoritme dat het snijpunt van 2 lijnen bepaalt. Demonstreer dat dit werkt door 100 lijnen random te tekenen op het scherm en alle snijpunten aan te duiden in het rood. Gebruik uw lijntekenalgoritme van 2 weken geleden.1

Oef 3: Punt inside polygon

Ontwikkel een algoritme dat controleert of een punt in of op een polygoon ligt. Dit moet niet geimplementeerd worden. Schrijf neer in pseudocode hoe het algoritme te werk gaat.

Werkt dit algoritme in randgevallen ?

Pas uw algoritme aan zodat het ook werkt bij alle randgevallen.

1 Als u geen werkend algoritme hebt kan u tekeer gaan met de vga_drawline functie. Let wel op de volgorde van de parameters van deze functie

#include<stdlib.h>
#include <vga.h>
typedef struct { int x1;
		 int y1;
		 int x2;
		 int y2;} lijnstuk ; 
typedef struct { int x;
                 int y; } punt;

int same_side(int x, int y, lijnstuk l);
int intersect(lijnstuk l1, lijnstuk l2);
punt bepaalSnijpuntVan2Rechten(lijnstuk, lijnstuk);


void drawline(lijnstuk l, int color)
{
vga_setcolor(color);
vga_drawline(l.x1,l.y1,l.x2,l.y2);
}

void main(void)
{
	lijnstuk l[0];
	int i,j;
	vga_setmode(G320x200x256);
	vga_setpalette(1,1,1,4);

	i=0;
	l[i].x1=random()/(RAND_MAX/0);
	l[i].x2=random()/(RAND_MAX/0);
	l[i].y1=random()/(RAND_MAX/0);
	l[i].y2=random()/(RAND_MAX/0);

drawline(l[0],4);
for(i=1;i<0;i++)
	{
	l[i].x1=random()/(RAND_MAX/0);
	l[i].x2=random()/(RAND_MAX/0);
	l[i].y1=random()/(RAND_MAX/0);
	l[i].y2=random()/(RAND_MAX/0);
	drawline(l[i],4);
	
	for(j=0;j<i;j++)
		{
		if (intersect(l[i],l[j])) 
			{ 
			punt p = bepaalSnijpuntVan2Rechten(l[i],l[j]);
			graph_mem[p.x+p.y*0] = 5;
			}
		}
	sleep(1);
	}
sleep(0);	
}



int intersect(lijnstuk l1, lijnstuk l2)
{	
	int result;
	int side1, side2;		

	side1 = which_side(l1.x1, l1.y1, l2);
	side2 = which_side(l1.x2, l1.y2, l2);
	
	result = side1*side2;
	
	if (result > 0)
		return 0;
	else if ( result == 0)
		return 1;
	else 
		{ side1 = which_side(l2.x1, l2.y1, l1);
		  side2 = which_side(l2.x2, l2.y2, l1);
		  result = side1*side2;
		  if (result > 0)
			return 0;
		   else return 1;
		}

}


int which_side(int x, int y, lijnstuk l)
{
	int v1, v2;

	v1 = (x - l.x1) * (l.y2 - l.y1);
	v2 = (y - l.y1) * (l.x2 - l.x1);
	
	if (v1 < v2) 
		return 1 ;
	else if (v1 == v2)
		return 0;
	else return -1;
}

punt bepaalSnijpuntVan2Rechten(lijnstuk l1, lijnstuk l2)
{
punt resultaat;
float a = l1.y2 - l1.y1;
float b = l1.x1 - l1.x2;
float c = l1.x1 * (l1.y2 - l1.y1) - l1.y1 * (l1.x2-l1.x1);
float d = l2.y2 - l2.y1;
float e = l2.x1 - l2.x2;
float f = l2.x1 * (l2.y2 - l2.y1) - l2.y1 * (l2.x2-l2.x1);

resultaat.x=(int)(c*e-f*b)/(a*e-b*d);
resultaat.y=(int)(a*f-c*d)/(a*e-d*b);
return resultaat;
}

http://werner.yellowcouch.org/
werner@yellowcouch.org