PureBoard
https://www.purebasic.fr/german/

Wann schneiden Objekte diagonale Linien?
https://www.purebasic.fr/german/viewtopic.php?f=5&t=31667		 Seite 1 von 1
Autor:  Syntacks_Error [ 23.09.2019 22:41 ]
Betreff des Beitrags:  Wann schneiden Objekte diagonale Linien?
Hallo,

ich habe wieder einmal ein Geometrieproblem.

Ein Spielfeld ist durch senkrechte und waagrechte Linien und diagonale Linien (nur in eine Richtung) in ein Raster aufgeteilt. Auf dem Spielfeld befinden sich diverse Objekte, Ort und Länge (Breite ist im Moment egal) und Orientierung sind bekannt. Die Orientierung kann beliebig sein.

Ich muss nun feststellen, ob diese Objekte die Gitterlinien schneiden. Bei den waagrechten und senkrechten Linien ist das kein Problem, aber wie mache ich das bei den Diagonalen?

Zur Veranschaulichung stark vergößert Folgendes, wobei die hier zufällig verteilten Objekte, die senkrechte oder waagerechte Linien schneiden, rot übermalt sind. Der Rasterabstand der Senkrechen/Waagerechten beträgt hier 64 Pixel:

Code:


; Hier werden die Objekte gezeichnet und es wird geprüft, ob sie senkrechte oder waagrechte Linien schneiden
 
Procedure makeobjects(canvGad,imageWidth,imageHeight)
 
 StartDrawing(CanvasOutput(canvGad))
 
 ; Die Objekte sind hier maßstabsgetreu 12.8 Pixel lang, wird natürlich beim Zeichnen gerundet
 For x = 1 To 200
  x1 = Random(imageWidth,12.8) ; x-Position des Anfangs; die 12.8 stellen den Abstand vom Rand sicher
  y1 = Random(imageHeight,12.8); y-Position des Anfangs
  degree.f = Random(360,0)
  x2 = x1 + Sin(Radian(degree)) * 12.8 ; x-Position des Endes ; na ja, kann über den Rand hinausgehen, egal
  y2 = y1 + Cos(Radian(degree)) * 12.8 ; y-Position des Endes
  LineXY(x1,y1,x2,y2,RGB(0,0,250))     ; Alle Objekte erstmal blau
 
  ;Die Objekte schneiden waagrechte oder senkrechte Linien, wenn sich
  ;Anfangs- und Endpunkte der Objekte in verschiedenen Gitterfeldern befinden.
  ;Dazu einfach die AnfangXY-Position und die EndeXY-Position durch den Linienabstand von 64 Punkten teilen.
  ;Wenn das Ergebnis für StartXY-Position und EndXY-Position unterschiedlich ist,
  ;liegen Anfang- und Endpositionen in unterschiedlichen Feldern
 
  If x1/64 <> x2/64 Or y1/64 <> y2/64  ; Objekte, die waagrechte oder senkrechte Linien schneiden,
   LineXY(x1,y1,x2,y2,RGB(255,0,0))    ; werden rot übermalt
  EndIf
 
;  Wie funktioniert der Test auf das Schneiden bei den diagonalen Linien?

 Next
StopDrawing()
 EndProcedure
 

 
 Procedure makeLines(canvGad,imageWidth,imageHeight)
 StartDrawing(CanvasOutput(canvgad)) 
 
 ;Grid senkrecht und waagrecht
 For x = 0 To imagewidth Step 64
   For y = 0 To imageheight Step 64
    LineXY(x,y + 64 ,imagewidth,y + 64,RGB(150,150,150)) ; Waagrechte Linien
    LineXY(x + 64, 0, x + 64, imageheight,RGB(0,0,0))    ;Senkrechte Linien
   Next 
  Next
 
 ; Diagonalen
  For x = 0 To imagewidth - 64 Step 64
   For y = 0 To imageWidth Step 64;
    LineXY(x,y,x + 64,y - 64,RGB(0,0,0))
   Next
 Next
 
 
 ; Folgendes ist unwichtig, diente mir nur der Visualisierung
 ; Die roten Rasterlinien ergeben schräg liegende, versetzte ungleichseitige Sechecke.
 ; Sieht man aber nur, wenn man es weiß
 
  ;Die Struktur bezieht sich nur auf den unwichten Teil und ist unwichtig ;-)
 Structure lines
  x1.i
  y1.i
  deg1.f
  x2.i
  y2.i
  deg2.f
  x3.i
  y3.i
  deg3.f
  x4.i
  y4.i
  deg4.f
  x5.i
  y5.i
  deg5.f
  x6.i
  y6.i
  deg6.f
  degree.f
  made.b
 EndStructure
 NewList lines.lines()
 
 a = 0
 b = imageheight
 For b = imageHeight + 64 To 0 Step - 192; von oben nach unten abnehmend, da hier y = 0 links unten
  For a =- 64  To imagewidth Step 192
 ; waagrechte Linie unten
  x1 = a
  y1 = b
  x2 = a + 64
  y2 = b
 ; senkrechte Linie links
  x3 = x1
  y3 = y1 - 64
 ;schräge Linie links
  x4 = x3 + 64
  y4 = y3 - 64
 ;waagrechte Linie oben
  x5 = x4 + 64
  y5 = y4 
 ;schräge Linie rechts
  x6 = x2 + 64
  y6 = y2 - 64
 ;waagrechte linie oben/Wird bei Versatz erfasst
 
 ;1.reguläre 6ecke
   AddElement(lines())
   With lines()
    \x1 = x1
    \y1 = y1
    \deg1.f = 90
    \x2 = x2
    \y2 = y2
    \deg2.f = 90
    \x3 = x3
    \y3 = y3
    \deg3.f = 360
    \x4 = x4
    \y4 = y4
    \deg4.f = 45
    \x5 = x5
    \y5 = y5
    \deg5.f = 90
    \x6 = x6
    \y6 = y6
    \deg6.f = 225
   EndWith
  Next
 Next

