Site-point collisions about voronoi HOT 9 CLOSED

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

from voronoi.

"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

from voronoi.

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 ?

from voronoi.

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.

from voronoi.

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 !

from voronoi.

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

image

from voronoi.

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;
    	}

from voronoi.

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

from voronoi.

Yup. Looks better when I use smaller points image

from voronoi.