kollisionsabfrage von sechsecken

[Guest]

hey,

ich mach gerade für ein risiko spiel zufällig generierte karten. funzt schon ganz gut, allerdings
steh ich nun vor nem problem und bin mir nicht sicher wie ich es am besten machen soll:

nach bestimmten regeln werden während des generierungs-prozesses der spielkarte einzelne länder (zufällig groß) aneinandergehängt. im moment allerdings kann es vorkommen, dass sich diese länder (durch sechsecke implementiert und dargestellt) überschneiden oder ineinander liegen.

bisher sind meine informationen über ein land lediglich die seitenlänge einer kante des sechsecks sowie die koordinaten der 6 eckpunkte.

allerdings müsste ich nun für jeden möglichen Punkt im Panel bestimmen können, ob er Teil eines Landes ist.

Und das will ich nun Fragen: Wie kann ich alle Punkte innerhalb eines Landes rausfinden, bzw. ist es überhaupt sinnvoll eine Liste zu machen mit allen Punkten, oder geht das besser mit "Grenzlinien" eines Landes, oder oder..

Bin mir unschlüssig und wäre froh über Ratschläge.

Nochmal zusammengefasst: Brauche eine Methode die über einen gegebenen Punkt aussagt, ob er Teil eines Sechsecks ist, oder anders gesagt: Innerhalb der Fläche liegt, die die 6 Eckpunkte eines Sechsecks einschließen.

Danke

 

[Guest]

edit

was mir grad noch einfällt:

so ein sechseck kann man ja schön in 2 dreiecke und ein viereck zerlegen.
falls die API da irgendwas anbietet.. dann wär das natürlich ne option.

 

[Wildcard]

Schau dir mal die Klasse Polygon an.

 

[Marco13]

Und nachdem du dir die klasse Polygon angeschaut hast, überleg' mal, ob du die Sechsecke wirklich frei im Raum platzieren willst, und ob das nicht einfach Elemente eines ("schief gezeichneten") 2D-Arrays sein sollen, bei denen man sich die Koordinaten des Mittelpunktes direkt aus den Array-Indizes berechnen kann....

 

[Guest]

okay also ich will das nun mit polygonen machen, da die auch noch andre schöne dinge anbieten wie z.B. ob ein geklickter Punkt im Panel in diesem Polygon liegt etc..

Jetzt muss ich irgendwie den PathIterator verwenden, scheitere aber.

Hier erstmal die Problemstellung:

Ich adde meinem Polygon solange zufällig Punkte, bis ein Punkt geaddet wurde, der schon in der Liste ist.
Grafisch heisst das: Es wird solange der Umriss eines Polygons gezeichnet, bis es sich abschließt.

Nun ist es aber so, dass ich dann nicht alle geaddeten punkte malen möchte, sondern die "abstehenden" erst löschen will.

D.h.: Alle Punkte, die VOR dem punkt, auf den zuletzt gestoßen wird, geaddet wurden, müssen wieder raus.

Tja, und jetzt check ich halt irgendwie nicht wie ich den Iterator verwenden soll. z.B. wäre es interessant zu wissen,
wo er anfängt. Also zu welchem Punkt springt er wenn ich ein mal "next()" mache?

Ich wollte es per System.out.println selbst rausfinden, aber das geht nicht:

        PathIterator iter = getPathIterator(null);
        while (!iter.isDone()) {
            iter.next();
            System.out.println(iter.currentSegment( ??? ));
        }

weil currentSegment() als Parameter ein double-Array will, und ich bin aus der API nicht schlau geworden, was ich darein schreiben soll. Ich will ja eben den Punkt haben, und nicht erst eingeben müssen?

Zusammenfassung: Ich will mich vom letzten geaddeten Punkt nach hinten durchhangeln, bis ich auf den stoße, mit dem der letzte Punkt kollidiert ist. Alles, was davor geaddet wurde, muss raus.

Wie mach ich das?

Danke

 

[Guest]

... also ich bin jetzt schon etwas weiter, aber jetzt müsste ich eben Punkte aus dem Polygon nehmen und bin überrascht dass es dafür keine Methode gibt..

Ich würde es EXTREM umständlich hinkriegen indem ich einige dinge tu und dann ein neues Polygon erstelle, aber das wird mir zu kompliziert.

Deshalb frag ich jetzt einfach mal:

Falls das hier der falsche Weg ist (?) wie würdet ihr zufällig generierte "Flecken" erstellen lassen?
Es handelt sich jetzt (wer oben gelesen hat ) nicht mehr um Sechsecke sondern um wie gesagt "Flecken", also eine zufällig gezeichnete Linie, die, wenn sie sich abshcließt, halt so eine Umrandung darstellt.

Thema ist nach wie vor: Wie krieg ich die Überbleibsel dann weg?

Zur grafischen Anschauung hab ich hier noch was gemacht:



