i actually happen to have something cooked up already, that might suit
your purpose. it is part of a larger work in progress and i have
copypasted only the parts that should help you with your problem. what
i am trying to say is: i have not checked this snippet very thoroughly
and i perhaps forgot to include a function that is called somewhere in
this code. just tell me, if you should find that something is missing.
with this snippet you should be able to find out if polygon_p has
intersecting edges with polygon_q by calling polygon_p.Intersects
(polygon_q); if polygon_p contains polygon_q by calling
polygon_p.Contains(polygon_q); and if polygon_p intersects with
polygon_q in the set-theoretical sense, by calling polygon_p.Overlaps
(polygon_q).
have a nice day
götz
/*******************************************
*
* GFLineSegment new GFLineSegment(GLatLng, GLatLng)
* source : GF
*
*******************************************/
function GFLineSegment(p0, p1)
{
this.StartPoint = p0;
this.EndPoint = p1;
}
/*******************************************
*
* GLatLngBounds GFLineSegment.GetLatLngBounds()
* source : GF
*
*******************************************/
GFLineSegment.prototype.GetLatLngBounds = function()
{
bounds = new GLatLngBounds();
bounds.extend(this.StartPoint);
bounds.extend(this.EndPoint);
return bounds;
}
/*******************************************
*
* Boolean GFLineSegment.Equals(GFLineSegment)
* source : GF
*
*******************************************/
GFLineSegment.prototype.Equals = function(other)
{
if (((this.StartPoint == other.StartPoint) && (this.EndPoint ==
other.EndPoint)) || ((this.StartPoint == other.EndPoint) &&
(this.EndPoint == other.StartPoint)))
{
return true;
}
else
{
return false;
}
}
/*******************************************
*
* Integer GFLineSegment.Intersects(GFLineSegment)
* source : GF
* returns : false if segments do not intersect
* true if segments intersect
* false if segements are coincident
* false if segments touch at one end
*
*******************************************/
GFLineSegment.prototype.Intersects = function(other)
{
var intersection;
var x1 = this.StartPoint.lng();
var y1 = this.StartPoint.lat();
var x2 = this.EndPoint.lng();
var y2 = this.EndPoint.lat();
var u1 = other.StartPoint.lng();
var v1 = other.StartPoint.lat();
var u2 = other.EndPoint.lng();
var v2 = other.EndPoint.lat();
// check if bounding boxes intersect
if (!(this.GetLatLngBounds().intersects(other.GetLatLngBounds())))
{
// cannot intersect
return false;
}
// get the (ax + by = c) form ...
var det = ((v2-v1)*(x2-x1))-((u2-u1)*(y2-y1));
var num_a = ((u2-u1)*(y1-v1))-((v2-v1)*(x1-u1));
var num_b = ((x2-x1)*(y1-v1))-((y2-y1)*(x1-u1));
// check if parallel or coincident
if (det == 0)
{
// lines are parallel, hence do not cross (in R2)
if (num_a == 0 && num_b == 0)
{
// lines are coincident
return false;
}
else
{
// parallel but not coincident, hence no intersection
return false;
// TODO: calculate if / where parallels in R2 cross on
spherical surface
}
}
// check "normal" case
else
{
var alpha_p = num_a/det;
var alpha_q = num_b/det;
if ((alpha_p >= 0) && (alpha_p <= 1) && (alpha_q >= 0) &&
(alpha_q <= 1)) // intersect
{
if (alpha_p == 0 || alpha_p == 1 || alpha_q == 0 ||
alpha_q == 1) // touch at one end of a segment
{
// touch at one end
return false;
}
else
{
// intersect
return true;
}
}
else
{
// do not intersect
return false;
}
}
}
/*******************************************
*
* GLatLng GFLineSegment.GetIntersection(GFLineSegment)
* source : GF
*
*******************************************/
GFLineSegment.prototype.GetIntersection = function(other)
{
var intersection;
var x1 = this.StartPoint.lng();
var y1 = this.StartPoint.lat();
var x2 = this.EndPoint.lng();
var y2 = this.EndPoint.lat();
var u1 = other.StartPoint.lng();
var v1 = other.StartPoint.lat();
var u2 = other.EndPoint.lng();
var v2 = other.EndPoint.lat();
if (!(this.GetLatLngBounds().intersects(other.GetLatLngBounds())))
{
intersection = new GLatLng(MN_DEFAULT, MN_DEFAULT, true);
intersection.Type = "none";
return intersection;
}
var det = ((v2-v1)*(x2-x1))-((u2-u1)*(y2-y1));
var num_a = ((u2-u1)*(y1-v1))-((v2-v1)*(x1-u1));
var num_b = ((x2-x1)*(y1-v1))-((y2-y1)*(x1-u1));
if (det == 0) // lines
are parallel, hence do not cross (in R2)
{
if (num_a == 0 && num_b == 0) // lines
are coincident
{
intersection = new GLatLng(MN_COINCIDENT, MN_COINCIDENT,
true)
intersection.Type = "coincident";
return intersection;
}
else
{
// TODO: calculate where parallels in R2 cross on
spherical surface
intersection = new GLatLng(MN_PARALLEL, MN_PARALLEL,
true);
intersection.Type = "parallel";
return intersection;
}
}
else
{
var alpha_p = num_a/det;
var alpha_q = num_b/det;
if ((alpha_p >= 0) && (alpha_p <= 1) && (alpha_q >= 0) &&
(alpha_q <= 1)) // intersect
{
xi = x1 + alpha_p*(x2-x1);
yi = y1 + alpha_p*(y2-y1);
intersection = new GLatLng(yi, xi);
if (alpha_p == 0 || alpha_p == 1 || alpha_q == 0 ||
alpha_q == 1) // touch at one end of a segment
{
intersection.Type = "touch";
intersection.Alpha_P = alpha_p;
intersection.Alpha_Q = alpha_q;
}
else
{
intersection.Type = "intersection";
intersection.Alpha_P = alpha_p;
intersection.Alpha_Q = alpha_q;
}
return intersection;
}
else // do not
intersect
{
intersection = new GLatLng(MN_DEFAULT, MN_DEFAULT, true);
intersection.Type = "none";
return intersection;
}
}
}
/*******************************************
*
* Boolean GPolygon.Contains(GLatLng || GPolyline || GPolygon)
* source : Mike Williams, GF
* found at: http://econym.googlepages.com/epoly.htm
*
*******************************************/
GPolygon.prototype.Contains = function(other)
{
// GPolygon.Contains(GLatLng other)
if (other instanceof GLatLng)
{
var i;
var j = 0;
var oddNodes = false;
var x = other.lng();
var y = other.lat();
for (i = 0; i < this.getVertexCount(); i++)
{
j++;
if (j == this.getVertexCount())
{
j = 0;
}
if (((this.getVertex(i).lat() < y) && (this.getVertex
(j).lat() >= y)) || ((this.getVertex(j).lat() < y) && (this.getVertex
(i).lat() >= y)))
{
if (this.getVertex(i).lng() + (y - this.getVertex
(i).lat())/(this.getVertex(j).lat() - this.getVertex(i).lat()) *
(this.getVertex(j).lng() - this.getVertex(i).lng()) < x)
{
oddNodes = !oddNodes
}
}
}
return oddNodes;
}
// GPolygon.Contains(GPolyline || GPolygon other)
if ((other instanceof GPolyline) || (other instanceof GPolygon))
{
var i;
if (this.Intersects(other))
{
return false;
}
if (!(this.Contains(other.getVertex(0))))
{
return false;
}
return true;
}
}
/*******************************************
*
* Boolean GPolygon.Intersects(GPolygon || GPolyline other)
* source : GF
* does : Returns true, if at least one of
* each polygon's edges intersect
*
*******************************************/
GPolygon.prototype.Intersects = function(other)
{
var i;
var j;
var thisSegment;
var otherSegment;
var intersection;
for (i = 0; i <= this.getVertexCount()-2; i++)
{
thisSegment = new GFLineSegment(this.getVertex(i),
this.getVertex(i+1));
for (j = 0; j <= other.getVertexCount()-2; j++)
{
otherSegment = new GFLineSegment(other.getVertex(j),
other.getVertex(j+1));
if (thisSegment.Intersects(otherSegment))
{
return true;
}
}
}
return false;
}
/*******************************************
*
* Boolean GPolygon.Overlaps(GPolygon other)
* source : GF
* does : returns true if this intersects other
* in the set theoretical meaning; that is
* when this and other share at least one
* point.
*
*******************************************/
GPolygon.prototype.Overlaps = function(other)
{
if (this.Intersects(other))
{
return true;
}
if (this.Contains(other))
{
return true;
}
if (other.Contains(this))
{
return true;
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Google Maps API" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/Google-Maps-API?hl=en
-~----------~----~----~----~------~----~------~--~---
