close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1 Finite Element Method Quadtree-Verfahren Dr

EinbettenHerunterladen
1
Finite Element Method
Quadtree-Verfahren
Dr. Jamel Tazarki
Diese Forschungsarbeit entstand am Institut für Mathematik
der Universität München.
Teil2
2
3
4
5
Figur 1: Der Quadtree ist ein Digraph
Figur 2 : Ein Knoten enthält eine Liste von vier Datenelementen , die den Quadraten einer Region des
Objektes entsprechen.
6
Figur 3: Das schwarze Quadrat in dem Image-Array ist durch die Zeiger-Sequenz (2,1,1,3) zu erreichen
Figur 4: Die Octree-Knoten enthalten eine Liste von acht Data-Elementen
7
8
Figur 1a: Quadtree nach der Erzeugung des Grades (level) 1.
1
Figur 3a : Feldspeicherung (Array Storage): “1” steht für das Quadrat (in diesem Fall die Wurzel), das nur
Teilweise in dem Objekt liegt, und das „Partial“ genannt wird.
9
Stufe 1:
Wir unterteilen die Wurzel der Stufe 0 (siehe Seite 62) in 4 Quadrate, die von q0 bis q3 durchnumeriert
werden. Man beachte die Reihenfolge.
Bemerkung:
Leere Quadrate (d.h. Quadrate die außerhalb des Objektes liegen) werden im Baum mit dem Zeichen "*"
und in der Feldspeicherung mit der Zahl "0" bezeichnet.
Parteielle Quadrate (d.h. Quadrate, die Teilweise im Objekt liegen) mit dem Zeichen “
Feldspeicherung mit der Zahl "1" bezeichnet.
" und in der
Figur 1b: Quadtree nach der Erzeugung der Stufe 1
Figur 2b Baumspeicherung: Der baum besteht aus der Wurzel und den "Kindern" der Wurzel.
10001
Figur 3b Feldspeicherung: Die erste "1" (von links) steht für die Wurzel. Die erste "0" steht für q0, die
zweite "0" steht für "q1", die dritte "0" steht für "q2", die zweite "1" steht für "q3"
Bemerkung: q0, q1 und q3 werden in der nächsten Stufe (Seite 64) nicht mehr unterteilt. Sie können
ignoriert werden.
10
11
12
13
14
15
16
Figur 6. Beschnittene Quadrate
17
18
19
20
21
22
23
24
25
26
27
FBB(i) entsteht aus FBB(i+1), wenn man FBB(i+1) jeden grauen Knoten, der zuletzt zu FB(i+1) zugefügt
wurde, durch seinen schwarzen Wald ersetzt.
28
29
30
31
Beweis
32
33
34
35
36
37
38
39
40
Hier ist das Java-Programm für Die Quadtree-Generierung:
package com.bmw.prolo.graphics;
// Autor: Dr. Jamel Tazarki
import javax.swing.*;
import java.awt.*;
import javax.swing.*;
import java.awt.*;
import java.io.*;
public class MyTreeCreator
extends JPanel{
int imageArray[][];
// main...
public static void main(String[] args) {
int depth = Integer.MAX_VALUE;
MyTreeCreator createTree1 = new MyTreeCreator();
java.awt.image.BufferedImage im = null;
QtNode firstNode = new QtNode();
try {
im = javax.imageio.ImageIO.read(new File("g:\\kreis.png"));
}
catch (IOException ex1) {
}
int height = im.getHeight();
int with = im.getWidth();
try {
createTree1.nodegenerator(im, 0, 0,2*with, with,height);
}
catch (Exception ex) {ex.printStackTrace();
}
System.out.println("The Quadtree is created");
}
public MyTreeCreator() {
}
public MyTreeCreator(String filename, int depth){
QuadTree qt=new QuadTree(filename);
System.out.println(""+qt);
int size = qt.initialSize;
imageArray = new int[size][size];
imageArray = qt.toArray(depth);
this.setPreferredSize(new Dimension(size,size));
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().add(this);
f.pack();
41
f.setVisible(true);
}
public void paintComponent(Graphics g){
for (int y = 0; y<256;y++){
for(int x=0;x<256;x++){
int c=imageArray[y][x];
Color col=new Color(c,c,c);
g.setColor(col);
g.fillRect(x,y,1,1);
}
}
}
public void nodegenerator(java.awt.image.BufferedImage im, int bsx1, int bsy1, int size1, int with, int height)
{
int depth =0 ;
int dummy=0;
Color colr;
int bsx = bsx1;
int bsy = bsy1;
int size = size1;
size = size/2;
if( uniqueClour(im,bsx,bsy,size,with,height).equals("white") )
{
System.out.println("white");
}
if( uniqueClour(im,bsx,bsy,size,with,height).equals("black") )
{
System.out.println("black");
}
if( uniqueClour(im,bsx,bsy,size,with,height).equals("misch") )
{
System.out.println("*******************256a**********************");
System.out.println("misch");
System.out.println("size_a=" + size);
nodegenerator(im,bsx,bsy,size,with,height);
System.out.println("*******************256b**********************");
System.out.println("size_b=" + size);
nodegenerator(im,bsx+size,bsy,size,with,height);
System.out.println("*******************256c**********************");
System.out.println("size_c=" + size);
nodegenerator(im,bsx,bsy+size,size,with,height);
System.out.println("*******************256d**********************");
System.out.println("size_d=" + size);
nodegenerator(im,bsx+size,bsy+size,size,with,height);
}
}
public void nodegenerator1(QtNode firstNode,java.awt.image.BufferedImage im, int bsx1, int bsy1, int size1, int with, int height)
{
int depth =0 ;
int dummy=0;
Color colr;
int bsx = bsx1;
int bsy = bsy1;
42
int size = size1;
if (leafwhite(im,bsx,bsy,size,with,height) && leafblack(im,bsx,bsy,size,with,height))
{
firstNode.grayValue=0;
firstNode.leaf = false;
}
else
{
size = size/2;
firstNode.children[0] = new QtNode();
firstNode.children[1] = new QtNode();
firstNode.children[2] = new QtNode();
firstNode.children[3] = new QtNode();
nodegenerator1(firstNode.children[0],im,bsx,bsy,size,with,height);
nodegenerator1(firstNode.children[1],im,bsx+size,bsy,size,with,height);
nodegenerator1(firstNode.children[2],im,bsx,bsy+size,size,with,height);
nodegenerator1(firstNode.children[3],im,bsx+size,bsy+size,size,with,height);
}
firstNode.toString();
}
public boolean leafblack(java.awt.image.BufferedImage im,int bsx, int bsy, int size, int with, int height)
{
boolean black = true;
int pix = 0;
for (int y=bsy;y<bsy+size && y < height;y++)
for (int x=bsx;x<bsx+size && x < with;x++)
{
pix = im.getRGB(x, y);
int r = (pix >> 16) & 0xFF;
int g = (pix >> 8) & 0xFF;
int b = pix & 0xFF;
System.out.println(" RGB-LeafBlack=" + r + "|" + g + "|" + b) ;
if (r > 1 && g > 1 && b > 1)
{
System.out.println(" RGB_Leaf_Enthaelt_Doch_white = " + r + "|" + g + "|" + b);
return false;
}
}
return black;
}
public boolean leafwhite(java.awt.image.BufferedImage im,int bsx, int bsy, int size, int with, int height)
{
boolean white = false;
boolean black = false;
int pix = 0;
for (int y=bsy;y<bsy+size && y < height;y++)
for (int x=bsx;x<bsx+size && x < with;x++)
{
pix = im.getRGB(x, y);
int r = (pix >> 16) & 0xFF;
int g = (pix >> 8) & 0xFF;
int b = pix & 0xFF;
System.out.println(" RGB-Leafwhite=" + r + "|" + g + "|" + b);
if (r < 1 && g < 1 && b < 1) // 0 0 0 = black
{
System.out.println(" RGB_Leaf_Enthaelt_Doch_Black = " + r + "|" + g + "|" + b);
return false;
43
}
}
return white;
}
public String uniqueClour(java.awt.image.BufferedImage im,int bsx, int bsy, int size, int with, int height)
{
boolean white = false;
boolean black = false;
String farbe = null;
int pix = 0;
for (int y=bsy;y<bsy+size && y < height;y++)
for (int x=bsx;x<bsx+size && x < with;x++)
{
pix = im.getRGB(x, y);
int r = (pix >> 16) & 0xFF;
int g = (pix >> 8) & 0xFF;
int b = pix & 0xFF;
// System.out.println(" RGB-Leafwhite=" + r + "|" + g + "|" + b);
if (r < 1 && g < 1 && b < 1) // 0 0 0 = black
{
black = true;
}
if (r > 1 && g > 1 && b > 1) // 255 255 255 = white
{
white = true;
}
if (black & white) return "misch";
}
if (white) farbe= "white";
if (black) farbe = "black";
return farbe;
}
public void fillArray(int[][]im, int bsx, int bsy, int size, int value){
for (int y=bsy;y<bsy+size;y++)
for (int x=bsx;x<bsx+size;x++)
im[y][x]=value;
}
public void fillGrayValues(QtNode node){
if (node.leaf)
return;
else{
int g = 0;
for (int i = 0; i<4;i++){
fillGrayValues(node.children[i]);
g += node.children[i].grayValue;
}
node.grayValue = g/4;
}
}
}
Wir erzeugen eine Quadtree für die folgende kreisförmige Form:
44
Hier ist das Output des Java-Programms:
Wir können wiederum aus dieser Feldspeicherung (Array Storage) die graphische Form ablesen und
darstellen (siehe Java-Code auf www.go4runisia.de ):
Autor
Document
Kategorie
Kunst und Fotos
Seitenansichten
5 474
Dateigröße
2 044 KB
Tags
1/--Seiten
melden