Wäre echt dankbar für Tipps. (@ marco13: würde sowas auch mit 2d-array gehen? wäre halt ein sehr großes array..
[800][500] oder so.

 

[Marco13]

Hm. Das Vorgehen an sich klingt gewagt. Bist du sicher, dass du irgendwann an einem Punkt ankommst, den es schon gibt? Musst du GENAU an den gewünschten Punkt kommen, oder reicht es, wenn ein "Schritt" (also ein Liniensegment) ein anderes Lininensegment schneidet? Wenn nicht: Was passiert bei Polygonen, die sich selbst überschneiden? Wie verhinderst du, dass spiralförmig nach außen gelaufen (und nie mehr ein schon vorhanderen Punkt getroffen) wird?

Wie auch immer. Ich würde dir empfehlen, die eigentlichen Berechnungen (bzw. das Erstellen der Felder) nicht mit der Polygon-Klasse zu machen. Die ist - wie du schon gemerkt hast - SEHR unhandlich. (SEHR, SEHR unhandlich).

Stattdessen könntest du eine eigene Klasse dafür basteln, die die gewünschten Methoden anbietet, und die du (wenn du fertig bist) in ein Polygon umwandeln kannst.

Den Code nicht so ernst nehmen, der war nur zum Testen und produziert halt selbstüberschneidende Polygone - das zu verhindern ist dein Job :wink:

import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.util.List;


class Area
{
    private List<Point> points = new ArrayList<Point>();

    public void createRandomPoint()
    {
        int x = (int)(Math.random()*10) * 10;
        int y = (int)(Math.random()*10) * 10;
        Point point = new Point(x,y);
        points.add(point);
    }

    boolean isClosed()
    {
        if (points.size() < 3)
        {
            return false;
        }
        Point pointA = points.get(points.size()-1);
        int index = indexOf(pointA, points.size()-1);
        return index != -1;
    }

    private int indexOf(Point pointA, int lastIndex)
    {
        for (int i=0; i<lastIndex;i++)
        {
            Point pointB = points.get(i);
            if (pointA.distance(pointB) == 0)
            {
                return i;
            }
        }
        return -1;
    }

    public void cutTheTrashAway()
    {
        Point pointA = points.get(points.size()-1);
        int index = indexOf(pointA, points.size()-1);
        if (index != -1)
        {
            for (int i=0; i<index; i++)
            {
                points.remove(0);
            }
        }
    }



    public Polygon createPolygon()
    {
        int n = points.size();
        int xpoints[] = new int[n];
        int ypoints[] = new int[n];
        for (int i=0; i<n; i++)
        {
            Point point = points.get(i);
            xpoints[i] = point.x;
            ypoints[i] = point.y;
        }
        Polygon polygon = new Polygon(xpoints, ypoints, n);
        return polygon;
    }


}




class AreaTest
{
    public static void main(String args[])
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setSize(400,400);

        Area area = new Area();
        while (!area.isClosed())
        {
            area.createRandomPoint();
        }
        area.cutTheTrashAway();
        final Polygon polygon = area.createPolygon();

        f.getContentPane().add(new JPanel()
        {
            public void paintComponent(Graphics g)
            {
                super.paintComponent(g);
                ((Graphics2D)g).draw(polygon);
            }
        });
        f.setVisible(true);
    }
}

 

[0x7F800000]

Hey die aufgabe gefällt mir, ich finds sehr interessant, werd's irgendwann mal proggen wenn ich die klausuren geschrieben hab... :toll:

ich würde die ganze sache komplett anders angehen. Ich würde einfach folgendes machen: Für jedes land erstellst du anfangs ein kleines dreieck.

Und dann machst du wiederholt folgendes:

1) jede kante AB von der Landgrenze nehmen.
2) prüfen ob AB lang genug ist (das land soll an keiner stelle zu schmal werden)
3) einen zufälligen punkt X aus einem Kreis um den kantenmittelpunkt nehmen (radius vordefiniert)

-prüfen, ob X auf dem unbesetzten territorium liegt (landesgrenze sollte ja nicht durch irgendein anderes land verlaufen)
-prüfen, ob strecken AX und BX die bereits vorhandene landsgrenze schneiden (landesgrenze darf keine knoten haben, sonst wäre der "offene Kern" des Landes nicht zusammenhängend)
-falls beides erfüllt: kante AB durch zwei kanten AX und XB ersetzen (eine doppelt verkettete Liste mit punkten wäre da am sinnvollsten)
-falls nicht: neues X wählen


damit dürftest du mehrere zufällig wachsende knotenfreie disjunkte amöben erhalten, die nach ein paar iterationen die gesamte fläche ausfüllen. Wenn die kollidieren, könnte man vielleicht noch ein wenig optimieren, und kleine verbleibende lücken sofort schliessen, ohne viel rechenzeit zu verschwenden.

dazu wärs wohl am praktischsten, wenn du dir deine eigene polygonklasse schreiben würdest, die auch mit doppelt verketteten listen arbeitet: mit arrays wird das ganze einfügen-entfernen viel zu lahm.

soviel zu meiner idee. Ich setz die in zwei wochen mal vielleicht in code um... Jetzt keine zeit :autsch:

 

[Guest]

danke erstmal, ich hatte es zuerst auch so gemacht bin dann auf polygone umgestiegen weil ich das problem hatte nicht zu wissen ob ein punkt im polygon liegt. aber so ein misch-ding mit polygon und arraylist hatte ich mir auch überlegt, ist zwar z.T. doppelt gemoppelt aber was solls..

