Get vertex pair from fixture.

[duplex199126]

Hi everyone.
First of all - sorry for my English.
My problem:
What is the best way to get vertex pair that contains point. I have square fixture and i create RayCast that collide with it.
So i get point of collision this raycast and my fixture. But i need get the line which raycast collide.

How i can get point 1 and 2.
Now i do that, I create Linear equation https://en.wikipedia.org/wiki/Linear_equation for each vertex pair, than i try search where it is more or less satisfies the conditions - i dont like that. maybe exist more good variant or at least know more powerful algorithm to search is point on line or not, because that i use - It has a large error. Help me find it pls.

private Vector2 test(PolygonShape ps, Vector2 point, Vector2 normal) {

    float[] vertexColl = new float[ps.getVertexCount()];

    for(int i = 0; i < ps.getVertexCount()-1; i++){
        ps.getVertex(i, v1);
        ps.getVertex(i + 1, v2);
        vertexColl[i] = isPointOnLine(v1, v2, point);
    }

    ps.getVertex(0, v1);
    ps.getVertex(ps.getVertexCount() - 1, v2);
    vertexColl[vertexColl.length-1] = isPointOnLine(v1, v2, point);

    int minIndex = min(vertexColl);

    ps.getVertex(minIndex, v1);
    ps.getVertex(((minIndex + 1) < vertexColl.length) ? minIndex + 1 : 0, v2);

    return null;
}
private float isPointOnLine(Vector2 startLine, Vector2 endLine, Vector2 point){
    return Math.abs((point.x - startLine.x) * (endLine.y - startLine.y) - (point.y - startLine.y) * (endLine.x - startLine.x));
}

public int min(float[] array) {
    int minIndex = 0;
    for (int i = 1; i < array.length; i++) {
        if (array[i] < array[minIndex]) minIndex = i;
    }
    return minIndex;
}

[KaiHH]

Have a look at: https://github.com/JOML-CI/JOML/blob/master/src/org/joml/Intersectionf.java#L2998
EDIT:
This is of course only for the special case of having an axis-aligned rectangle.

[duplex199126]

@KaiHH

Have a look at: https://github.com/JOML-CI/JOML/blob/master/src/org/joml/Intersectionf.java#L2933

Yes, i saw it. It contains method:

    public static float distancePointLine(float pointX, float pointY, float x0, float y0, float x1, float y1) {
        float dx = x1 - x0;
        float dy = y1 - y0;
        float denom = (float) Math.sqrt(dx * dx + dy * dy);
        return (dx * (y0 - pointY) - (x0 - pointX) * dy) / denom;
    }

if distancePointLine return zero or almost zero, so that mean that the point on this line but:
-but using own method - I’m doing less computing.
-and most importantly - I still have to go through all vertex=(((

[KaiHH]

I did not mean that method, but the one that the original link pointed at. (updated)
Also added Intersectionf.intersectRayLineSegment()
You can test all line segments between pairwise vertices with it.

In essence: You don’t need a method to test whether a point lies on a line or line segment.
What you have is a ray. And when you want to know whether a ray intersects a line segment (or many line segments) then just use a “ray/line-segment” intersection test method, like the mentioned one.

EDIT:
In order to not having to test all line segments against the ray, you can use a spatial acceleration structure, such as a kd-tree (in this case k = 2) or just a quad tree. You could then test the ray against the axis-aligned rectangles of the quad tree nodes and test only the line segments inside that a particular quadtree node.
If such a test did not found any line segments and you need to follow the ray to the next quadtree node, you can accelerate that even further by having “ropes” or “links” between adjacent nodes of a quadtree to determine which leaf node to check next as you follow your ray along the scene.
But this will only likely make things faster in case your polygons have a moderate to large number of vertices, say more than 100.

[KaiHH]

Just so that you know what I mean, the following is a complete working but unaccelerated method to find the nearest intersection of a ray with a polygon, given as a sequence of (x, y) coordinate pairs in a float array, by testing the ray against all line segments of pairwise vertices.
The method returns the index of the first vertex of the nearest polygon edge the ray intersected with, if any, or -1 if none.
The second index would always be the first index + 1 (modulus the vertex count).
So if your polygon were a rectangle and the ray intersected the “last edge” of the polygon, the method would return 3, and your second vertex would be 0 (= (3+1) % 4).
Also it optionally writes the point of intersection into the supplied vector ‘p’.

public static int intersectPolygonRay(float[] verticesXY, float originX, float originY, float dirX, float dirY, Vector2f p) {
    float nearestT = Float.MAX_VALUE;
    int count = verticesXY.length >> 1;
    int j = count - 1;
    int edgeIndex = -1;
    for (int i = 0; i < count; i++) {
        float aX = verticesXY[j<<1], aY = verticesXY[(j<<1) + 1];
        float bX = verticesXY[i<<1], bY = verticesXY[(i<<1) + 1];
        float v1X = originX - aX, v1Y = originY - aY;
        float v2X = bX - aX, v2Y = bY - aY;
        float invV23 = 1.0f / (v2Y * dirX - v2X * dirY);
        float t = (v2X * v1Y - v2Y * v1X) * invV23;
        float t2 = (v1Y * dirX - v1X * dirY) * invV23;
        if (t >= 0.0f && t2 >= 0.0f && t2 <= 1.0f && t < nearestT) {
            edgeIndex = j;
            nearestT = t;
            p.x = originX + t * dirX;
            p.y = originY + t * dirY;
        }
        j = i;
    }
    return edgeIndex;
}

[duplex199126]

Listen! I want to kiss you! Thank you. Thank you. Thank you! Its work!!!

Thank you very much=)