Method ELleftbnd

src/LNLib/Algorithm/Voronoi.cpp:276–326

}

struct LNLib::Halfedge* LNLib::VoronoiDiagramGenerator::ELleftbnd(struct PointVDG* p)
{
	int i, bucket;
	struct Halfedge* he;

	/* Use hash table to get close to desired halfedge */
	bucket = (int)((p->x - xmin) / deltax * ELhashsize);	//use the hash function to find the place in the hash map that this HalfEdge should be

	if (bucket < 0) bucket = 0;					//make sure that the bucket position in within the range of the hash array
	if (bucket >= ELhashsize) bucket = ELhashsize - 1;

	he = ELgethash(bucket);
	if (he == (struct Halfedge*)NULL)			//if the HE isn't found, search backwards and forwards in the hash map for the first non-null entry
	{
		for (i = 1; 1; i += 1)
		{
			if ((he = ELgethash(bucket - i)) != (struct Halfedge*)NULL)
				break;
			if ((he = ELgethash(bucket + i)) != (struct Halfedge*)NULL)
				break;
		};
		totalsearch += i;
	};
	ntry += 1;
	/* Now search linear list of halfedges for the correct one */
	if (he == ELleftend || (he != ELrightend && right_of(he, p)))
	{
		do
		{
			he = he->ELright;
		} while (he != ELrightend && right_of(he, p));	//keep going right on the list until either the end is reached, or you find the 1st edge which the point
		he = he->ELleft;				//isn't to the right of
	}
	else 							//if the point is to the left of the HalfEdge, then search left for the HE just to the left of the point
		do
		{
			he = he->ELleft;
		} while (he != ELleftend && !right_of(he, p));

		/* Update hash table and reference counts */
		if (bucket > 0 && bucket < ELhashsize - 1)
		{
			if (ELhash[bucket] != (struct Halfedge*)NULL)
			{
				ELhash[bucket]->ELrefcnt -= 1;
			}
			ELhash[bucket] = he;
			ELhash[bucket]->ELrefcnt += 1;
		};
		return (he);
}


/* This delete routine can't reclaim node, since pointers from hash