die sache mit selbstüberschneidung erübrigt sich im prinzip, da er (siehe meine grafik) sich automatisch beim überschneiden abschließt. und falls ein so enstandenes polygon viel zu klein ist wird es geköscht und neu gemacht.

sooo wild wäre das nicht, weil das ganze ist für ein risiko spiel und da wird die map einmal erstellt und dann ist gut.
das kann dann ruhig ein paar sekunden dauern, "please wait while generating map..." wär da nich so schlimm.

aber das ganze ist echt einigermassen umständlich.. naja ich schau mal was ich mir aus deinem code ziehen kann und zieh das ganze neu auf.

melde mich aber zu einer einigermassen hohen wahrscheinlichkeit wieder

 

[Marco13]

Hm. Dann müßtest ud aber wirklich die Überschneidungen zwischen den Segmenten ausrechnen (was sonst rauskommt, sieht man ja an meinem Code :roll: ). Ich würde dir aber empfehlen, dir für die Generierung ein System zu überlegen, das über den Ansatz "mach so lange irgendwas, bis dieses 'irgendwas' zufällig(!) kein Mist mehr ist" hinausgeht.

BTW: Es werden bei dieser Lösung mit der Area-Klasse die Daten ja nicht unbedingt doppelt gespeichert. Die Klasse Faßt nur das Erstellen es Polygons (auf besis von Handlichen, Bequemen Datenstrukturen) zusammen. (Könnte z.B. auch Objekte der Klasse "Edge" enthalten, die die Schnittpunktberechnungen anbieten usw.). Später brauchst du (wenn du willst) nurnoch die generierten Polygon zu verwenden...

 

[Guest]

jo, genau das ist die idee. im moment generiert er eben so lang wild rum, bis es passt.
erst wenn es passt castet er das ganze zu nem polygon. und später im spiel wird nur noch mit diesen ("guten") polygonen gerechnet.

ich bin jetzt schon kurz vorm ziel, ist zwar recht umständlich aber zumindest schafft er es jetzt schon ein (einziges) polygon zu erstellen, dass sich nicht selbst überschneidet und das eine gewisse mindestgrösse hat.

allerdings ist nohc irgendwo n bug drin, naja mal sehn.

die frage stellt sich, wie realisierbar das so noch ist, wenn ein 2. und 3.polygon hinzukommen.
die sollen sich nämlich an die schon existenten polygone dranhängen, die karte soll ja keine lücken haben.

ich bin gespant... ^^

 

[Janus]

guck dir zu dem thema mal http://de.wikipedia.org/wiki/Hexagon#Sechseckige_Parkettierungen an. reguläre sechsecke werden aus genau diesem grund schon seit ewigkeiten für diverse strategiespiele verwendet. mit denen sind solche berechnungen nämlich unglaublich simpel.

und wenn du keine regulären sechsecke haben willst: verwende sie trotzdem lass alle berechnungen auf regulären sechsecken basieren und wende abschließend einfach eine transformation an, die die dinger dann so zusammenstaucht, dass sie entsprechend deinen vorstellungen aussehen. isometrische ansicht o.ä.

 

[Quaxli]

Und nachdem du dir die klasse Polygon angeschaut hast, überleg' mal, ob du die Sechsecke wirklich frei im Raum platzieren willst, und ob das nicht einfach Elemente eines ("schief gezeichneten") 2D-Arrays sein sollen, bei denen man sich die Koordinaten des Mittelpunktes direkt aus den Array-Indizes berechnen kann....

Diese Bemerkung von Marco13 zusammen mit der von Janus scheint mir der geeignetste und am wenigsten aufwändige Weg um sowas zu realisieren. Bis jetzt hast Du ja gerade mal die Karte gebastelt und noch nicht mal Figuren gezogen oder ähnliches...

 

[Guest]

jo also es ist wirklich das (einzig) beste mit sechsecken. ich hatte das ja schon mal so, wollte dann aber polygone damit ich die mausklicks zuordnen kann. aber mit dem tip des castens nach polygon is das ja dann erledigt.

wegen der parkettierung: ich will unterschiedlich große länder, wo unterschiedlich viele einheiten drauf passen.
dann leg ich halt einfach 3 oder 4 feste größen fest die ausgewürfelt werden, und wenn sich ein kleineres land an ein größeres dranhängen möchte, oder andersrum, dann zentriert es sich halt an der kante oder so.

zumindest mit reinen polygonen ist das echt zu krass, ein land wie gesagt okay, aber die anderen dranhängen is mir jetzt echt zu dumm.

danke für den tipp mit casten und sechseck!

 

[Guest]

update der problematik

okay also es werden nun sechsecke erfolgreich generiert und in ein polygon gecastet, auch hängen sie sich aneinander.

jetzt steh ich vor dem problem dass ich rausfinden muss wenn ein punkt innerhalb des poylgons liegt, damit sie sich bei der generierung nicht überschneiden. ich caste das ganze total falsch in ein polygon scheinbar, denn ich übergebe ihm nur die 6 eckpunkte, und nur diese koordinaten enthält es dann auch.

