Thread kollisionen zweier polygonen (16 answers)
Opened by #Kein Kommentar at 2010-12-10 18:47

#Kein Kommentar
 2010-12-12 13:41
#143499 #143499
User since
2007-06-09
575 Artikel
HausmeisterIn
[default_avatar]
also ist das so ne art infinitesimalrechnung? ich teile die polygone in ganz viele kleine rechtecke auf und teste, ob sie sich überlappen?

ist das sehr rechenintensiv? wahrscheinlich habe ich später um die 100 polygone, welche ich ständig vergleichen muss.

gibt es da einen fertigen algorithmus? ansonsten versuche ich mal etwas selber zu basteln, allerdings will ich das rad auch nicht neu erfinden =)

ich habe mal ein kleines beispiel-programm mithilfe deiner angaben gebastelt. in zeile 90 müsste eben der algorithmus stehen, welcher prüft, ob sich die zwei polygone überschneiden.

Code (perl): (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#!/usr/bin/perl -w

use strict;
use warnings;

use Tk;
use Tk::Canvas;

my $mw = MainWindow->new();
$mw->state('zoomed');

my $canvas =
        $mw->Canvas()->pack(-expand => 1, -fill => 'both');
        
my %coord_1 = (
        'a' => [100,100,'b'],
        'b' => [200,100,'c'],
        'c' => [200,200,'d'],
        'd' => [150,250,'e'],
        'e' => [100,200,'a'],
);

my %coord_2 = (
        'f' => [250,250,'g'],
        'g' => [300,200,'h'],
        'h' => [300,300,'i'],
        'i' => [250,350,'j'],
        'j' => [200,300,'f'],
);

drawPolygon($canvas, \%coord_1, 'yellow');
my $moving_pol =  drawPolygon($canvas, \%coord_2, 'lightblue');

$mw->bind('<Up>', sub{movePolygon($canvas,$moving_pol,0,-5);});
$mw->bind('<Down>', sub{movePolygon($canvas,$moving_pol,0,5);});
$mw->bind('<Left>', sub{movePolygon($canvas,$moving_pol,-5,0);});
$mw->bind('<Right>', sub{movePolygon($canvas,$moving_pol,5,0);});

Tk::MainLoop;

sub drawPolygon{
        my $widget      = shift;
        my $coord       = shift;
        my $color       = shift;
        
        my @coords;
        foreach my $point (sort keys %{$coord}){
                push(@coords, $coord->{$point}->[0], $coord->{$point}->[1]);
        }

        return  $widget->createPolygon(
                @coords,
                -fill => $color,
                -outline => 'black',
        );
}

sub movePolygon{
        my $widget      = shift;
        my $polygon = shift;
        my $x_move = shift;
        my $y_move = shift;
        
        foreach my $point (sort keys %coord_2){
                $coord_2{$point}->[0] += $x_move;
                $coord_2{$point}->[1] += $y_move;
        }

        $widget->move($polygon, $x_move, $y_move);
        
        if (PolygonsOverlap(\%coord_1,\%coord_2)){
                $widget->itemconfigure(
                        $polygon, 
                        -outline        => 'red',
                        -fill => 'lightgreen',
                );
        }else{
                $widget->itemconfigure(
                        $polygon, 
                        -outline        => 'black',
                        -fill => 'lightblue',
                );
        }
}

sub PolygonsOverlap{
        my %coord_1 = %{shift()};
        my %coord_2 = %{shift()};
        
        #################################
        # algorithmus zum testen, ob sich
        # die polygone überschneiden.
        #################################
}

Last edited: 2010-12-12 13:43:23 +0100 (CET)
Gerade weil wir alle in einem Boot sitzen, sollten wir froh sein, dass nicht alle auf unserer Seite sind

View full thread kollisionen zweier polygonen