|
|
80bc9b |
/*
|
|
|
80bc9b |
......... 2015 Ivan Mahonin
|
|
|
80bc9b |
|
|
|
80bc9b |
This program is free software: you can redistribute it and/or modify
|
|
|
80bc9b |
it under the terms of the GNU General Public License as published by
|
|
|
80bc9b |
the Free Software Foundation, either version 3 of the License, or
|
|
|
80bc9b |
(at your option) any later version.
|
|
|
80bc9b |
|
|
|
80bc9b |
This program is distributed in the hope that it will be useful,
|
|
|
80bc9b |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
80bc9b |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
80bc9b |
GNU General Public License for more details.
|
|
|
80bc9b |
|
|
|
80bc9b |
You should have received a copy of the GNU General Public License
|
|
|
80bc9b |
along with this program. If not, see <http: licenses="" www.gnu.org="">.</http:>
|
|
|
80bc9b |
*/
|
|
|
80bc9b |
|
|
|
f6cc12 |
using System;
|
|
|
f6cc12 |
using System.Drawing;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
namespace Contours {
|
|
|
f6cc12 |
public static class Geometry {
|
|
|
f6cc12 |
public enum IntersectionType {
|
|
|
f6cc12 |
None,
|
|
|
f6cc12 |
Cross,
|
|
|
f6cc12 |
Identical,
|
|
|
f6cc12 |
Inverted,
|
|
|
f6cc12 |
Touch_a0,
|
|
|
f6cc12 |
Touch_a1,
|
|
|
f6cc12 |
Touch_b0,
|
|
|
f6cc12 |
Touch_b1,
|
|
|
f6cc12 |
Touch_a0_b0,
|
|
|
f6cc12 |
Touch_a0_b1,
|
|
|
f6cc12 |
Touch_a1_b0,
|
|
|
f6cc12 |
Touch_a1_b1,
|
|
|
f6cc12 |
Along_a0_b0_a1_b1,
|
|
|
f6cc12 |
Along_a0_b0_b1_a1,
|
|
|
f6cc12 |
Along_a0_b1_a1_b0,
|
|
|
f6cc12 |
Along_a0_b1_b0_a1,
|
|
|
f6cc12 |
Along_b0_a0_a1_b1,
|
|
|
f6cc12 |
Along_b0_a0_b1_a1,
|
|
|
f6cc12 |
Along_b1_a0_a1_b0,
|
|
|
f6cc12 |
Along_b1_a0_b0_a1
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// Compare to points place at line base0-base1
|
|
|
f6cc12 |
public static int comparePointsAtLine(Point a0, Point a1, Point base0, Point base1) {
|
|
|
f6cc12 |
if (base0.X < base1.X && a0.X < a1.X) return -1;
|
|
|
f6cc12 |
if (base0.X < base1.X && a1.X < a0.X) return 1;
|
|
|
f6cc12 |
if (base1.X < base0.X && a0.X < a1.X) return 1;
|
|
|
f6cc12 |
if (base1.X < base0.X && a1.X < a0.X) return -1;
|
|
|
f6cc12 |
if (base0.Y < base1.Y && a0.Y < a1.Y) return -1;
|
|
|
f6cc12 |
if (base0.Y < base1.Y && a1.Y < a0.Y) return 1;
|
|
|
f6cc12 |
if (base1.Y < base0.Y && a0.Y < a1.Y) return 1;
|
|
|
f6cc12 |
if (base1.Y < base0.Y && a1.Y < a0.Y) return -1;
|
|
|
f6cc12 |
return 0;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
b0fc65 |
public static bool isPointAtLine(Point p, Point p0, Point p1) {
|
|
|
b0fc65 |
if (p == p0 || p == p1)
|
|
|
b0fc65 |
return true;
|
|
|
b0fc65 |
if (p0 == p1)
|
|
|
b0fc65 |
return false;
|
|
|
b0fc65 |
if ((long)(p.Y-p0.Y)*(long)(p1.X-p0.X) != (long)(p.X-p0.X)*(long)(p1.Y-p0.Y))
|
|
|
b0fc65 |
return false;
|
|
|
b0fc65 |
if (p1.X > p0.X)
|
|
|
b0fc65 |
return p.X >= p0.X && p.X <= p1.X;
|
|
|
b0fc65 |
if (p1.X < p0.X)
|
|
|
b0fc65 |
return p.X >= p1.X && p.X <= p0.X;
|
|
|
b0fc65 |
if (p1.Y > p0.Y)
|
|
|
b0fc65 |
return p.Y >= p0.Y && p.Y <= p1.Y;
|
|
|
b0fc65 |
//if (p1.Y < p0.Y)
|
|
|
b0fc65 |
return p.Y >= p1.Y && p.Y <= p0.Y;
|
|
|
b0fc65 |
}
|
|
|
b0fc65 |
|
|
|
f6cc12 |
public static IntersectionType findIntersection(Point a0, Point a1, Point b0, Point b1, out Point c) {
|
|
|
f6cc12 |
c = new Point(0, 0);
|
|
|
f6cc12 |
Point da = new Point(a1.X - a0.X, a1.Y - a0.Y);
|
|
|
f6cc12 |
Point db = new Point(b1.X - b0.X, b1.Y - b0.Y);
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (a0.X == b0.X && a0.Y == b0.Y && a1.X == b1.X && a1.Y == b1.Y)
|
|
|
f6cc12 |
return IntersectionType.Identical;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (a0.X == b1.X && a0.Y == b1.Y && a1.X == b0.X && a1.Y == b0.Y)
|
|
|
f6cc12 |
return IntersectionType.Inverted;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
long divider = (long)da.X*(long)db.Y - (long)db.X*(long)da.Y;
|
|
|
f6cc12 |
if (divider == 0) {
|
|
|
f6cc12 |
if ((long)da.X*(long)(b0.Y - a0.Y) != (long)da.Y*(long)(b0.X - a0.X))
|
|
|
f6cc12 |
return IntersectionType.None;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
int a0b0 = comparePointsAtLine(a0, b0, a0, a1);
|
|
|
f6cc12 |
int a0b1 = comparePointsAtLine(a0, b1, a0, a1);
|
|
|
f6cc12 |
int a1b0 = comparePointsAtLine(a1, b0, a0, a1);
|
|
|
f6cc12 |
int a1b1 = comparePointsAtLine(a1, b1, a0, a1);
|
|
|
f6cc12 |
int b0b1 = comparePointsAtLine(b0, b1, a0, a1);
|
|
|
f6cc12 |
int b0a0 = -a0b0;
|
|
|
f6cc12 |
int b0a1 = -a1b0;
|
|
|
f6cc12 |
int b1a0 = -a0b1;
|
|
|
f6cc12 |
int b1a1 = -a1b1;
|
|
|
f6cc12 |
int b1b0 = -b0b1;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
// a0a1b0b1
|
|
|
04c11c |
if (a1b0 == 0 && b0b1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Touch_a1_b0;
|
|
|
f6cc12 |
// a0a1b1b0
|
|
|
04c11c |
if (a1b1 == 0 && b1b0 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Touch_a1_b1;
|
|
|
f6cc12 |
// b0b1a0a1
|
|
|
04c11c |
if (b0b1 <= 0 && b1a0 == 0)
|
|
|
f6cc12 |
return IntersectionType.Touch_a0_b1;
|
|
|
f6cc12 |
// b1b0a0a1
|
|
|
04c11c |
if (b1b0 <= 0 && b0a0 == 0)
|
|
|
f6cc12 |
return IntersectionType.Touch_a0_b0;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (a0b0 <= 0 && b0a1 <= 0 && a1b1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_a0_b0_a1_b1;
|
|
|
f6cc12 |
if (a0b0 <= 0 && b0b1 <= 0 && b1a1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_a0_b0_b1_a1;
|
|
|
f6cc12 |
if (a0b1 <= 0 && b1a1 <= 0 && a1b0 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_a0_b1_a1_b0;
|
|
|
f6cc12 |
if (a0b1 <= 0 && b1b0 <= 0 && b0a1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_a0_b1_b0_a1;
|
|
|
f6cc12 |
if (b0a0 <= 0 && /* a0a1 */ a1b1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_b0_a0_a1_b1;
|
|
|
f6cc12 |
if (b0a0 <= 0 && a0b1 <= 0 && b1a1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_b0_a0_b1_a1;
|
|
|
f6cc12 |
if (b1a0 <= 0 && /* a0a1 */ a1b0 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_b1_a0_a1_b0;
|
|
|
f6cc12 |
if (b1a0 <= 0 && a0b0 <= 0 && b0a1 <= 0)
|
|
|
f6cc12 |
return IntersectionType.Along_b1_a0_b0_a1;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
return IntersectionType.None;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (a0.X == b0.X && a0.Y == b0.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a0_b0;
|
|
|
f6cc12 |
if (a0.X == b1.X && a0.Y == b1.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a0_b1;
|
|
|
f6cc12 |
if (a1.X == b0.X && a1.Y == b0.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a1_b0;
|
|
|
f6cc12 |
if (a1.X == b1.X && a1.Y == b1.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a1_b1;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
long numeratorX = (long)da.X*((long)b1.Y*(long)b0.X - (long)b0.Y*(long)b1.X)
|
|
|
f6cc12 |
- (long)db.X*((long)a1.Y*(long)a0.X - (long)a0.Y*(long)a1.X);
|
|
|
f6cc12 |
long numeratorY = (long)db.Y*((long)a1.X*(long)a0.Y - (long)a0.X*(long)a1.Y)
|
|
|
f6cc12 |
- (long)da.Y*((long)b1.X*(long)b0.Y - (long)b0.X*(long)b1.Y);
|
|
|
f6cc12 |
Point p = new Point((int)(numeratorX/divider), (int)(numeratorY/divider));
|
|
|
04c11c |
if ( comparePointsAtLine(p, a0, a0, a1) < 0
|
|
|
04c11c |
|| comparePointsAtLine(p, a1, a0, a1) > 0
|
|
|
04c11c |
|| comparePointsAtLine(p, b0, b0, b1) < 0
|
|
|
04c11c |
|| comparePointsAtLine(p, b1, b0, b1) > 0 )
|
|
|
f6cc12 |
return IntersectionType.None;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
if (p.X == a0.X && p.Y == a0.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a0;
|
|
|
f6cc12 |
if (p.X == a1.X && p.Y == a1.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_a1;
|
|
|
f6cc12 |
if (p.X == b0.X && p.Y == b0.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_b0;
|
|
|
f6cc12 |
if (p.X == b1.X && p.Y == b1.Y)
|
|
|
f6cc12 |
return IntersectionType.Touch_b1;
|
|
|
f6cc12 |
|
|
|
f6cc12 |
c = p;
|
|
|
f6cc12 |
return IntersectionType.Cross;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
public static bool isCCW(Point a, Point b, Point c) {
|
|
|
f6cc12 |
long d = (long)a.X*(long)c.Y - (long)a.Y*(long)c.X;
|
|
|
f6cc12 |
// angle AC < 180 deg
|
|
|
f6cc12 |
if (d > 0)
|
|
|
f6cc12 |
return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X
|
|
|
f6cc12 |
&& (long)c.X*(long)b.Y <= (long)c.Y*(long)b.X;
|
|
|
f6cc12 |
// angle AC > 180 deg
|
|
|
f6cc12 |
if (d < 0)
|
|
|
f6cc12 |
return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X
|
|
|
f6cc12 |
|| (long)c.X*(long)b.Y <= (long)c.Y*(long)b.X;
|
|
|
f6cc12 |
// angle AC == 180 deg
|
|
|
f6cc12 |
if ((a.X >= 0) != (c.X >= 0) || (a.Y >= 0) != (c.Y >= 0))
|
|
|
f6cc12 |
return (long)a.X*(long)b.Y >= (long)a.Y*(long)b.X;
|
|
|
f6cc12 |
// angle AC == 0 deg
|
|
|
f6cc12 |
return true;
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
public static bool isCCW(Point center, Point a, Point b, Point c) {
|
|
|
f6cc12 |
return isCCW(
|
|
|
f6cc12 |
new Point(a.X - center.X, a.Y - center.Y),
|
|
|
f6cc12 |
new Point(b.X - center.X, b.Y - center.Y),
|
|
|
f6cc12 |
new Point(c.X - center.X, c.Y - center.Y) );
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
public static void makeLongestLine(Point p0, ref Point p1) {
|
|
|
4717b8 |
int MaxValue = int.MaxValue >> 1;
|
|
|
f6cc12 |
Point direction = new Point(p1.X - p0.X, p1.Y - p0.Y);
|
|
|
f6cc12 |
int amplifierX =
|
|
|
f6cc12 |
direction.X > 0 ? (MaxValue - p0.X)/direction.X + 1
|
|
|
f6cc12 |
: direction.X < 0 ? (MaxValue + p0.X)/(-direction.X) + 1
|
|
|
f6cc12 |
: int.MaxValue;
|
|
|
f6cc12 |
int amplifierY =
|
|
|
f6cc12 |
direction.Y > 0 ? (MaxValue - p0.Y)/direction.Y + 1
|
|
|
f6cc12 |
: direction.Y < 0 ? (MaxValue + p0.Y)/(-direction.Y) + 1
|
|
|
f6cc12 |
: int.MaxValue;
|
|
|
f6cc12 |
int amplifier = Math.Min(amplifierX, amplifierY);
|
|
|
f6cc12 |
p1 = new Point(
|
|
|
f6cc12 |
p0.X + direction.X*amplifier,
|
|
|
f6cc12 |
p0.Y + direction.Y*amplifier );
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
}
|
|
|
f6cc12 |
|