aber irgendwie müsste ich alle punkte da rein kriegen, sonst bringt mich das ganze mit dem polygon null weiter und ich hab nix anderes als ein sechseck (array mit 6 Punkten...) als polygon dargestellt.

echt schön langsam fällt mir keine lösung mehr für das problem ein...

wie kann ich ein polygon erstellen dass alle punkte eines sechecks, also auch den kompletten "inhalt" enthält?
ich hab halt nur die 6 eckpunkte (und ich weiss natürlich auch wie es aussieht).

ich könnte glaub ich über 300 zeilen code alle punkte mehr oder weniger einzeln adden, aber das is ja blödsinn..

was würdet ihr mir jetzt empfehlen? kann das denn SO schwer sein?
ich bin echt am verzweifeln.. ich kann irgendwie einfach nicht glauben dass es für geometrische objekte jenseits von rechtecken in java keine gescheiten methoden gibt!
wie kann es sein dass es eine klasse für polygone gibt die aber keine methode entählt, den inhalt des polygons zu bestimmen? ich meine worin besteht dann der sinn dieser klasse? das is doch das wichtigste find ich! irgendwie fühl ich mich grad von der API im stich gelassen...

ich weiss einfach ums verrecken nicht, wie ich das ganze aufziehen soll damit es funktioniert. es ist ja jetzt schon fast lächerlich kompliziert, wie ich es im moment habe.

bitte... helft mir weiter.

wie überprüfe ich, ob ein neues sechseck in einem der bereits existierenden liegt, es also überschneidet? kann doch nicht sein dass das scheinbar unmöglich ist :bahnhof:

 

[Wildcard]

Polygon hat genügend contains intersects und inside Methoden.

 

[Guest]

also es gibt da rectangle2d, aber es is ein sechseck kein rechteck.

das problem ist ja vorallem: das polygon, in das ich das sechseck caste...wie mach ich das?
wie gesagt im moment hält es nur die 6 eckpunkte. ich dachte, genau das is der sinn von der klasse polygon, dass man ihm eckpunkte gibt und er dann weiss was er is..

aber das tut er nich, ich müsste jeden punkte wirklich einzeln adden. das macht die klasse total überflüssig, statt
xpoints[] und ypoints[] kann ich mir doch dann selber n array von points machen und gut is.

wozu diese klasse?

das is doch mein problem :autsch: wie kann ich mein sechseck in ein polygon casten, dass danach auch wirklich alle punkte in der eigenfläche hat, also dass erkennt wenn man innerhalb des polygons geklickt hat oder eben ein punkt darin liegt.

es gibt ja auch contains(Point p), nur um das polygon zu erstellen muss ich das alles einzeln machen, pixel für pixel.
womit ich wieder bei der frage bin: was hab ich an der klasse polygon falsch verstanden? weil so wie ich sie im moment nutze (zu nutzen weiss) bringt sie mir rein gar nix, und is nix anderes als eine liste von punkten, die ich aber per hand einzeln adden müsste.

6 punkte -> polygon, dass weiss wie es aussieht. WIE?

 

[Wildcard]

Ein Polygon nimmt alle übergebenen Punkte, verbindet sie logisch durch Linien und verbindet am Ende den ersten mit dem letztem Punkt. Die dadurch entstandene Fläche ist das Polygon.
API-Doc lesen hilft übrigens wenn man eine Klasse nicht versteht. Dazu ist sie da.

 

[Guest]

ich lese die APIs durchaus, aber ich finde die API doc ist zu großen teilen extrem schlecht erklärt.

z.B. der "unterschied" zwischen contains(Point) und contains(Point2D).

hört sich so an als ob contains(Point) auch die Grenzen berücksichtigt, Point2D aber nicht. generell ist das total uneinheitlich hingeklatscht. ich hab neulich in einer klasse ne methodenbeschreibung gesehen wo sie ein erfundenes wort benutzen, es in anführungzeichen setzen und dann denken man versteht es. so ähnlich wie:

"... sets the "grunchy" coordinates."

und das soll dann ne erklärung sein, das is nich mal n wort. ohne beispiel is sowas dann schon wacklig find ich.

aber ich will ja nicht weiter flamen, ich les die APIs zumindest, wenn ich frag, dann hab ichs halt nicht verstanden.

und so is es eben im moment: ihr habt mir vorgeschlagen, die klasse polygon zu verwenden. ich weiss aber nicht wie.
weil ich es nicht hinkrieg mehrere länder zu generieren und testen, ob sie sich überschneiden.
weil die grenzlinie zweier länder die selbe ist, also würde ein contains() immer true geben.

ich brauch contains(point WITHIN the polygon, EXCLUDING the border).

gibts sowas? hab n kleinen test mit contains(point und point 2d) gemacht, scheint scheinbar das gleiche zu sein.
aber keine ahnung, is ja nicht erklärt.

das sind halt immer so sachen wo ich dann seit 30 stunden oder mehr rumtu, und mir mehr oder weniger immer das gleiche gesagt wird, aber ich nicht weiss wie KONKRET ich sowas machen soll, weil ich immer auf probleme stoß.

