Site-point collisions

[kewp]

Not sure where to put these comments / requests for info ...

(Thanks for creating this library, btw ! Has saved me a lot of time and brain power)

Is there an easy way to determine which site within the rectangle belongs to an x,y co-ordinate ? All I can think to do is loop through each one and do a polygonal collision check using each edge but I figured Voronoi is sort-of designed to know which points belong inside (that's basically the definition of a Voronoi diagram).

[kewp]

I suppose one way is just to loop through each point (site point) and check the distance and then the minimum one is the site the point belongs in

[mathiaswking]

"Not sure where to put these comments / requests for info" Me neither, but this is fine I think :)

So, for a random point(x,y) you want to find what cell/site it belongs to? I'm guessing the simplest way would be to go through each cell, and check if the point is outside or not: for each site: for each edge: normal = site.pos - edge.pos[0] // pointing "inwards" v = testpos - edge.pos[0] if dot(normal, v) < 0: // The normals are opposite each other break // it's outside of this cell

[kewp]

I'm not sure I understand why a negative dot product means it is outside ? I assume if you get to the end of the inner loop, you must be inside ?

[mathiaswking]

Sorry for the lack of indentation, github took all spaces there :/

Oops, a bit sloppy there by me. The normal of course should to be orthogonal to the edge. diff = edge.pos[1] - edge.pos[0] normal = point(-diff.y, diff.x) // pointing inwards

It's a check to see if a point is in front or behind a plane. In this case the plane is in 2D (an edge), and the front face of the plane is facing the site. If the dot product between two vectors is negative, it means they point in opposite directions in relation to the plane.

[kewp]

Ok, I think I understand. So the only way a point can be inside the plane is if the vector to it (from a point in the plane, e.g. edge.pos[1]) has a positive dot product with the plane normal ...

Makes sense. Thanks for the help !

[kewp]

I'm getting strange anomolies near the edges - maybe the point algorithm doesn't work there ?

image

[kewp]

Here is my code

        int found=1;
        while (edge) { 

            jcv_point diff;
            diff.x = edge->pos[1].x - edge->pos[0].x;
            diff.y = edge->pos[1].y - edge->pos[0].y;

            // pointing inwards
            jcv_point normal;
            normal.x = -diff.y;
            normal.y = diff.x; 

            jcv_point v;
            v.x = x - edge->pos[0].x;
            v.y = y - edge->pos[0].y;

            double dot = normal.x * v.x + normal.y * v.y;
            if (dot<0.0)
            {
                found=0;
                break;
            }

            edge = edge->next;
        }

[kewp]

Think the algorithm is right. I used the distance algorithm I described earlier and I'm getting the same result.

I think the problem is that I'm plotting with dots so it inevitably looks aliased

[kewp]

Yup. Looks better when I use smaller points image