How to find out if two PolyLines intersect

Question

I have a problem finding out if two PolyLines intersect.

Well the main objective is to compare last X and Y with the other PolyLine and find out if it's colliding aka intersecting with it.

There are gaps in the data due moving the X and Y, so most of the time I can't find the X and Y in the other PolyLine.

I think I should compare the visualtree or something and not the data itself, but I have no idea how to get do that.

<Canvas x:Name="LayoutRoot" Background="Black" Margin="2">
    <Polyline x:Name="player3line" Stroke="GreenYellow" StrokeThickness="4" Points="146,106 141,106 136,105 131,105 126,105 121,106 116,108 112,110 108,113 104,115 100,118 96,120 92,123 88,126 84,129 80,132 77,136 74,140 72,144 69,148 67,152 64,156 " />
    <Polyline x:Name="player4line" Stroke="Cyan" StrokeThickness="4" Points="85,113 89,116 93,119 97,121 102,123 107,124" />
</Canvas>

There must be an easy way to check if those two intersect?

Answer 1

I figured i should search all coordinates around my point, since the stroke thickness is 4.

So I figured I need to check from X-2 to X+2 and from Y-2 to Y+2.

So I did this and amazingly it works for now, I admit it's not perfect but it's simple and for now I don't see any CPU spikes with this method:

  private bool CheckCollision(Point centerPoint)
    {
        bool functionReturnValue = false;

        //wall collision
        if (centerPoint.X - 1 < 0
            || centerPoint.X + 1 > (int)LayoutRoot.ActualWidth
            || centerPoint.Y - 1 < 0
            || centerPoint.Y + 1 > (int)LayoutRoot.ActualHeight)
        {
            functionReturnValue = true;
        }

        //player collision
        if (!functionReturnValue)
        {
            foreach (var player in playerList) //all players are in this list
            {
                for (int i = Convert.ToInt32(centerPoint.X - 2); i < centerPoint.X + 2; i++)
                {
                    for (int j = Convert.ToInt32(centerPoint.Y - 2); j < centerPoint.Y + 2; j++)
                    {
                        var point = new Point() { X = i, Y = j };
                        if (player.CoordinatePoints.Contains(point))
                        {
                            functionReturnValue = true;
                            goto END;
                        }
                    }
                }
            }
        }
        goto END;

     END:
        return functionReturnValue;
    }

Answer 2

Any collision testing has to be done on the data as there is no magic hardware/software collision testing in Silverlight I am aware of.

In the case of 2 polylines you need to check each segment of the line against each segment of the other line (or simplified versions of one or both for starters).

You can first check for bounds-rectangle collision (min and max x,y positions of each polygon make a bounding rectangle) and if they overlap at all you then need to check each individual line segment for collision.

There is no shortcut I am aware of for this sort of collision testing. Just a few tricks to speed up the checking.

This link shows a high level example, but there are more game-oriented solutions around as well.