z.B. das eben erwähnte mit den überschneidungen.

polygon hilft hier evtl nicht weiter? keine ahnung? ich hab da keine erfahrung, nur weil ich in der API über ne klasse lese heisst das nicht, dass ich entscheiden kann ob das die richtige für mich ist.. müsst ihr halt verstehen

also nochmal: wie würdet ihr so eine karte aus sechsecken erstellen lassen? bei mir sinds im konstruktor schon über 300 zeilen code, ich wette ich mach da was falsch. aber kann es nicht besser.

egal wie oft ich die API noch les - sorry :!:

 

[schalentier]

Also ich les hier schon seit anfang deines Threads mit, aber so richtig verstanden hab ich immer noch nicht was du willst.

Anfangs hast du von Sechsecken geredet. Dann von irgendwelchen Polygonzuegen. Jetzt sinds wieder Sechsecke. Ich schlag vor, du ueberlegst dir zunaechst, komplett ohne Quellcode, was genau du eigentlich machen willst.

Ich seh grundsaetzlich 2 Moeglichkeiten:

- Vektororientiert unter zuhilfenahme eines bestimmten Gittersystems (Grid). Regelmaessige 6-Ecke machen sich da recht gut (Lektuere).
- Pixelorientiert, indem du eine 2d Map nimmst und dort pro Koordinate die Id des Landes speicherst.

Vektororientiert braucht weniger Speicher, dafuer mehr Rechenoperationen. Zudem bist du auch das grundlegende Gitter beschraenkt, musst also immer mit 6-Ecken arbeiten (allerdings kapier ich nicht, wie du ein Risikobrett aus 6-Ecken bauen willst).

Pixelorientiert braucht mehr Speicher ist dafuer total einfach. Du musst nur die Anzeige-Koordinaten in Map-Koordinaten umrechnen (Skalieren, evtl. Verschieben) und dann in der Map guggen, was dort fuer ein Land ist. Selbstverstaendlich darfst du so die Karte nicht in jedem Frame komplett neuzeichnen, sondern musst einen entsprechenden Backbuffer benutzen.

Viel Spass noch ;-)

 

[Janus]

wie würdet ihr so eine karte aus sechsecken erstellen lassen?

ich würds so machen:
ich nehme erstmal ein grid aus sechsecken fixer ausmaße (40x60, 120x180, o.ä.), das lässt sich sehr einfach "generieren".
dieses grid wird dann eingefärbt, wobei färbung hier für zuweisung zu ländern steht.
ich bestimme die anzahl der länder und für jedes land einen faktor "größe" zwischen 0 und 1.
jetzt wird auf dem grid für jedes land ein einzelnes raster festgelegt. dabei achte ich darauf, dass der abstand zwischen den punkten ein gewisses mindesmaß nicht unterschreitet. z.b. 5 raster abstand.
jetzt beginnt eine schleife.
in jeder iteration werden jedem land neue rasterfelder zugewiesen. wieviele das in jeder iteration werden, ist vom faktor abhängig. neue rasterfelder werden immer an den horizont des landes angeklebt. das sind die außenliegenden felder.
wenn ein feld bereits von einem land belegt ist, wird ein anderes freies feld gesucht.
das mache ich solange, bis kein land mehr wachsen kann. aufgrund der vorgehensweise müssen zwangsläufig alle felder der karte einem land zugewiesen sein.

in einem abschließenden schritt könnte man noch die größe aller länder überprüfen und wenn eines wesentlich zu groß oder klein geraten ist, nachkorrigieren. eine korrekturschleife sähe dann so aus, dass je zwei benachbarte länder verglichen werden, und einem zu kleinen ein angrenzendes feld eines zu großen landes zugewiesen wird.

wenn die karte danach immer noch nicht den vorstellungen entspricht, kann man nochmal beginnen. die wahrscheinlichkeit dazu ist aber recht gering.

 

[Quaxli]

So ähnlich wie Janus würde ich es auch machen. Das grundsätzliche Problem scheint bei Dir das zu sein:

...und so is es eben im moment: ihr habt mir vorgeschlagen, die klasse polygon zu verwenden. ich weiss aber nicht wie.
weil ich es nicht hinkrieg mehrere länder zu generieren und testen, ob sie sich überschneiden.

Wenn Du die Vorgehensweise von Janus verwendest hast Du das Problem nicht.

Du kannst auch mal nach "Killer Game Programming" googeln, da gibt es auch ein Beispiel, Karten mit Rauten bzw. Sechsecken.

 

[Marco13]

Hm. Die Empfelung, die Klasse "Polygon" zu verwenden, wurde unter bestimmten "Vorbedingungen" gemacht (im Zweifelsfall: Der Vorbedingung, dass du sie dann einfach verwendest und der Thread damit abgehakt ist :wink: ). Wenn du mit regelmäßigen Sechsecken arbeitest, besteht kaum noch ein Grund, die Klasse Polygon zu verwenden, sondern eher (wie ich schon ganz am Anfang gesagt habe) einen "schiefen gezeichneten" Array, der die Sechsecke repräsentiert. Der Link von schalentier veranschaulicht gut, was ich damit meinte. Damit brauchst du auch nichtmehr die contains-Methode, sondern kannst anders (und nebenbei effizienter) ausrechnen, in welchem Sechseck ein Punkt liegt.