;2.versetzte 6ecke
 For b = imageHeight   To 0  Step - 192 ; - 64
  For a = 64 To imagewidth - 64 Step 192 ; 0
  ;waagrechte Linie unten
   x1 = a
   y1 = b
   x2 = a + 64
   y2 = b
  ;senkrechte Linie links
   x3 = x1
   y3 = y1 - 64
  ;schräge Linie links
   x4 = x3 + 64
   y4 = y3 - 64
  ;waagrechte Linie oben
   x5 = x4 + 64
   y5 = y4 
  ;schräge Linie rechts
   x6 = x2 + 64
   y6 = y2 - 64
  ;waagrechte linie oben
 
   AddElement(lines())
   With lines()
    \x1 = x1
    \y1 = y1
    \x2 = x2
    \y2 = y2
    \x3 = x3
    \y3 = y3
    \x4 = x4
    \y4 = y4
    \x5 = x5
    \y5 = y5
    \x6 = x6
    \y6 = y6
   EndWith
  Next
 Next
 
 ForEach lines()
  LineXY(lines()\x1,lines()\y1,lines()\x2,lines()\y2,RGB(200,0,0))
  LineXY(lines()\x1,lines()\y1,lines()\x3,lines()\y3,RGB(200,0,0))
  LineXY(lines()\x3,lines()\y3,lines()\x4,lines()\y4,RGB(200,0,0))
  LineXY(lines()\x4,lines()\y4,lines()\x5,lines()\y5,RGB(200,0,0))
  LineXY(lines()\x2,lines()\y2,lines()\x6,lines()\y6,RGB(200,0,0))
  LineXY(lines()\x5,lines()\y5,lines()\x6,lines()\y6,RGB(200,0,0))
 Next
 ; unwichtig Ende
 
 StopDrawing() 
EndProcedure

Procedure closeprog(window)
If IsWindow(window)
  CloseWindow(window)
 EndIf
 End
 EndProcedure
 


