Fläche mit Kreisen füllen

  • Allgemein

Es gibt 6 Antworten in diesem Thema. Der letzte Beitrag () ist von bsHobbit.

    Fläche mit Kreisen füllen

    Guten Morgen,

    ich habe folgendes Problem:

    Ich habe eine Fläche gekennzeichnet durch n Punkte, die mit einander verbunden sind.
    Von dieser Fläche kenne ich nur alle Punkte P.

    (Die Fläche ist beliebig, ist nur ein Beispiel in der Grafik)

    Nun habe ich einen Kreis, von dem ich den Radius kenne, nun soll der Kreis so oft in die Fläche, das er die Fläche ausfüllt.

    Das ganze mal Grafisch dargestellt:



    Und das Ergebnis soll das hier ergeben:
    (diese Grafik entspricht nicht dem tatsächlichen ergebnis)



    Ich selber hab noch keinen Ansatz gefunden, wie ich dieses Problem lösen kann. Vielleicht kann mir hier ja jemand helfen.

    Theoretisch würd es mir schon helfen, wenn mir jemand sagen könnte, wie ich herausfinde, ob ein Punkt, innerhalb der Fläche ist.


    Gruß Hobbit

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „bsHobbit“ ()

    Ich kann dir sagen, wie du herausfindest, ob ein Punkt innerhalb eines Dreiecks liegt. Gegeben sind: A,B,C (alles Punkte vom Dreieck) sowie Z, der irgendwo liegen kann.

    Du ziehst von Z zu A,B und C jeweils 1Linie.

    Jetzt hast du die Winkel:

    AZB, BZC und CZA. Merke: Z ist immer in der Mitte!

    Jetzt zählst du alle 3 Winkel zusammen. Entspricht das resultat ungefähr (+- 0.5 Rehcenfehler) 360 (Vollkreis), so liegt der Punkt innerhalb des Dreiecks.

    Muahaha, ich habs grad nochmal durchgelesen und nix mehr kapiert:) Bei Fragen einfach nachfragen. Falls es dir überhaupt was bringt.

    Du könntest z.B. die Fläche in Dreiecke aufteilen und dann für jedes prüfen, ob der Punkt darinliegt. Sollte das bei einem der Fall sein, liegt der Punkt innerhlab der Fläche. Die se Methode ist aber sehr, sehr, sehr langsam.

    Joa, wenn ich mein Polygon noch in einzelne Dreicke aufteil, dann kann ich ja ewig rechnen xD

    Ich hab bereits eine Annährungslösung gefunden xD

    Ich bekomms nur iwi nich genauer hin, wenn sich einer dran setzen will...

    is mit vb2005 geschrieben, einfach alles kopieren, starten glücklich sein^^

    VB.NET-Quellcode

    1. Public Class Form1
    3. private P(100) As Point
    4. Private CountEdge As Integer = 0
    5. Private CurrPoint As Point
    6. Private Px As Point
    7. Private guiCrossList As New List(Of Point)
    8. Private MinL As Integer, MaxR As Integer
    9. Private MinT As Integer, MaxB As Integer
    10. Private SpotR As Integer = 10
    13. Private Sub createCircle(ByVal middle As Point, ByVal angle As Double, ByVal radius As Integer, ByVal spotRadius As Integer, ByVal WriteToCommandList As Boolean)
    15. Dim tmpPoint As Point
    16. Dim AddToAngle As Double
    17. Dim Perimeter As Double = 2 * Math.PI * radius
    18. Dim count As Double
    21. count = Math.Round(Perimeter / (2 * spotRadius))
    22. AddToAngle = 360 / count
    24. If radius <= spotRadius Then
    25. tmpPoint.X = middle.X
    26. tmpPoint.Y = middle.Y
    27. Else
    28. tmpPoint.X = (middle.X + Math.Cos(angle * Math.PI / 180) * radius)
    29. tmpPoint.Y = (middle.Y + Math.Sin(angle * Math.PI / 180) * radius)
    30. End If
    33. If angle < 360 Then
    34. If isPointInPolygon(tmpPoint) Then
    35. guiCrossList.Add(tmpPoint)
    36. End If
    37. If radius > spotRadius Then
    38. createCircle(middle, angle + AddToAngle, radius, spotRadius, WriteToCommandList)
    39. End If
    40. Else
    41. If radius > spotRadius Then
    42. createCircle(middle, 0, radius - spotRadius, spotRadius, WriteToCommandList)
    43. End If
    44. End If
    46. End Sub
    48. Private Function isPointInPolygon(ByVal point As Point) As Boolean
    49. Dim RCross As Integer = 0
    50. Dim LCross As Integer = 0
    52. For i As Integer = 0 To CountEdge - 1
    53. Dim EdgeStart As Point = P(i)
    54. Dim EdgeEnd As Point = P(i + 1)
    55. If i = CountEdge - 1 Then
    56. EdgeEnd = P(0)
    57. End If
    58. If (point = EdgeStart) Then
    59. Return True
    60. End If
    62. If (EdgeStart.Y > point.Y) <> (EdgeEnd.Y > point.Y) Then
    63. Dim Term1 As Integer = (EdgeStart.X - point.X) * (EdgeEnd.Y - point.Y) - (EdgeEnd.X - point.X) * (EdgeStart.Y - point.Y)
    64. Dim Term2 As Integer = (EdgeEnd.Y - point.Y) - (EdgeStart.Y - EdgeEnd.Y)
    65. If ((Term1 > 0) = (Term2 >= 0)) Then
    66. RCross += 1
    67. End If
    68. End If
    70. If (EdgeStart.Y < point.Y) <> (EdgeEnd.Y < point.Y) Then
    71. Dim Term1 As Integer = (EdgeStart.X - point.X) * (EdgeEnd.Y - point.Y) - (EdgeEnd.X - point.X) * (EdgeStart.Y - point.Y)
    72. Dim Term2 As Integer = (EdgeEnd.Y - point.Y) - (EdgeStart.Y - EdgeEnd.Y)
    73. If ((Term1 < 0) = (Term2 <= 0)) Then
    74. LCross += 1
    75. End If
    76. End If
    77. Next i
    79. If ((RCross Mod 2) <> (LCross Mod 2)) Then
    80. Return True
    81. End If
    83. Return (RCross Mod 2) = 1
    84. End Function

    VB.NET-Quellcode

    1. Private Function isIn() As Boolean
    2. Dim P1 As Point = Px
    3. Dim count As Integer = 0
    5. If isPointInPolygon(P1) Then
    6. tb.Text = "Drin"
    7. Else
    8. tb.Text = ""
    9. End If
    10. End Function
    12. Private Sub pp_MouseDown(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles pp.MouseDown
    13. If PaintPoly.Checked Then
    14. If CountEdge < 100 Then
    15. P(CountEdge).X = e.X
    16. P(CountEdge).Y = e.Y
    18. CountEdge += 1
    19. MinL = IIf(e.X < MinL, e.X, MinL)
    20. MaxR = IIf(e.X > MaxR, e.X, MaxR)
    21. MinT = IIf(e.Y < MinT, e.Y, MinT)
    22. MaxB = IIf(e.Y > MaxB, e.Y, MaxB)
    23. End If
    24. Else
    25. Px.X = e.X
    26. Px.Y = e.Y
    27. Dim Middle As New Point(pp.Width / 2, pp.Height / 2)
    28. Dim X1 As Integer = MaxR - MinL
    29. Dim x2 As Integer = MaxB - MinT
    30. Dim r As Integer = IIf(X1 > x2, X1 / 2, x2 / 2)
    31. createCircle(Middle, 0, r, SpotR, False)
    32. End If
    33. pp.Refresh()
    34. End Sub
    36. Private Sub pp_MouseMove(ByVal sender As System.Object, ByVal e As System.Windows.Forms.MouseEventArgs) Handles pp.MouseMove
    37. If PaintPoly.Checked Then
    38. CurrPoint.X = e.X
    39. CurrPoint.Y = e.Y
    40. pp.Refresh()
    41. End If
    42. End Sub
    44. Private Sub pp_Paint(ByVal sender As System.Object, ByVal e As System.Windows.Forms.PaintEventArgs) Handles pp.Paint
    46. If CountEdge > 0 Then
    47. If PaintPoly.Checked Then
    48. e.Graphics.DrawLine(Pens.Red, P(CountEdge - 1), CurrPoint)
    49. e.Graphics.DrawLine(Pens.Red, CurrPoint, P(0))
    50. Else
    51. e.Graphics.DrawLine(Pens.White, P(CountEdge - 1), CurrPoint)
    52. e.Graphics.DrawLine(Pens.White, CurrPoint, P(0))
    53. End If
    54. End If
    56. For i As Integer = 0 To CountEdge - 2
    57. e.Graphics.DrawLine(Pens.Black, P(i), P(i + 1))
    58. Next i
    59. If CountEdge > 2 Then
    60. e.Graphics.DrawLine(Pens.Black, P(0), P(CountEdge - 1))
    61. End If
    63. 'e.Graphics.DrawLine(Pens.Blue, Px.X - 4, Px.Y, Px.X + 4, Px.Y)
    64. 'e.Graphics.DrawLine(Pens.Blue, Px.X, Px.Y - 4, Px.X, Px.Y + 4)
    66. For i As Integer = 0 To guiCrossList.Count - 1
    67. 'e.Graphics.DrawLine(Pens.Red, guiCrossList.Item(i).X - 4, guiCrossList.Item(i).Y, guiCrossList.Item(i).X + 4, guiCrossList.Item(i).Y)
    68. 'e.Graphics.DrawLine(Pens.Red, guiCrossList.Item(i).X, guiCrossList.Item(i).Y - 4, guiCrossList.Item(i).X, guiCrossList.Item(i).Y + 4)
    69. e.Graphics.DrawEllipse(Pens.Green, guiCrossList.Item(i).X - SpotR, guiCrossList.Item(i).Y - SpotR, SpotR * 2, SpotR * 2)
    70. 'e.Graphics.fillEllipse(Brushes.Green, guiCrossList.Item(i).X - SpotR, guiCrossList.Item(i).Y - SpotR, SpotR * 2, SpotR * 2)
    71. Next
    73. End Sub
    75. Private Sub PaintPoly_CheckedChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles PaintPoly.CheckedChanged
    76. pp.Refresh()
    77. End Sub
    79. Private Sub Delete_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Delete.Click
    80. CountEdge = 0
    81. MinL = 0
    82. MinT = 0
    83. MaxR = 0
    84. MaxB = 0
    85. guiCrossList.Clear()
    86. pp.Refresh()
    87. End Sub
    88. End Class


    Edit by Agent: VB-Tag gesplittet

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Agent“ ()

    Den Polygon in Dreiecke aufzuteilen ist definitiv die einzige sinnvolle, allgemeine Lösung! Wenn du anfangst zu schauen, ob der Punkt Rechts von der einen Linie, Links von ner anderen etc. (was allgemein nur sehr schwer zu implementieren ist), kommst du auf deutlich mehr Rechenvorgänge ;)

    Das Problem hierbei ist nur, dass das Dreieck gültig sein muss (also das das Dreieck teil der Gesamtfläche ist und nicht außerhalb liegt. Ich denke, wenn du per Hand ein paar schräge Polygone aufzeichnest, kommst du da auch auf eine Lösung :)

    Hatte den Ansatz mit den Dreiecken versucht, hab mein Polygon in zig tausend dreicecke zerhackt, aber geholfen hats mir auch nicht... xD, denn dreicke helfen bei dem Problem mal so garnich... aber das Programm läuft jetzt mit einer sehr guten annäherung *freu* hat sich also alles erledigt =)

    Die Fläche in zgitausend Dreiecke zu unterteilen ist ja auch völliger overkill. Ich nehme an, dass war übertrieben? Du musst nur (AnzahlDerPunkte - 2) Dreiecke machen. Es bringt ja nichts, ein Dreieck immer weiter zu unterteilen;)
    "Theoretisch würd es mir schon helfen, wenn mir jemand sagen könnte, wie ich herausfinde, ob ein Punkt, innerhalb der Fläche ist." Dabei helfen dir aber die Dreiecke:)

    Nein, ich hab schon einen normalen polygon triangulations algorithmus angewndet, für meine Dreiecke, aber das hat mir nicht weitergeholfen, bei dem Problem, die fläche so weit wie möglich mit kreisen zu füllen, ohne den rand zu überschneiden...

Facebook
Telefonspende