EDIT: Schau vielleicht auch mal hier: http://www.codeproject.com/KB/cs/hexagonal_part1.aspx

 

[trazzag]

ich hab auch mal angefangen ein kleines Spiel das auf 6-Ecken basiert zu schreiben. Ich poste mal ein paar Code-Fragmente, die die vllt. weiter helfen.

Zunächst einmal habe ich GeneralPath statt Polygon zur Darstellung der Hexagone verwendet:

/**
	 * Constructs a polygon as a GeneralPath Object. Used to construct the
	 * hexagons.
	 * 
	 * @param sides
	 *            Number of sides of the polygon (for a hexagon use 6).
	 * @param x
	 *            An array containig the x-coords for the polygon-points.
	 * @param y
	 *            An array containig the y-coords for the polygon-points.
	 * @param closed
	 *            Defines if the polygon should be closed (set true for a
	 *            hexagon).
	 * @return A GeneralPath Object (in this class always a hexagon).
	 */
	private GeneralPath makePolygon(int sides, double[] x, double[] y,
			boolean closed) {
		GeneralPath polygon = new GeneralPath(GeneralPath.WIND_EVEN_ODD, sides);
		polygon.moveTo(x[0], y[0]);
		for (int i = 1; i < sides; i++) {
			polygon.lineTo(x[i], y[i]);
		}
		if (closed) {
			polygon.closePath();
		}
		return polygon;
	}

Jedes Hexfed ist bei mir ein eigenes Objekt (public class Hex extends JComponent implements MouseInputListener)

Also, die eigentlich Darstellung erfolgt, wie bereits geschrieben über GeneralPath - dann kannst du einfach über folgende Methode abfragen, ob ein Punkt in deinm Hexagon ist:

// Berechnung der Koordinaten habe ich hier mal ausgespart
GeneralPath hexagon = makePolygon(6, xCoords, yCoords, true);
Point point = //wo auch immer du deinen Punkt herbekommst
if (hexagon.contains(point)) //...mache irgendwas

 

[Guest]

okay danke euch allen erstmal!
ich werde diesen thread auf jeden fall wieder rauskramen wenn ich sowas nochmal mache.

allerdings hab ich jetzt schon so viel code geschrieben und stehe echt so kurz vorm ziel.
nun dachte ich, ich hab die lösung gefunden.

jetzt versteh ich aber scheinbar die contains-methode von polygonen falsch.
ich hab hier 2 polygone mit ihren 6 eckpunkten:

java.awt.Point[x=396,y=329]
java.awt.Point[x=438,y=287]
java.awt.Point[x=480,y=329]
java.awt.Point[x=480,y=389]
java.awt.Point[x=438,y=431]
java.awt.Point[x=396,y=389]

java.awt.Point[x=354,y=227]
java.awt.Point[x=396,y=185]
java.awt.Point[x=438,y=227]
java.awt.Point[x=438,y=287]
java.awt.Point[x=396,y=329]
java.awt.Point[x=354,y=287]

wie man sieht, gibt es zwei(!) punkte, die gleich sind: 396,329 und 438,287.

nun lauf ich alle eckpunkte des zweiten polygons in einer schleife durch:

if (firstPolygon.contains( currentEckpunktdesZweitenPolygons )

das komische ist: manchmal kommt nur 1 mal true raus, manchmal sogar gar nicht!
aber eindeutig gibt es ja wohl 2 punkte, die gleich sind! das hab ich mir ausgeben lassen.
daran gibt es nichts zu rütteln.

also wie testet diese contains-methode? bezieht die die grenzlinie des polygons mit ein, oder nicht?
ich verstehe nicht wieso nicht IMMER zwei mal true raus kommt (ein neues polygon heftet sich IMMER an eine kante des anderen, es gibt also IMMER 2 punkte die sie beide gemeinsam haben... Das sieht man auch jedesmal an den outprints von den koordinaten. es gibt in der tat immer 2 gleiche punkte)

also was genau testet die contains(Point) methode der polygon-klasse? danke

 

[Guest]

hey leute sorry, genau das meinte ich mit der API... was soll das?

wie funktioniert diese sch*** contains-methode? anscheinend nicht so wie es klingt?

falls ich jetzt irgendwie mein gehirn über nacht verloren hab, wieso zum teufel funktioniert das hier nicht:

        for (int i = 0; i < otherSectors.size(); i++) {
            for (int thisV = 0; thisV < 6; thisV++) {
                if (otherSectors.get(i).contains(vertices[thisV])) {
                    System.out.println("in einem anderen sektor");
                    return true;
                }
            }
        }

otherSectors ist dabei ein Array von Polygonen. vertices[] ist ein array aus den Eckpunkten des momentanen Polygons.
das momentane Polygon ist in der ArrayList otherSectors NICHT enthalten!

In dieser Methode wird doch geschaut: Gibt es einen sektor, in dem der momentane liegt? Sprich für jeden Eckpunkt vertices[x] wird überprüft, ob dieser Punkt in einem anderen Polygon enthalten ist? oder nicht??

Die ganze Zeit malt er mir nämlich Polygone in andere hinein, obwohl das doch damit abgedeckt sein müsste? Er returned aber nie true! Was isn da los, was macht diese contains-methode???

 

[Marco13]

Was du da vorhast, sollte nicht notwendig sein.

Die Frage wird vielleicht beantwortet, wenn du dir mal die Definition von "Insideness" ansiehst, auf die AUCH in der Polygon-Doku verwiesen wird:
http://java.sun.com/j2se/1.4.2/docs/api/java/awt/Shape.html
Wenn du testen willst, ob zwei Polygone in dieser Form aneinander grenzen, dann überprüfe notfalls die Abstände der Punkte zueinander:

for (i= 1 bis 6)
{
    for (j = 1 bis 6)
    {
        float ds = hexagonA.point(i).distanceSquared(hexagonB.point(j)));
        if (ds < 1) return joDieBerührenSich;
    }
    return nöDieBerührenSichNicht.
}