windowWidth = 1024
windowHeight = 1024
window = OpenWindow(#PB_Any,#PB_Ignore,#PB_Ignore,windowWidth,windowHeight,"Demo",#PB_Window_SystemMenu )

imageWidth = 1024
imageHeight = 1024
canvGad = CanvasGadget(#PB_Any,0,0,imageWidth,imageHeight,#PB_Canvas_Keyboard)
makeLines(canvGad,imageWidth,imageHeight)
makeobjects(canvGad,imageWidth,imageHeight)
 
Repeat
 event = WindowEvent()
 Select event
  Case #PB_Event_CloseWindow 
   close = 1
   While WindowEvent() : Wend
 EndSelect 
Until close = 1



Meine Überlegungen bisher:
Ich kippe das Koordinatensystem so, dass die Diagonalen senkrecht oder waagerecht stehen. Dann muss ich aber auch alle Objekte und einiges mehr umrechnen, sehr unschön.

Oder: Wenn die Diagonalen geschnitten werden, bilden die Anfangskoordinaten (oder Endkoordinaten) der Elemente mit den Diagonalen ein Dreieck. Ich berechne die senkrechte Distanz dieser Koordinaten auf die Diagonale und aus dem Orientierungswinkel der Objekte dann, ob der Abstand so klein ist, dass das Objekt die Diagonale schneiden kann. Nachteil ist hier, dass ich jedes Objekt gegen jede Linie laufen lassen muss, und das mit Geometriefunktionen. Dauert sicherlich ewig.

Gibt es für die Diagonalen eine vergleichbar schlanke Lösung wie für die Senkrechten/Waagrechten?

Grüße,
S. Error
Autor:  DrShrek [ 24.09.2019 09:42 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Versuche es doch mal mit dem Chipmunk2PB wrapper:
viewtopic.php?f=11&t=23073

Das geht dann sogar für alle möglichen gekippten oder sonst wie gezeichneten Objeke (z.B. Kreise, Linien, Ovale, Polygone, Dreiecke, usw.)
Autor:  NicTheQuick [ 24.09.2019 11:37 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Am besten nutzt du einfach einen Algorithmus um Schnittpunkte von Geraden zu finden.

Allerdings musst du ihn noch etwas anpassen, damit Start- und Endpunkte der Linien auch berücksichtigt werden. Außerdem möchtest du vielleicht andere Strukturen nutzen.
Code:
; Source: https://rosettacode.org/wiki/Find_the_intersection_of_two_lines#C.2B.2B
Structure Pd2D
   x.d
   y.d
EndStructure
Structure Ld2D
   a.Pd2D
   b.Pd2D
EndStructure
Procedure.i lineIntersect(*line1.Ld2D, *line2.Ld2D, *intersect.Pd2D)
   Protected a1.d = *line1\b\y - *line1\a\y
   Protected b1.d = *line1\a\x - *line1\b\x
   Protected c1.d = a1 * *line1\a\x + b1 * *line1\a\y
   
   Protected a2.d = *line2\b\y - *line2\a\y
   Protected b2.d = *line2\a\x - *line2\b\x
   Protected c2.d = a1 * *line2\a\x + b2 * *line2\a\y
   
   Protected delta.d = a1 * b2 - a2 * b1
   If Abs(delta) < 0.00001
      ; Parallel
      ProcedureReturn #False
   
   ElseIf *intersect :
      *intersect\x = (b2 * c1 - b1 * c2) / delta
      *intersect\y = (a1 * c2 - a2 * c1) / delta
   EndIf
   
   ProcedureReturn #True
EndProcedure

Define.Ld2D line1, line2

line1\a\x = 4
line1\a\y = 0
line1\b\x = 6
line1\b\y = 10
line2\a\x = 0
line2\a\y = 3
line2\b\x = 10
line2\b\y = 7

Define intersect.Pd2D

If lineIntersect(line1, line2, intersect)
   Debug "Schnittpunkt: " + intersect\x + ", " + intersect\y
EndIf
Autor:  Syntacks_Error [ 24.09.2019 21:32 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Vielen Dank! Dieses Chipmunk scheint ja ein tolles Teil zu sein, aber vielleicht mehr für die Profis. Bei mir geht es nicht einmal um ein eigenes Spiel, sondern nur um ein Hilfsprogramm für ein anderes. Da ist diese Intersect-Geschichte genau richtig. Den Code habe ich alledings nicht verstanden und musste das erst einmal behelfsmäßig für mich umschreiben ;-).

Beim Testen habe ich festgestellte, dass die Prozedur, was ja auch in ihr angelegt ist, für nicht-parallele Linien immer einen Schnittpunkt liefert. Sie berücksichtigt also die Länge der Linien nicht. Ich gedenke das dadurch zu lösen, dass ich um meine Objekte noch eine Box lege und prüfe, ob der Schnittpunkt innerhalb der Box liegt, oder gibt es da etwas Besseres? Dass ich jedes Objekt (das können so bis zu etwa 80.000 sein) gegen jede diagonale Linie laufen lassen muss, ist wohl nicht zu umgehen, das dauert dann halt.

Außerdem gibt es ein Problem: Die Prozedur liefert einen falschen Wert für den y-Schnittpunkt? Jedenfalls gibt ein Mausclick links hier einen anderen (offenbar auch richtigen) Wert als die Prozedur?

S. Error

Window mit Linien und Mausclick links ergänzt:
Code:

; Source: https://rosettacode.org/wiki/Find_the_intersection_of_two_lines#C.2B.2B

; Window mit Linien und Mausclick links zur Positionsabfrage ergänzt


Structure Pd2D
   x.d
   y.d
EndStructure

Structure Ld2D
   a.Pd2D
   b.Pd2D
 EndStructure

 
Procedure.i lineIntersect(*line1.Ld2D, *line2.Ld2D, *intersect.Pd2D,canvgad)
   Protected a1.d = *line1\b\y - *line1\a\y
   Protected b1.d = *line1\a\x - *line1\b\x
   Protected c1.d = a1 * *line1\a\x + b1 * *line1\a\y
   
   Protected a2.d = *line2\b\y - *line2\a\y
   Protected b2.d = *line2\a\x - *line2\b\x
   Protected c2.d = a1 * *line2\a\x + b2 * *line2\a\y
         
   Protected delta.d = a1 * b2 - a2 * b1
   If Abs(delta) < 0.00001
      ; Parallel
     ProcedureReturn #False
   
   ElseIf *intersect :
      *intersect\x = (b2 * c1 - b1 * c2) / delta
      *intersect\y = (a1 * c2 - a2 * c1) / delta
   EndIf
   
   StartDrawing(CanvasOutput(canvGad))
   
   LineXY(*line1\a\x,*line1\a\y,*line1\b\x,*line1\b\y,RGB(255,0,0))
   LineXY(*line2\a\x,*line2\a\y,*line2\b\x,*line2\b\y,RGB(0,0,255))
   
   StopDrawing()
   
   ProcedureReturn #True
EndProcedure

Define.Ld2D line1, line2

; Senkrechte Linie
line1\a\x = 150
line1\a\y = 10
line1\b\x = 150
line1\b\y = 500

;Schräge Linie
line2\a\x = 20
line2\a\y = 40
line2\b\x = 210
line2\b\y = 250

; Originalwerte
; line1\a\x = 4
; line1\a\y = 0
; line1\b\x = 6
; line1\b\y = 10
;
; line2\a\x = 0
; line2\a\y = 3
; line2\b\x = 10
; line2\b\y = 7

Define intersect.Pd2D

 window = OpenWindow(#PB_Any, 100,100,800,800, "Test",#PB_Window_SystemMenu| #PB_Window_BorderLess)
 canvGad = CanvasGadget(#PB_Any,0,0,800,800)
 InitMouse()
 
 If lineIntersect(line1, line2, intersect,canvgad)
   Debug "Schnittpunkt: " + intersect\x + " / " + intersect\y
 EndIf
 

 Repeat
   event = WaitWindowEvent()
   Select event
     Case #PB_Event_CloseWindow
       close = 1
     Case #PB_Event_Gadget   
       Select EventGadget()
         Case canvGad
          Select EventType()
           Case #PB_EventType_LeftClick
            Debug Str(GetGadgetAttribute(canvGad, #PB_Canvas_MouseX)) + "/" + Str(GetGadgetAttribute(canvGad, #PB_Canvas_MouseY))
       EndSelect
     EndSelect 
   EndSelect
  Until close = 1
Autor:  Nino [ 25.09.2019 11:47 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
NicTheQuick hat geschrieben:
Am besten nutzt du einfach einen Algorithmus um Schnittpunkte von Geraden zu finden.

Allerdings musst du ihn noch etwas anpassen, damit Start- und Endpunkte der Linien auch berücksichtigt werden.

Das Rad braucht nicht neu erfunden zu werden. :-)
-> Intersection of two line segments
Autor:  NicTheQuick [ 25.09.2019 12:02 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
@Nino :allright:
Umso besser. Ich hab es ja auch nur von Rosettacode geklaut, weil ich gerade Lust dazu hatte. :D
Autor:  Syntacks_Error [ 25.09.2019 19:40 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Hallo,

habe nun doch noch eine schlankere Methode gefunden:

(Horizontaler Abstand der Diagonalen = 64)

If (x1 + y1)/64 <> (x2 + y2)/64
; Objekt x1,y1 - x2,y2 schneidet (oder berührt) Diagonale
LineXY(x1,y1,x2,y2,RGB(255,0,0))
EndIf

Hier muss jedes Objekt nur einmal geprüft werden und die Länge der Objekte ist berücksichtigt. Funktioniert allerdings nur bei Diagonalen mit 45 Grad, was ich habe. Das Prinzip müsste aber auch für 3, 5 und 7 * 45 Grad gehen. Den Schnittpunkt liefert das nicht, ich nehme aber an, dass auch der nach diesem Prinzip zu ermitteln ist. Gleichwohl würde ich gerne wissen, wie die intersect Prozedure mit korrektem y-Ausgabewert aussieht.

S. Error
Autor:  NicTheQuick [ 26.09.2019 11:02 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Syntacks_Error hat geschrieben:
Gleichwohl würde ich gerne wissen, wie die intersect Prozedure mit korrektem y-Ausgabewert aussieht.

Da ist ein Vertipper in der Rechnung für c2. So ist es korrekt:
Code:
Protected c2.d = a2 * *line2\a\x + b2 * *line2\a\y
Autor:  Syntacks_Error [ 26.09.2019 19:45 ]
Betreff des Beitrags:  Re: Wann schneiden Objekte diagonale Linien?
Vielen Dank, jetzt geht's!

S. Error
Seite 1 von 1 Alle Zeiten sind UTC + 1 Stunde [ Sommerzeit ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/