fork(4) download
copy 
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5.  
  6. public static class Program
  7. {
  8.     public static void Main()
  9.     {
  10.     	var samples = new Dictionary<string, Polygon>
  11.     	{
  12. 	        { "a", new Polygon
  13. 		        {
  14. 		            { -5,  1 },
  15. 		            { -3,  3 },
  16. 		            { -1,  5 },
  17. 		            {  1,  5 },
  18. 		            {  3,  3 },
  19. 		            {  5,  1 },
  20. 		            {  5, -1 },
  21. 		            {  3, -3 },
  22. 		            {  1, -5 },
  23. 		            { -1, -5 },
  24. 		            { -3, -3 },
  25. 		            { -5, -1 },
  26. 		        } },
  27. 	        { "b", new Polygon
  28. 		        {
  29. 		            { -3,  0 },
  30. 		            {  0,  3 },
  31. 		            {  3,  0 },
  32. 		            {  0, -3 },
  33. 		        } },
  34. 	        { "c", new Polygon
  35. 		        {
  36. 		            {  4,  0 },
  37. 		            {  7,  3 },
  38. 		            { 10,  0 },
  39. 		            {  7, -3 },
  40. 		        } }
  41.         };
  42.  
  43.         foreach (var p1 in samples)
  44.         foreach (var p2 in samples) {
  45.         	var result = IsPolygonsIntersecting(p1.Value, p2.Value);
  46.         	Console.WriteLine("IsPolygonsIntersecting({0}, {1}) = {2}",
  47.         		p1.Key, p2.Key, result);
  48.         }
  49.     }
  50.  
  51.     static bool IsPolygonsIntersecting(Polygon a, Polygon b)
  52.     {
  53.         foreach (var polygon in new[] { a, b })
  54.         {
  55.             for (int i1 = 0; i1 < polygon.Points.Count; i1++)
  56.             {
  57.                 int i2 = (i1 + 1) % polygon.Points.Count;
  58.                 var p1 = polygon.Points[i1];
  59.                 var p2 = polygon.Points[i2];
  60.  
  61.                 var normal = new Point(p2.Y - p1.Y, p1.X - p2.X);
  62.  
  63.                 double? minA = null, maxA = null;
  64.                 foreach (var p in a.Points)
  65.                 {
  66.                     var projected = normal.X * p.X + normal.Y * p.Y;
  67.                     if (minA == null || projected < minA)
  68.                         minA = projected;
  69.                     if (maxA == null || projected > maxA)
  70.                         maxA = projected;
  71.                 }
  72.  
  73.                 double? minB = null, maxB = null;
  74.                 foreach (var p in b.Points)
  75.                 {
  76.                     var projected = normal.X * p.X + normal.Y * p.Y;
  77.                     if (minB == null || projected < minB)
  78.                         minB = projected;
  79.                     if (maxB == null || projected > maxB)
  80.                         maxB = projected;
  81.                 }
  82.  
  83.                 if (maxA < minB || maxB < minA)
  84.                     return false;
  85.             }
  86.         }
  87.         return true;
  88.     }
  89. }
  90.  
  91. class Polygon : IEnumerable<Point> {
  92.     public List<Point> Points { get; set; }
  93.  
  94.     public Polygon() : this(new Point[0]) {  }
  95.     public Polygon(IEnumerable<Point> points) {
  96.         this.Points = points.ToList();
  97.     }
  98.  
  99.     public IEnumerator<Point> GetEnumerator() {
  100.         return Points.GetEnumerator();
  101.     }
  102.  
  103.     IEnumerator IEnumerable.GetEnumerator() {
  104.         return this.GetEnumerator();
  105.     }
  106.  
  107.     public void Add(Point p) {
  108.         this.Points.Add(p);
  109.     }
  110.  
  111.     public void Add(double x, double y) {
  112.         this.Add(new Point(x, y));
  113.     }
  114. }
  115.  
  116. class Point {
  117.     public double X { get; set; }
  118.     public double Y { get; set; }
  119.  
  120.     public Point(double x = 0, double y = 0) {
  121.         this.X = x;
  122.         this.Y = y;
  123.     }
  124. }
Success #stdin #stdout 0.03s 34024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IsPolygonsIntersecting(a, a) = True
IsPolygonsIntersecting(a, b) = True
IsPolygonsIntersecting(a, c) = True
IsPolygonsIntersecting(b, a) = True
IsPolygonsIntersecting(b, b) = True
IsPolygonsIntersecting(b, c) = False
IsPolygonsIntersecting(c, a) = True
IsPolygonsIntersecting(c, b) = False
IsPolygonsIntersecting(c, c) = True
https://ideone.com/H7DWOO
Polygon intersection
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!