Aber nochmal: Das sollte nicht notwendig sein!

Im Moment habe ich das Gefühl, dass du dort Berechnungen auf eine Weise machen willst, wie man sie nicht machen sollte. Das, was du dort mit Polygonen auf den Bildschirm zeichnest, ist ja nur das BILD einer Situation in deinem Spiel. Dein komplettes Spiel sollte im Idealfall auch laufen können, OHNE dass irgendwas auf dem Bildshirm erscheint. Wenn du ein Polygon erstellst, um ein Feld zu malen - schön. Aber um zu prüfen, ob zwei Felder nebeneinander liegen, solltest du NICHT prüfen, ob die Polygone nebeneinander liegen, oder ob ein Pixel nun gerade rot oder grün eingefärbt ist, sondern du solltest z.B. in einem Array nachsehen, der alle "Feld"-Objekte enthält.

Brutal formuliert: Entwirf das Spiel, implementiere das Spielbrett und die Regeln und den Ablauf, bis das Spiel komplett fertig und spielbar ist. Und DANN überleg' dir, wie du das ganze hübsch zeichnen kannst.

 

[Guest]

hey,

deine testroutine funktioniert leider nicht immer, denn wenn ein polygon in einem anderen drin liegt, können die abstände durchaus größer sein. z.B. ein kreis mit radius 1 in einem mit radius 5.
da schneidet sich kein punkt, trotzdem liegt der eine im anderen.

deshalb verwende ich ja die polygon-klasse, weil ich dachte dass für sowas sie eben gedacht ist und methoden anbietet.
z.B. die contains().
aber laut definition von insideness sollte ja so ein szenario wie z.B. das der zwei kreise mit contains() ergeben, dass der eine eben im anderen liegt.
oder verstehe ich das noch immer falsch?

und wegen dem malen: ich versteh nich ganz, was du meinst? wenn ich sage "x liegt in polygon y" dann sage ich das ja nicht, weil das gemalte so aussieht, als ob x in y liegt. sondern x LIEGT in y, deshalb wird es so gemalt.
also klar kann ich mich nach dem gemalten richten. wenn ich es doch sehe, dann sehe ich ja ganz klar wo die koordinaten liegen.

naja okay aber die frage bleibt nach wie vor: wieso returned mir meine methode nicht true? wieso ist er der ansicht, dass der punkt gar nicht im polygon liegt?

das einzige was ich mir vorstellen kann is, dass ich die polygone falsch erstelle. ich arbeite ja erst nur mit nem array von 6 punkten und caste es dann zu polygon.

dafür geb ich ihm die 6 punkte. aber ich dachte die klasse weiss dann eben, was innerhalb des polygons liegt?
schon oder? weil wo ist da sonst der sinn?

so mach ichs:

    private void castToPoly() {

        int thisN = vertices.length;             // vertices = array der länge 6, enthält 6 Points
        int[] thisXpoints = new int[thisN];
        int[] thisYpoints = new int[thisN];
        for (int i = 0; i < thisN; i++) {
            thisXpoints[i] = vertices[i].x;
            thisYpoints[i] = vertices[i].y;
        }

        this.npoints = thisN;
        this.xpoints = thisXpoints;
        this.ypoints = thisYpoints;
    }

jetzt müsste doch ein contains(), angewandt auf ein so gecastetes Polygon, für jeden beliebigen Punkt selbstständig erkennen können, ob er innerhalb des Polygons liegt. oder?

das ist doch strange, dass er aber scheinbar der meinung ist, ein punkt liegt nicht in einem polygon, obwohl ich eindeutig sehe, dass er mitten drin liegt.
nochmal: das gezeichnete basiert doch auf der internen repräsentation, nicht andersrum, also gilt doch:

im bild liegt der punkt x innerhalb des polygons y
=> y.contains(x) müsste true sein.

oder nicht?

 

[Guest]

hier nochmal ein beispiel:



das rote polygon ist das neue, also auf dieses wird gerade die methode die man im bild sieht angewendet.

in der schleife müsste also erst für das rechts daneben und dann für das darüber überprüft werden, ob einer der eckpunkte des roten polygons drinliegen (->contains()).

