Intro
So I needed this function for my building generator script, for the floor plans to rotate the walls to the correct angle. But it doesn't know whether its concave or convex. This script checks for the point P, on a polygon, to see if its inside or outside the polygon consisting of all points minus the point P.Problem Breakdown
To find whether a point is inside or outside a polygon, I will need to use the Jordan Curve Theorem. To put it simply, for a point P, draw a line using its X axis, for each intersection with the polygon to the left or right of the point P, count it. If the count is even, then point P is outside, if its odd, it is inside. Imagine a pentagon. For its first point, pp0, I'd like to check if the angle0 is concave or convex.1. First I'll need to draw a line using the X axis through pp0. lineP
2. Secondly, I'll need to find the edges of the rectangle consisting of lines, line(pp4, pp1), line(pp1,pp2), line(pp2,pp3), line(pp3, pp4).
3. Use line-line intersection to see if line0, line1, line2, line3 intersects with lineP. If intersect, note if the intersection point is to the left or right of pp0 and add the count.
4. If the count is even, pp0 is outside the rectange, which makes angle0 convex, if the count is odd, pp0 is inside the rectangle, and makes angle0 concave.
Source
global proc int checkInside(int $i) {//checks
string $sel = "ngon";
int $vtxSize[] = `polyEvaluate -v "ngon"`;
int $a, $b, $c, $d, $e, $l_count, $r_count;
float $a1, $a2, $b1, $b2, $c1, $c2;
float $pp0[], $pp1[], $pp2[], $pointMax[], $pointXmin[];
float $xx, $yy, $det;
//this checks the immediate line AC from the point B. return should be boolean
$a = $i - 1;
$b = $i;
$c = $i + 1;
if($i == 0) {
$a = $vtxSize[0] - 1;
$b = 0;
}//if
float $pp0[] = pointPosition ($sel + ".vtx[" + $a + "]"); //coord of $a
float $pp1[] = pointPosition ($sel + ".vtx[" + $b + "]"); //after checking the above, if none of the above, continue getting pp of next two vtx
float $pp2[] = pointPosition ($sel + ".vtx[" + $c + "]"); //^
float $min = min($pp0[2], $pp2[2]);
float $max = max($pp0[2], $pp2[2]);
$pointXmax = $pp1;
$pointXmax[0] = $pointXmax[0] + 20;//arbitrary max, should be max x of the polygon
$pointXmin = $pp1;
$pointXmin[0] = $pointXmin[0] - 20;//lets only look at one side of the polygon
$a2 = $pointXmax[2] - $pointXmin[2];
$b2 = $pointXmin[0] - $pointXmax[0];
$c2 = ($a2 * $pointXmin[0] + $b2 * $pointXmin[2]);
if(($pp1[2] < $max) && ($pp1[2] > $min)) { //if inside do check
$a1 = $pp2[2] - $pp0[2];
$b1 = $pp0[0] - $pp2[0];
$c1 = ($a1 * $pp0[0]) + ($b1 * $pp0[2]);
$det = ($a1 * $b2) - ($a2 * $b1);
if($det != 0) {
$xx = ($b2*$c1 - $b1*$c2)/$det;
$yy = ($a1*$c2 - $a2*$c1)/$det;
}
else {
print "det = 0";
}
if($xx > $pp1[0]) {
$r_count = $r_count + 1;
}
else if($xx < $pp1[0]) {
$l_count = $l_count + 1;
}
}//if
//--------------------checks the imaginary line of prev and next point---end//
//check every other edge in the polygon
for($j = 0; $j < $vtxSize[0] - 2; $j++) {//every other edge
$d = $j + $i + 1;
$e = $d + 1;
if($e >= $vtxSize[0]) {
$e = $e - $vtxSize[0];
}
if($d >= $vtxSize[0]) {
$d = $d - $vtxSize[0];
}
float $pp0[] = pointPosition ($sel + ".vtx[" + $d + "]"); //coord of $a
float $pp2[] = pointPosition ($sel + ".vtx[" + $e + "]"); //^
float $min = min($pp0[2], $pp2[2]);
float $max = max($pp0[2], $pp2[2]);
if(($pp1[2] < $max) && ($pp1[2] > $min)) { //if inside do check
$a1 = $pp2[2] - $pp0[2];
$b1 = $pp0[0] - $pp2[0];
$c1 = ($a1 * $pp0[0]) + ($b1 * $pp0[2]);
$det = ($a1 * $b2) - ($a2 * $b1);
if($det != 0) {
$xx = ($b2*$c1 - $b1*$c2)/$det;
$yy = ($a1*$c2 - $a2*$c1)/$det;
}
if($xx > $pp1[0]) { //jordan curve theorem, simmple test to see inside or outside
$r_count = $r_count + 1;
}
else if($xx < $pp1[0]) {
$l_count = $l_count + 1;
}
//print ("rcount = " + $r_count + "\n");
//print ("lcount = " + $l_count + "\n");
}//if inside
} //for $j
if($l_count % 2 == 0) {//even == outside
return 0;
}
else return 1;
}
Notes
Input: int $i, point $i on the polygon.
Output: boolean, 0 = outside, 1 = inside.
