Skip to main content
added 696 characters in body
Source Link
Quantum_Oli
  • 8k
  • 2
  • 21
  • 44

The link provided by corey979 in the comments to the question does certainly look close to the desired outcome. However I'm not sure it would generalise (easily) to the case with objects within a bounding region also occluding the vision. Here is a method using RegionIntersection, it is relatively slow (around a second in my test cases), and ideally would have a recursive procedure added to refine the visibility polygon where needed.

Setup

space = Polygon[{{0, 0}, {10, 0}, {10, 8}, {5, 8}, {5, 12}, {0, 12}}];
obstacles = {Rectangle[{2, 1}, {6, 3}], Disk[{5, 5}, 1], Polygon[{{7, 5}, {9, 5}, {8, 7}}]};
reg = RegionDifference[DiscretizeGraphics[space], DiscretizeGraphics[obstacles, MaxCellMeasure -> 0.03]];

vision = CirclePoints[2., 200];(*Could be altered to only permit a viewing angle < 360*)

loc = {2, 5.5};

Show[reg, Graphics[Point[loc]]]

enter image description here

Solve

mp = MeshPrimitives[RegionBoundary[reg], 1];

polypts = Flatten[
    ParallelTable[
     Nearest[
      DeleteCases[
        RegionIntersection[#, HalfLine[{loc, loc + v}]] & /@ mp, 
        EmptyRegion[2]][[;; , 1]], 
     loc, 1],
    {v, vision}],
   1
  ];

Show[reg, Graphics[{Point[loc], Opacity[0.5], Red, Polygon[polypts]}]]

enter image description here

You can see that at the edges of occluding objects the vision polygon sometimes clips through them. This will be an artefact of this method that will reduce as the number of vision lines increases, however this slows the process down. Better would be to use a few vision lines at the outset (20, maybe 50?) and then recursively refine (by adding further vision lines) those regions where the distance from loc to the termination points of subsequent vision lines changes abruptly.

Here is an exaggerated illustration of the problem with the vision lines used shown in blue:

enter image description here

The link provided by corey979 in the comments to the question does certainly look close to the desired outcome. However I'm not sure it would generalise (easily) to the case with objects within a bounding region also occluding the vision. Here is a method using RegionIntersection, it is relatively slow (around a second in my test cases), and ideally would have a recursive procedure added to refine the visibility polygon where needed.

space = Polygon[{{0, 0}, {10, 0}, {10, 8}, {5, 8}, {5, 12}, {0, 12}}];
obstacles = {Rectangle[{2, 1}, {6, 3}], Disk[{5, 5}, 1], Polygon[{{7, 5}, {9, 5}, {8, 7}}]};
reg = RegionDifference[DiscretizeGraphics[space], DiscretizeGraphics[obstacles, MaxCellMeasure -> 0.03]];

vision = CirclePoints[2., 200];(*Could be altered to only permit a viewing angle < 360*)

loc = {2, 5.5};

Show[reg, Graphics[Point[loc]]]

enter image description here

mp = MeshPrimitives[RegionBoundary[reg], 1];

polypts = Flatten[
    ParallelTable[
     Nearest[
      DeleteCases[
        RegionIntersection[#, HalfLine[{loc, loc + v}]] & /@ mp, 
        EmptyRegion[2]][[;; , 1]], 
     loc, 1],
    {v, vision}],
   1
  ];

Show[reg, Graphics[{Point[loc], Opacity[0.5], Red, Polygon[polypts]}]]

enter image description here

The link provided by corey979 in the comments to the question does certainly look close to the desired outcome. However I'm not sure it would generalise (easily) to the case with objects within a bounding region also occluding the vision. Here is a method using RegionIntersection, it is relatively slow (around a second in my test cases), and ideally would have a recursive procedure added to refine the visibility polygon where needed.

Setup

space = Polygon[{{0, 0}, {10, 0}, {10, 8}, {5, 8}, {5, 12}, {0, 12}}];
obstacles = {Rectangle[{2, 1}, {6, 3}], Disk[{5, 5}, 1], Polygon[{{7, 5}, {9, 5}, {8, 7}}]};
reg = RegionDifference[DiscretizeGraphics[space], DiscretizeGraphics[obstacles, MaxCellMeasure -> 0.03]];

vision = CirclePoints[2., 200];(*Could be altered to only permit a viewing angle < 360*)

loc = {2, 5.5};

Show[reg, Graphics[Point[loc]]]

enter image description here

Solve

mp = MeshPrimitives[RegionBoundary[reg], 1];

polypts = Flatten[
    ParallelTable[
     Nearest[
      DeleteCases[
        RegionIntersection[#, HalfLine[{loc, loc + v}]] & /@ mp, 
        EmptyRegion[2]][[;; , 1]], 
     loc, 1],
    {v, vision}],
   1
  ];

Show[reg, Graphics[{Point[loc], Opacity[0.5], Red, Polygon[polypts]}]]

enter image description here

You can see that at the edges of occluding objects the vision polygon sometimes clips through them. This will be an artefact of this method that will reduce as the number of vision lines increases, however this slows the process down. Better would be to use a few vision lines at the outset (20, maybe 50?) and then recursively refine (by adding further vision lines) those regions where the distance from loc to the termination points of subsequent vision lines changes abruptly.

Here is an exaggerated illustration of the problem with the vision lines used shown in blue:

enter image description here

Source Link
Quantum_Oli
  • 8k
  • 2
  • 21
  • 44

The link provided by corey979 in the comments to the question does certainly look close to the desired outcome. However I'm not sure it would generalise (easily) to the case with objects within a bounding region also occluding the vision. Here is a method using RegionIntersection, it is relatively slow (around a second in my test cases), and ideally would have a recursive procedure added to refine the visibility polygon where needed.

space = Polygon[{{0, 0}, {10, 0}, {10, 8}, {5, 8}, {5, 12}, {0, 12}}];
obstacles = {Rectangle[{2, 1}, {6, 3}], Disk[{5, 5}, 1], Polygon[{{7, 5}, {9, 5}, {8, 7}}]};
reg = RegionDifference[DiscretizeGraphics[space], DiscretizeGraphics[obstacles, MaxCellMeasure -> 0.03]];

vision = CirclePoints[2., 200];(*Could be altered to only permit a viewing angle < 360*)

loc = {2, 5.5};

Show[reg, Graphics[Point[loc]]]

enter image description here

mp = MeshPrimitives[RegionBoundary[reg], 1];

polypts = Flatten[
    ParallelTable[
     Nearest[
      DeleteCases[
        RegionIntersection[#, HalfLine[{loc, loc + v}]] & /@ mp, 
        EmptyRegion[2]][[;; , 1]], 
     loc, 1],
    {v, vision}],
   1
  ];

Show[reg, Graphics[{Point[loc], Opacity[0.5], Red, Polygon[polypts]}]]

enter image description here