aber er hat es erstellt, er hat also nicht true geliefert sondern war der meinung, keins der anderen zwei polygone enthält einen eckpunkt des roten.

warum? die grafik IST doch die repräsentierung der koordinaten, oder hab ich jetzt ne totale blockade?

diese situation hätte doch nie gemalt werden dürfen, das rote polygon hätte nie erstellt werden drüfen weil die methode hätte true liefern müssen. aber sie lieferte false ??

 

[Marco13]

Starten, sinnlos rumlicken, rote punkte sehen

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class Hexagon
{
    private int size;
    private Polygon polygon;
    Point points[] = new Point[6];
    public Hexagon other;

    public Hexagon(int x, int y, int size)
    {
        this.size = size;
        setPosition(x,y);
    }

    public void setPosition(int x, int y)
    {
        double h = Math.sin(Math.toRadians(30)) * size;
        double r = Math.cos(Math.toRadians(30)) * size;
        int xcoords[] = new int[6];
        int ycoords[] = new int[6];
        xcoords[0] = (int)(x);
        xcoords[1] = (int)(x + size);
        xcoords[2] = (int)(x + size + h);
        xcoords[3] = (int)(x + size);
        xcoords[4] = (int)(x);
        xcoords[5] = (int)(x - h);

        ycoords[0] = (int)(y);
        ycoords[1] = (int)(y);
        ycoords[2] = (int)(y + r);
        ycoords[3] = (int)(y + r + r);
        ycoords[4] = (int)(y + r + r);
        ycoords[5] = (int)(y + r);

        for (int i=0; i<6; i++)
        {
            points[i] = new Point(xcoords[i], ycoords[i]);
        }

        polygon = new Polygon(xcoords,ycoords, 6);
    }

    public void draw(Graphics g)
    {
        g.setColor(Color.BLACK);
        ((Graphics2D)g).draw(polygon);
        g.setColor(Color.RED);
        if (other != null)
        {
            for (int i=0; i<6; i++)
            {
                if (other.polygon.contains(points[i]))
                {
                    g.fillOval(points[i].x-2,points[i].y-2,5,5);
                }
            }
        }
    }

}


class HexagonTest extends JPanel
{
    Hexagon a = new Hexagon(100,100,100);
    Hexagon b = new Hexagon(100,200,100);

    public static void main(String args[])
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setSize(500,500);
        final HexagonTest hexagonTest = new HexagonTest();
        hexagonTest.addMouseListener(new MouseAdapter()
        {
            public void mouseClicked(MouseEvent e)
            {
                hexagonTest.a.setPosition(e.getX(), e.getY());
                hexagonTest.repaint();
            }
        });

        hexagonTest.a.other = hexagonTest.b;
        hexagonTest.b.other = hexagonTest.a;
        f.getContentPane().add(hexagonTest);
        f.setVisible(true);
    }

    public void paintComponent(Graphics g)
    {
        super.paintComponent(g);
        a.draw(g);
        b.draw(g);
    }


}

 

[Guest]

hey,

vielen Dank.

ich hab jetzt denk ich die Arbeitsweise von contains begriffen, deshalb hab ich mir für das Prüfen auf Überschneidung ne Methode gebastelt, bei der für eine Überschneidung gilt:

polygon.contains(p) && !partOfPath(p)

wobei die Methode partOfPath mit dem PathIertator die Grenze abläuft.
D.h. jetzt gibts nur noch ne Überschneidung wenn ein Punkt tatsächlich IN dem polygon liegt, und das funktioniert auch prima.

aaaber: jetzt hab ich grad mit vielen Tests etwas SEHR komisches rausgefunden, und mein motivation ist nun == 0,
weil ich gar nich mehr check was das soll.

mittels mouselistener hab ich nun herausgefunden:
er kriegt einen klick in einem polygon manchmal (manchmal heisst hier es hängt vom polygon ab, nicht von der zeit oder mehreren mausklicks) nur in einem bestimmten bereich des polygons mit.

sprich: die interne darstellung scheint von der bildlichen abzuweichung.

aber jetzt das, was mir nicht in den kopf geht: meine paint-methode macht nur ein g.drawPolygon().

d.h. ja wohl, dass die koordinaten und alles doch tatsächlich da sein müssten, wo ers malt. er malt ja mittels der koordinaten.

also wie kann sowas passieren, dass das polygon gezeichnet wird, er aber z.B. nur in der oberen linken ecke ein contains() als true wahrnimmt, in anderen bereichen des polygons aber nicht?

ich tick total aus, das kanns doch nicht sein, wo is da der fehler? ich meine es kann sein dass ich ein paar logische fehler hab, weils inzwischen recht kompliziert is alles, aber das lustige is ja eben dass er es zeichnet.

drawPolygon() geht, aber ein contains() auf dieses polygon denkt manchmal, dass der punkt gar nicht darin enthalten ist? obwohl es korrekt gezeichnet ist? das würde ja heissen, dass die methode contains() ganz andere eckpunkte des polygons hernimmt als drawPolygon?

wer blickt denn da noch durch?? schön langsam muss ich echt aufgeben

 

[Guest]

closed

thema hat sich erledigt.