PERSPECTIVE DETERMINATION METHOD, PERSPECTIVE DETERMINATION APPARATUS AND PROGRAM

Abstract

A line-of-sight determination method includes: a point cloud data acquisition step of acquiring point cloud data including a first position indicating a position of a first wireless station and a plurality of second positions indicating positions on a structure serving as a candidate in which a second wireless station opposing the first wireless station is to be installed; and a line-of-sight determination step of determining whether or not there is a line of sight between the first position and at least one of the second positions, and determining whether or not there is a line of sight between the first wireless station and the structure based on the determination result. In the line-of-sight determination step, if it has been determined that there is no line of sight between the first position and a first second position of the second positions, it is not determined whether or not there is a line of sight between the first position and a second second position among the second positions, the second second position being located in the vicinity of the first second position.

Claims

1. A line-of-sight determination method comprising: a point cloud data acquisition step of acquiring point cloud data including a first position indicating a position of a first wireless station and a plurality of second positions indicating positions on a structure serving as a candidate in which a second wireless station opposing the first wireless station is to be installed; and a line-of-sight determination step of determining whether or not there is a line of sight between the first position and at least one of the second positions, and determining whether or not there is a line of sight between the first wireless station and the structure based on the determination result, wherein in the line-of-sight determination step, if it has been determined that there is no line of sight between the first position and a first second position among the second positions, it is not determined whether or not there is a line of sight between the first position and a second second position among the second positions, the second second position being located in the vicinity of the first second position.

2. The line-of-sight determination method according to claim 1, wherein a distance between the first second position and the second second position is a distance based on a beam width of an electromagnetic wave emitted in wireless communication between the first wireless station and the second wireless station.

3. The line-of-sight determination method according to claim 1, wherein a distance between the first second position and the second second position is a distance based on a size of a Fresnel zone of an electromagnetic wave emitted in wireless communication between the first wireless station and the second wireless station.

4. The line-of-sight determination method according to claim 1, wherein a distance between the first second position and the second second position is a distance based on a size of an object located between the first wireless station and the structure.

5. The line-of-sight determination method according to claim 1, wherein an angle between the first second position and the second second position at the first position is a predetermined angle or less.

6. The line-of-sight determination method according to claim 1, wherein in the line-of-sight determination step, if it has been determined that there is no line of sight between the first position and the first second position, subsequently, it is determined whether or not there is a line of sight between the first position and a third second position among the second positions, the third second position being located the farthest from the first second position among the second positions.

7. A line-of-sight determination apparatus comprising: a processor; and a storage medium having computer program instructions stored thereon, when executed by the processor, perform to: acquire point cloud data including a first position indicating a position of a first wireless station and a plurality of second positions indicating positions on a structure serving as a candidate in which a second wireless station opposing the first wireless station is to be installed; and determine whether or not there is a line of sight between the first position and at least one of the second positions, and determine whether or not there is a line of sight between the first wireless station and the structure based on the determination result, wherein if it has been determined that there is no line of sight between the first position and a first second position among the second positions, does not determine whether or not there is a line of sight between the first position and a second second position among the second positions, the second second position being located in the vicinity of the first second position.

8. A non-transitory computer-readable medium having computer-executable instructions that, upon execution of the instructions by a processor of a computer, cause the computer to function as the line-of-sight determination method according to claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0028] FIG. 1 is a schematic diagram showing line-of-sight determination performed by a line-of-sight determination apparatus according to a first embodiment of the present invention.

[0029] FIG. 2 is a block diagram showing a functional configuration of a line-of-sight determination apparatus according to the first embodiment of the present invention.

[0030] FIG. 3 is a flowchart showing operations of the line-of-sight determination apparatus according to the first embodiment of the present invention.

[0031] FIG. 4 is a schematic diagram showing line-of-sight determination performed by a line-of-sight determination apparatus according to a fifth embodiment of the present invention.

[0032] FIG. 5 is a diagram for illustrating a separation angle according to the fifth embodiment of the present invention.

[0033] FIG. 6 is a schematic diagram showing line-of-sight determination performed by a line-of-sight determination apparatus according to a sixth embodiment of the present invention.

[0034] FIG. 7 is a flowchart showing operations of the line-of-sight determination apparatus according to the sixth embodiment of the present invention.

DESCRIPTION OF EMBODIMENTS

[0035] Hereinafter, a line-of-sight determination method, a line-of-sight determination apparatus, and a program according to an embodiment of the present invention will be described with reference to the drawings.

[0036] As a premise, a line-of-sight determination apparatus 1 in each embodiment described hereinafter aims to quickly determine whether or not there is a line of sight in the traffic of electromagnetic waves for wireless communication, between a wireless base station installation position candidate (e.g., a utility pole, etc.) of a wireless base station and a building or the like that is an installation position candidate of a wireless terminal station. The line-of-sight determination processing performed by the line-of-sight determination apparatus 1 is basically performed in the following flow.

[0037] First, the line-of-sight determination apparatus 1 selects any installation position candidate from among a plurality of installation position candidates for a wireless base station. Next, the line-of-sight determination apparatus 1 determines whether or not there is a line of sight between the selected installation position candidate of the wireless base station and each building or the like that is present within a service provision region (e.g., a residential area, etc.).

[0038] However, in a building or the like (for example, on a wall surface of a building or the like), there are a plurality of installation position candidates at which a wireless terminal station can be installed. The line-of-sight determination apparatus 1 determines whether or not there is a line of sight between the installation position candidate of the wireless base station and at least one installation position candidate among the plurality of installation position candidates in the building or the like (e.g., on the wall surface). Based on the determination result, the line-of-sight determination apparatus 1 determines whether or not there is a line of sight between the above-selected wireless base station installation position candidate and each building or the like.

[0039] Here, the line-of-sight determination apparatus 1 determines that there is a line of sight between an installation position candidate or the wireless base station and the building or the like if at least one of the plurality of installation position candidates determined as having a line of sight is present in a certain building or the like. On the other hand, the line-of-sight determination apparatus 1 determines that there is no line of sight between the installation position candidate of the wireless base station and the building or the like if it is determined that there is no line of sight between the above-described plurality of installation position candidates and the installation position candidate of the wireless base station in a certain building or the like. By performing such a determination, the line-of-sight determination apparatus 1 can prevent erroneous determination that there is no line of sight between the installation position candidate of the wireless base station and the building or the like even though there is at least one installation position candidate that has a line of sight with the installation position candidate of the wireless base station among the plurality of installation position candidates for the wireless terminal station.

[0040] The line-of-sight determination apparatus 1 determines whether or not there is the above-mentioned line of sight for each building or the like for all installation position candidates for the wireless base station. As a result, the line-of-sight determination apparatus 1 can distinguish between a building or the like with a line of sight and a building or the like without a line of sight for each installation position candidate of the wireless base station. Then, by solving the combination problem using the above-mentioned result of determining whether or not there is a line of sight obtained for each installation position candidate of the wireless base station, the line-of-sight determination apparatus 1 performs station placement design in which the installation position of the wireless base station is determined so as to minimize the number of wireless base stations while making it possible to accommodate all of the buildings and the like in the service providing area.

First Embodiment

[0041] Hereinafter, a first embodiment of the present invention will be described.

[0042] FIG. 1 is a schematic view showing line-of-sight determination performed by the line-of-sight determination apparatus 1 according to the first embodiment of the present invention.

[0043] First, the line-of-sight determination apparatus 1 selects any installation position candidate BS1 of the wireless base station (hereinafter, simply referred to as “wireless base station BS1”) from among a plurality of installation position candidates of the wireless base station, which are present in the service provision area. In addition, the line-of-sight determination apparatus 1 selects a building or the like (hereinafter, simply referred to as “building B2”) that is a target to be subjected to the determination of whether or not there is a line of sight from among a plurality of buildings or the like that are present in the service provision area (e.g., in a residential area). The line-of-sight determination apparatus 1 determines whether or not there is a line of sight between the wireless base station BS1 and the building B2.

[0044] FIG. 1 shows an example of a case of looking down on the wireless base station BS1, the building B2, and an obstruction B3 from directly above. As shown in FIG. 1, in the building B2 (e.g., on a wall surface thereof), there are N installation candidate points p.sub.n (n=1, 2, . . . , N), which are installation position candidates for the wireless terminal station. The N installation candidate points p.sub.n are arranged in a horizontal row at equal intervals, for example. The line-of-sight determination apparatus 1 first determines whether or not there is a line of sight between the wireless base station BS1 and an installation candidate point p.sub.1 on the leftmost end in the building B2. As shown in FIG. 1, there is an obstruction B3 between the wireless base station BS1 and the installation candidate point p.sub.1. Accordingly, the line-of-sight determination apparatus 1 determines that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1.

[0045] In such a case, in general, the line-of-sight determination apparatus often sets an installation candidate point p.sub.2 adjacent to the installation candidate point p.sub.1 (located one to the right of the installation candidate point p.sub.1 in FIG. 1) as the next determination target and performs determination of whether or not there is a line of sight between the wireless base station BS1 and the installation candidate point p.sub.2. However, the setting interval of the point cloud data such as the installation candidate point p.sub.n is commonly an interval in units of centimeters or millimeters. In contrast to this, the width of the obstruction B3 is commonly a length in units of meters in many cases. That is, if the interval between two adjacent installation candidate points p.sub.n is l.sub.p and the width of the obstruction B3 is l.sub.b, the relationship between l.sub.p and l.sub.b is expressed by the following equation (1).

[Math. 1]

l.sub.p<<l.sub.b  (1)

[0046] In this manner, the width l.sub.b of the obstruction B3 is relatively quite wide compared to the interval l.sub.p between two adjacent installation candidate points p.sub.n. For this reason, if it is determined that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1, it can be said that there is a very high likelihood that it will be determined that there is similarly no line of sight between the wireless base station BS1 and the installation candidate point p.sub.2 (which is located in the vicinity of the installation candidate point p.sub.1) as well.

[0047] Note that in general, the width l.sub.b of the obstruction B3 is unknown, and in actuality, the width l.sub.b may not necessarily be much wider than the above interval l.sub.p. However, in order to specify the width l.sub.b of the obstruction B3, it is easily expected that analysis of a large number of pieces of point cloud data will be required and a huge amount of calculation time will be required. Thus, in the present embodiment, the width l.sub.b of the obstruction B3 is not specified.

[0048] The line-of-sight determination apparatus 1 in the present embodiment holds in advance a value of the separation distance l.sub.q that satisfies the following equation (2).

[Math. 2]

l.sub.p<l.sub.q  (2)

[0049] For example, if it is determined that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1, the line-of-sight determination apparatus 1 similarly assumes that there is no line of sight with the wireless base station BS1 also for another installation candidate point p.sub.n present at a position for which the distance from the installation candidate point p.sub.1 is within the separation distance l.sub.w. In the example shown in FIG. 1, if it is determined that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1, the line-of-sight determination apparatus 1 assumes that there is no line of sight also between the wireless base station BS1 and each of the installation candidate points p.sub.2 to p.sub.m. Then, for example, the line-of-sight determination apparatus 1 sets an installation candidate point p.sub.m+1 having the shortest distance from the installation candidate point p.sub.1 among the installation candidate points p.sub.n present at a position where the distance from the installation candidate point p.sub.1 is farther than the separation distance l.sub.q as the next determination target and performs determination of whether or not there is a line of sight between the wireless base station BS1 and the installation candidate point p.sub.m+1.

[0050] Thus, the line-of-sight determination apparatus 1 in the first embodiment excludes another installation candidate point p.sub.n that is present at a position with the separation distance l.sub.q from the installation candidate point p.sub.n for which it was determined that there is no line of sight with the wireless base station BS1, from the targets to be subjected to determination of whether or not there is a line of sight. For this reason, the line-of-sight determination apparatus 1 can reduce the number of instances of performing processing for determining whether or not there is a line of sight for the installation candidate points p.sub.n that are highly likely to be determined to have no line of sight.

[0051] Note that the subsequent operations of the line-of-sight determination apparatus 1 will be described in more detail later with reference to the flowchart.

[0052] Configuration of Line-of-Sight Determination Apparatus

[0053] Hereinafter, the functional configuration of the line-of-sight determination apparatus 1 will be described.

[0054] FIG. 2 is a block diagram showing a functional configuration of the line-of-sight determination apparatus 1 according to the first embodiment of the present invention.

[0055] The line-of-sight determination apparatus 1 is, for example, an information processing device such as a general-purpose computer. As shown in FIG. 2, the line-of-sight determination apparatus 1 is constituted by including a point cloud data acquisition unit 11, an installation candidate point selection unit 12, a line-of-sight determination unit 13, a determination exclusion list update unit 14, a determination result output unit 15, and a storage unit 16.

[0056] From, for example, an external device or the like, the point cloud data acquisition unit 11 acquires point cloud data including a plurality of installation position candidates (first positions) for the wireless base station (first wireless station) and a plurality of installation candidate positions (second positions) of a candidate building or the like (on a structure) in which a wireless terminal station (second wireless station) opposing the wireless base station is to be installed. The external device in this context is a device such as an MMS that can acquire point cloud data indicating the positions and shapes of objects in the surrounding area using, for example, a laser scanner or the like. The point cloud data acquisition unit 11 stores the acquired point cloud data in the storage unit 16.

[0057] The installation candidate point selection unit 12 selects an installation position candidate that is a target to be subjected to the determination of whether or not there is a line of sight from among a plurality of installation position candidates of the wireless base station, which are included in the point cloud data stored in the storage unit 16. Also, the installation candidate point selection unit 12 selects information indicating a building or the like that is a target to be subjected to the determination of whether or not there is a line of sight, from among information indicating a plurality of buildings or the like, which is included in the point cloud data stored in the storage unit 16. Also, the installation candidate point selection unit 12 selects an installation position candidate that is a target to be subjected to the determination of whether or not there is a line of sight, from among the plurality of installation candidate positions of the wireless terminal station in the selected building or the like (e.g., on the wall surface thereof). The installation candidate point selection unit 12 outputs information indicating the selection result to the line-of-sight determination unit 13.

[0058] The line-of-sight determination unit 13 acquires information indicating the installation position candidates of the wireless base station, the building or the like, and the installation position candidates of the wireless terminal station, which are selected by the installation candidate point selection unit 12 and that are targets to be subjected to the determination of whether or not there is a line of sight. The line-of-sight determination unit 13 determines whether or not there is a line of sight between the installation position candidate (first position) of the wireless base station and at least one installation position candidate (second position) of the wireless terminal station. The line-of-sight determination unit 13 determines whether or not there is a line of sight between the wireless base station (first wireless station) and the building or the like (structure) based on the determination result. The line-of-sight determination unit 13 outputs information indicating the determination result to the determination result output unit 15.

[0059] Also, if it is determined that there is no line of sight between the installation position candidate of the wireless base station (first position) and the installation position candidate of a certain wireless terminal station (first second position), the line-of-sight determination unit 13 outputs, to the determination exclusion list update unit 14, information indicating another installation position candidate (second second position) of the wireless terminal station located in the vicinity (that is, located within the separation distance l.sub.q) of the above-mentioned certain installation position candidate (first second position) of the wireless terminal station. Then, the line-of-sight determination unit 13 does not determine whether or not there is a line of sight between the installation position candidate (second second position) of the wireless terminal station included in the determination exclusion list and the installation position candidate (first position) of the wireless base station.

[0060] Also, if there is at least one installation position candidate that has been determined as having a line of sight among a plurality of installation position candidates of the wireless terminal station in a certain building or the like, the line-of-sight determination unit 13 determines that there is a line of sight between the installation position candidate of the wireless base station and that building or the like. On the other hand, if it is determined that there is no line of sight between the plurality of installation position candidates of the wireless terminal station and the installation position candidate of the wireless base station in a certain building or the like, the line-of-sight determination unit 13 determines that there is no line of sight between the installation position candidate of the wireless base station and the building or the like.

[0061] The determination exclusion list update unit 14 acquires the information that was output from the line-of-sight determination unit 13 and indicates another installation position candidate of the wireless terminal station that is located in the vicinity of the installation position candidate of the wireless terminal station determined to have no line of sight. The determination exclusion list update unit 14 adds the acquired information indicating the other installation position candidate of the wireless terminal station to the determination exclusion list stored in the storage unit 16.

[0062] The determination result output unit 15 acquires information indicating the determination result output from the line-of-sight determination unit 13. The determination result output unit 15 outputs information indicating the acquired determination result. For example, the determination result output unit 15 outputs a determination result indicating that there is a line of sight between the installation position candidate of the wireless base station and the building or the like. That is, a determination result is output which indicates that a wireless terminal station can be installed in the building or the like if the wireless base station is installed at the installation position candidate of the wireless base station. Alternatively, for example, the determination result output unit 15 outputs a determination result indicating that there is no line of sight between the installation position candidate of the wireless base station and the building or the like. That is, a determination result is output which indicates that a wireless terminal station cannot be installed in the building or the like if the wireless base station is installed at the installation position candidate of the wireless base station.

[0063] Note that, for example, the determination result output unit 15 may also be configured to include a communication interface and output information indicating the determination result to, for example, an external device. Alternatively, for example, the determination result output unit 15 may also be configured to include a display device such as a liquid crystal display and output the determination result by displaying on the display device.

[0064] The storage unit 16 stores the point cloud data acquired by the point cloud data acquisition unit 11. Also, the storage unit 16 stores the determination exclusion list to be updated by the determination exclusion list update unit 14. Also, the storage unit 16 stores the separation distance l.sub.q or the separation angle θ.sub.q according to a later-described fifth embodiment. The storage unit 16 may also store information indicating the width of the obstruction B3 obtained by analyzing the acquired point cloud data, information indicating the selection result of the selection performed by the installation candidate point selection unit 12, and information indicating the determination result of the determination performed by the line-of-sight determination unit 13.

[0065] Also, the storage unit 16 stores various types of data and programs to be used in each functional unit of the line-of-sight determination apparatus 1. For example, it is possible to use a configuration in which each of the above-mentioned functional units of the line-of-sight determination apparatus 1 operates due to various programs stored in the storage unit 16 being read and executed by a processor (not shown) such as a CPU (Central Processing Unit) included in the line-of-sight determination apparatus 1. Note that the storage unit 16 is constituted by including, for example, a storage medium such as a RAM (Random Access Memory; readable/writable memory), a flash memory, an EEPROM (Electrically Erasable Programmable Read Only Memory), an HDD (Hard Disk Drive), or any combination of these storage media.

[0066] Operations of Line-of-Sight Determination Apparatus

[0067] Hereinafter, an example of operations of the line-of-sight determination apparatus 1 will be described.

[0068] FIG. 3 is a flowchart showing operations of the line-of-sight determination apparatus 1 according to the first embodiment of the present invention.

[0069] The operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 3 are started when the point cloud data acquisition unit 11 acquires the point cloud data and stores the acquired point cloud data in the storage unit 16, and thereafter the installation candidate point selection unit 12 selects the installation position candidate of the wireless base station (position of the wireless base station BS1) and the building or the like (building B2) that is a target to be subjected to the determination of whether or not there is a line of sight. The point cloud data in this context is point cloud data that includes a plurality of installation position candidates of the wireless base stations (positions of the wireless base station BS1), which are present in the range of the service provision area, and a plurality of installation position candidates for the wireless terminal station in the plurality of buildings or the like (for example, on a wall surface thereof) (the installation candidate point p.sub.n in each building B2).

[0070] First, the installation candidate point selection unit 12 refers to the point cloud data stored in the storage unit 16 and selects the installation candidate point p.sub.1 in the above-described selected building B2 (e.g., on a wall surface thereof) (step S101).

[0071] Next, the line-of-sight determination unit 13 determines whether or not there is a line of sight between the position of the wireless base station BS1 selected by the installation candidate point selection unit 12 and the installation candidate point p.sub.1 (step S102). If the line-of-sight determination unit 13 determines that there is a line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.1 (step S102, Yes), the determination result output unit 15 outputs information indicating that the wireless terminal station can be installed at the installation candidate point p.sub.1 (step S103), and the operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 3 end. That is, a determination result indicating that there is a line of sight between the position of the selected wireless base station BS1 and the building B2 is output.

[0072] On the other hand, if the line-of-sight determination unit 13 determines that there is no line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.1 (step S102, No), the determination exclusion list update unit 14 adds the other installation candidate point p.sub.n that is present at a position within the separation distance l.sub.q from the position of the installation candidate point p.sub.1 to the determination exclusion list stored in the storage unit 16 (step S104).

[0073] Next, the installation candidate point selection unit 12 confirms whether or not there is an installation candidate point p.sub.n that is not included in the determination exclusion list stored in the storage unit 16 and for which determination of whether or not there is a line of sight has not been performed (step S105). If it is determined by the installation candidate point selection unit 12 that there is an installation candidate point p.sub.n that is not included in the determination exclusion list and for which the determination of whether or not there is a line of sight has not been performed (step S105, Yes), the line-of-sight determination unit 13 determines the line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n (step S107).

[0074] If the line-of-sight determination unit 13 determines that there is a line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n (step S107, Yes), the determination result output unit 15 outputs information indicating that the wireless terminal station can be installed at the installation candidate point p.sub.n (step S103), and the operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 3 end. That is, a determination result is output which indicates that there is a line of sight between the position of the selected wireless base station BS1 and the building B2.

[0075] On the other hand, if the line-of-sight determination unit 13 determines that there is no line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n (step S107, No), the determination exclusion list update unit 14 adds information indicating another installation candidate point p.sub.n that is present at a position within the separation distance l.sub.q from the position of the installation candidate point p.sub.n to the determination exclusion list stored in the storage unit 16 (step S104).

[0076] On the other hand, if it has been determined by the installation candidate point selection unit 12 that there is no installation candidate point p.sub.n that is not included in the determination exclusion list and for which the determination of whether or not there is a line of sight has not been performed (step S105, No), the installation candidate point selection unit 12 checks whether or not there is an installation candidate point p.sub.n that is included in the determination exclusion list and for which the determination of whether or not there is a line of sight has been performed (step S106).

[0077] If it has been determined by the installation candidate point selection unit 12 that there is an installation candidate point p.sub.n that is included in the determination exclusion list and for which the determination of whether or not there is a line of sight has not been performed (step S106, Yes), the determination exclusion list update unit 14 extracts the information indicating the installation candidate point p.sub.n from the determination exclusion list stored in the storage unit 16 (step S108). Next, the line-of-sight determination unit 13 determines the line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n extracted above (step S107).

[0078] If it has been determined by the line-of-sight determination unit 13 that there is a line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n extracted above (step S107, Yes), the determination result output unit 15 outputs information indicating that the wireless terminal station can be installed at the installation candidate point p.sub.n extracted above (step S103), and the operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 3 end. That is, a determination result is output which indicates that there is a line of sight between the position of the selected wireless base station BS1 and the building B2.

[0079] On the other hand, if it has been determined by the line-of-sight determination unit 13 that there is no line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.n extracted above (step S107, No), the determination exclusion list update unit 14 adds information indicating another installation candidate point p.sub.n that is present at a position within the separation distance l.sub.q from the position of the installation candidate point p.sub.n extracted above to the determination exclusion list stored in the storage unit 16 (step S104).

[0080] On the other hand, if it is determined by the installation candidate point selection unit 12 that there is no installation candidate point p.sub.n that is included in the determination exclusion list and for which the determination of whether or not there is a line of sight has not been performed (step S106, No), it is determined that there is no line of sight between the positions of the wireless base station BS1 and all of the installation candidate points p.sub.n of the building B2. In this case, the determination result output unit 15 outputs information indicating that there is no position at which the wireless terminal station can be installed in the building B2 selected as the target to be subjected to the determination of whether or not there is a line of sight (step S109), and the operations of the line-of-sight determination apparatus 1 indicated by the flowchart in FIG. 3 end. That is, a determination result is output which indicates that there is no line of sight between the position of the selected wireless base station BS1 and the building B2.

[0081] Note that in an example, as shown in FIG. 1, the line-of-sight determination apparatus 1 according to the present embodiment starts processing for determining whether or not there is a line of sight from the installation candidate point p.sub.1 located at an end portion of the building B2, and determines whether or not there is a line of sight in order starting from the installation candidate point p.sub.n with a closer distance to the installation candidate point p.sub.1 (while excluding the installation candidate points p.sub.n included in the determination exclusion list from the determination targets). For example, the line-of-sight determination apparatus 1 determines whether or not there is a line of sight in the following order: installation candidate point p.sub.1, installation candidate point p.sub.2, installation candidate point p.sub.3, . . . , and installation candidate point p.sub.N. However, the configuration is not limited to this kind of configuration, and for example, the line-of-sight determination apparatus 1 may also be configured to randomly select one installation candidate point p.sub.n as a determination target each time from among the N installation candidate points p.sub.n.

[0082] Note that as shown in the flowchart of FIG. 3, in some cases, the line-of-sight determination apparatus 1 according to the present embodiment extracts an installation candidate point p.sub.n that is included in the exclusion list and for which the determination of whether or not there is a line of sight has not been performed, and determines whether or not there is a line of sight. That is, if there is no installation candidate point p.sub.n that has been determined as having a line of sight among the installation candidate points p.sub.n that are not included in the determination exclusion list, next, the line-of-sight determination apparatus 1 determines whether or not there is a line of sight using all of the N installation candidate points p.sub.n as the determination targets.

[0083] However, the present invention is not limited to such a configuration, and for example, the line-of-sight determination apparatus 1 may also be configured to omit the operation of step S106 of the flowchart shown in FIG. 3 in order to speed up the determination of whether or not there is a line of sight for each building B2, whereby the installation candidate point p.sub.n is not extracted from the determination exclusion list. That is, the line-of-sight determination apparatus 1 may also deem that there is similarly no line of sight between the candidate position of the wireless base station and another installation candidate point p.sub.n located in the vicinity (within the separation distance l.sub.q) of the installation candidate point p.sub.n that has been determined as having no line of sight with the candidate position of the wireless base station.

[0084] Note that in this embodiment, in order to simplify the description, it is assumed that N installation candidate points p.sub.n are arranged linearly on a two-dimensional plane as shown in FIG. 1. However, in actuality, the installation candidate point p.sub.n generally exists in a three-dimensional space. However, even in such a case, as described above, the line-of-sight determination apparatus 1 may sequentially select the installation candidate points p.sub.n that are closer, or may randomly select one installation candidate point p.sub.n each time.

[0085] Even if the installation candidate point p.sub.n is present in a three-dimensional space, according to the line-of-sight determination apparatus 1 in the present embodiment, other installation candidate points p.sub.n that are present in the vicinity of the installation candidate point p.sub.n that has been determined as having no line of sight are less likely to be selected as targets to be subjected to the determination of whether or not there is a line of sight, and therefore the determination of whether or not there is a line of sight between the position of the wireless base station BS1 and the building B2 is made more efficient.

Second Embodiment

[0086] Hereinafter, a second embodiment of the present invention will be described.

[0087] The free-space propagation loss of wireless electromagnetic wave propagation is proportional to the square of the frequency. For this reason, there is a problem in that the range reached by the electromagnetic waves (hereinafter referred to as “coverage”) becomes narrow, especially in a high frequency band such as a millimeter-wave band. In contrast to this, it is conceivable to expand the coverage by narrowing the beam of the electromagnetic wave and increasing the gain. However, by simply increasing the gain, the coverage expands in only a specific direction. In view of this, by using a beamforming technique according to which it is possible to direct a beam in a plurality of directions, it is possible to emit an electromagnetic wave in any direction, and therefore coverage can be expanded in any direction.

[0088] However, the purpose of using beamforming is merely to compensate for the free space propagation loss in any direction. Accordingly, the desired range need only be covered by directing the radiation direction of the electromagnetic wave in each direction divided in equal intervals with an interval of about the beam width. That is, it is not necessary to control the emission direction of the electromagnetic wave with a particle size finer than this. For example, a configuration is common in which beamforming is performed by selecting from a limited number of beam direction candidates, such as performing beamforming in units of 3-dB beam widths and directing the beam in an overall desired direction, with an allowed power loss of 3 [dB].

[0089] If it has been determined that there is no line of sight between the installation position candidate of the wireless base station and one installation position candidate of the wireless terminal station within a specific beam range, it is thought that there is a high likelihood that it will be determined that there is similarly no line of sight between the installation position candidate of the wireless base station and the installation position candidate of another wireless terminal station that is present within the same beam range. This is because a plurality of installation position candidates that are present in the same beam range are located close to each other.

[0090] The line-of-sight determination apparatus 1 in the second embodiment sets the value of the separation distance l.sub.q, which was set as a random value in the above-described first embodiment, to a value obtained based on the beam width. The value obtained based on the beam width is, for example, the value of the beam width itself, a value obtained by adding or subtracting a predetermined numeric value from the value of the beam width, or the like. As a result, the line-of-sight determination apparatus 1 can reduce the number of instances of performing the processing for determining whether or not there is a line of sight for the installation candidate position, which is likely to be determined as having no line of sight.

Third Embodiment

[0091] Hereinafter, a third embodiment of the present invention will be described.

[0092] In the above-described second embodiment, it is assumed that a configuration is used in which, in the beamforming performed by the wireless base station, a specific beam is selected from beam candidates directed in a plurality of emission directions set at intervals of about the beam width. Then, the value of the separation distance l.sub.q is set to a value obtained based on the beam width, and processing for determining whether or not there is a line of sight is performed.

[0093] On the other hand, the particle size of the beamforming performed by the wireless base station can be made even finer than the beam width. For example, in the case where there is an obstruction in the Fresnel zone, if there is an installation position candidate of the wireless terminal station that has been determined as having no line of sight due to the influence of the obstruction that is present in the Fresnel zone, it is thought that there is a high likelihood that it will be determined that there is similarly no line of sight also for another installation position candidate located in the vicinity of the installation position candidate.

[0094] The line-of-sight determination apparatus 1 in the third embodiment sets the value of the separation distance l.sub.q, by which the value obtained based on the beam width is set in the above-described second embodiment, to a value obtained based on the Fresnel zone width. The value obtained based on the Fresnel zone width is, for example, the value of the Fresnel zone width itself, a value obtained by adding or subtracting a predetermined numeric value to or from the value of the Fresnel zone width, or the like.

[0095] Specifically, for example, the value of the Fresnel zone width r.sub.1 [m], which is represented by the following equation (3) is set as the value of the above-described separation distance l.sub.q. Then, if there is an installation position candidate of a wireless terminal station that has been determined as having no line of sight with the installation position candidate of the wireless base station due to the influence of an obstruction that is present in the Fresnel zone, the line-of-sight determination apparatus 1 does not perform the determination of whether or not there is a line of sight on another installation position candidate of the wireless terminal station located within the range of the Fresnel zone width r.sub.1.

[00001]$\begin{array}{cc}\left[\mathrm{Math}.3\right]& \\ r_1=\frac{\sqrt{\lambda d}}{2}& \left(3\right)\end{array}$

[0096] Here, λ, represents the wavelength of an electromagnetic wave used for wireless communication. Also, d represents the distance between the wireless base station and the wireless terminal station. Note that the Fresnel zone width at this time is the radius at a distance d/2 at which the Fresnel zone radius is at its maximum, but it may also be the radius at a different position d′. This radius r2 is expressed by the following equation (4). When d′=d/2, r2=r1 is satisfied.

[00002]$\begin{array}{cc}\left[\mathrm{Math}.4\right]& \\ r_2=\sqrt{\lambda \frac{d^{\prime }\left(d-d^{\prime }\right)}{d}}& \left(4\right)\end{array}$

[0097] According to the above-described configuration, the line-of-sight determination apparatus 1 can reduce the number of instances of performing processing for determining whether or not there is a line of sight for an installation candidate position that is highly likely to be determined as having no line of sight.

Fourth Embodiment

[0098] Hereinafter, a fourth embodiment of the present invention will be described.

[0099] In each of the above-described embodiments, in order to simplify the description, a configuration was used in which it is determined whether or not there is a line of sight using point cloud data on a two-dimensional plane. However, in actuality, three-dimensional point cloud data is commonly used. In general, the number of pieces of three-dimensional point cloud data is often very large. For this reason, it is thought that it may not be realistic to extract an object that serves as an obstruction from this large amount of point cloud data.

[0100] In contrast to this, for example, in general two-dimensional map data such as a vector map, by regarding a figure of a closed path such as a rectangle as a building or the like, it is possible to estimate the size of the building or the like. This makes it possible to identify the width of a building assumed to be an obstruction.

[0101] The line-of-sight determination apparatus 1 in the fourth embodiment sets the value of the separation distance l.sub.c′ to a value obtained based on the width of the obstruction. The value obtained based on the width of the obstruction is, for example, the value of the width of the obstruction itself, or a value obtained by adding or subtracting a predetermined value to or from the value of the width of the obstruction.

[0102] As described above, the width of the obstruction is specified based on other map data such as a vector map. For example, the line-of-sight determination apparatus 1 identifies the minimum value l.sub.b of the width of the obstruction detected based on the other map data. Then, the line-of-sight determination apparatus 1 sets the value of the separation distance l.sub.q to the value of l.sub.b.

[0103] According to the above-described configuration, the line-of-sight determination apparatus 1 can reduce the number of instances of performing processing for determining whether or not there is a line of sight for an installation candidate position that is likely to be determined as having no line of sight.

Fifth Embodiment

[0104] Hereinafter, a fifth embodiment of the present invention will be described.

[0105] In each of the above-described embodiments, in order to simplify the description, a case has been described in which the direction of the building or the like (e.g., the wall surface thereof) is the direction of the wireless base station BS1 has been described. However, in actuality, as shown in FIG. 4, for example, a case is also conceivable in which two wall surfaces of the building B2 face direction that are at different angles with respect to the wireless base station BS1. In the example shown in FIG. 4, the angle between the orientation of the wall surface w1 of the building B2 and the direction of the wireless base station BS1 is smaller than the angle between the orientation of the wall surface w2 of the building B2 and the direction of the wireless base station BS1.

[0106] If the orientations of the wireless base station BS1 and the building B2 are as shown in FIG. 4, for example, when the intervals of the plurality of installation candidate points p.sub.n are set to equal intervals similarly to, for example, the above-described first embodiment, the angle interval of each installation candidate point p.sub.n viewed from the wireless base station BS1 varies. That is, the angle interval between the two adjacent installation candidate points p.sub.n located on the wall surface w1 of the building B2 as seen from the wireless base station BS1 is wider, and the angle interval between the two adjacent installation candidate points p.sub.n located on the wall surface w2 of the building B2 is narrower. Note that even if the installation candidate points p.sub.n are located on the same wall surface, the closer the installation candidate point p.sub.n is to the wireless base station BS1, the wider the angle interval is, and the farther the installation candidate point p.sub.n is from the wireless base station BS1, the narrower the angle interval is.

[0107] In such a case, if the separation distance l.sub.q is set according to the interval of the installation candidate points p.sub.n located on the wall surface w1 having a wider angle interval, the interval of a plurality of installation candidate points p.sub.n located on the wall surface w2 having a narrow angle interval will be too narrow when viewed from the wireless base station BS1. As a result, the number of instances of processing for determining whether or not there is a line of sight is increased, and thus an unnecessary calculation cost is generated. Conversely, if the separation distance l.sub.q is set according to the interval of the installation candidate points p.sub.n located on the wall surface w2 with the narrower angle interval, the interval of the plurality of installation candidate points p.sub.n located on the wall surface w1 with the wider angle interval will be too wide when viewed from the wireless base station BS1. As a result, there is a possibility that the installation candidate point p.sub.n, which is determined as having a line of sight, will not be detected efficiently.

[0108] In contrast to this, in the line-of-sight determination apparatus 1 according to the fifth embodiment, the separation value used to determine whether or not to add, to the determination exclusion list, another installation position candidate of the wireless terminal station that is located in the vicinity of the installation position candidate of the wireless terminal station that has been determined as not having a line of sight with the candidate position of the wireless base station is defined not by the distance (separation distance l.sub.q) as in the first embodiment described above, but by the angle (separation angle θ.sub.q).

[0109] If the interval l.sub.p of the adjacent installation candidate point p.sub.n has been converted into the angle seen from the wireless base station BS1, the angle θ.sub.p is expressed by as in following equation (5).

[00003]$\begin{array}{cc}\left[\mathrm{Math}.5\right]& \\ {\theta }_p={\cos }^{-1}\frac{\stackrel{.Math.}{p_i{p}_{\mathrm{BS}1}}.Math.\stackrel{.Math.}{p_{i+1}{p}_{\mathrm{BS}1}}}{.Math.\stackrel{.Math.}{p_i{p}_{\mathrm{BS}1}}.Math..Math.\stackrel{.Math.}{p_{i+1}{p}_{\mathrm{BS}1}}.Math.}& \left(5\right)\end{array}$

[0110] Here, p.sub.ip.sub.SB1 (right arrow above) represents a vector starting from a point p.sub.i and ending at a point p.sub.BS1. Also, for example, the above interval l.sub.p shown in FIG. 5 can be expressed as in the following equation (6).

[Math. 6]

l.sub.p=|p.sub.ip.sub.i+1|  (6)

[0111] Also, between the angle θ.sub.b obtained by converting the width l.sub.b of the obstruction B3 into the angle viewed from the wireless base station BS1 and θ.sub.p shown in the above-described equation (4), the same relationship as the relationship between the interval l.sub.p between the two adjacent installation candidate points p.sub.n and the width l.sub.b of the obstruction B3 shown in equation (1) in the above-described first embodiment is satisfied. That is, the relationship between θ.sub.b and θ.sub.p is expressed by the following equation (7).

[Math. 7]

θ.sub.p<<θ.sub.b  (7)

[0112] As described above, in general, the width l.sub.b of the obstruction B3 is relatively quite large compared to the distance l.sub.p between two adjacent installation candidate points p.sub.n. Therefore, if it has been determined that there is no line of sight between a certain installation candidate point p.sub.n and the wireless base station BS1, it can be said that there is a very high likelihood that it will similarly be determined that there is no line of sight also for another installation candidate point p.sub.n that is present at a position within the separation angle θ.sub.p in a view from the wireless base station BS1.

[0113] Note that in general, the angle θ.sub.b obtained by converting the width l.sub.b of the obstruction B3 into the angle viewed from the wireless base station BS1 is unknown, and in actuality, there may be cases where the angle θ.sub.b is not necessarily much larger than the above angle θ.sub.p. However, in order to specify the angle θ.sub.b, it is easily expected that analysis of a large number of pieces of point cloud data will be required and a large amount of calculation time will be required. Therefore, in the line-of-sight determination apparatus 1 according to the fifth embodiment, the angle θ.sub.b is not specified, and any separation angle θ.sub.q that satisfies the following equation (8) is defined.

[Math. 8]

θ.sub.p<θ.sub.q  (8)

[0114] As described above, the line-of-sight determination apparatus 1 in the fifth embodiment excludes another installation candidate point p.sub.n that is present at a position within the separation angle θ.sub.q from the installation candidate point p.sub.n that has been determined as having no line of sight with the wireless base station BS1 from the targets to be subjected to the determination of whether or not there is a line of sight. That is, the line-of-sight determination apparatus 1 excludes another installation candidate point p.sub.n for which the angle between the installation candidate point p.sub.n that has been determined as having no line of sight and another installation candidate point p.sub.n as viewed from the position of the wireless base station BS1 is a predetermined angle (separation angle θ.sub.q) or less from the targets to be subjected to the determination of whether or not there is a line of sight. As a result, the line-of-sight determination apparatus 1 can reduce the number of instances of performing processing for determining whether or not there is a line of sight for the installation candidate point p.sub.n, which is likely to be determined as having no line of sight.

[0115] Note that as described above, the line-of-sight determination apparatus 1 in the fifth embodiment has a configuration in which the separation angle θ.sub.q is used instead of the separation distance l.sub.q as in the first embodiment described above as the value of the separation serving as a reference for determining whether or not to add, to the determination exclusion list, another installation position candidate of the wireless terminal station located in the vicinity of the installation position candidate of the wireless terminal station that has been determined as having no line of sight. Such a configuration in which the separation angle θ.sub.q is used as a reference instead of the separation distance l.sub.q can be similarly applied to the second to fourth embodiments described above as well.

Sixth Embodiment

[0116] Hereinafter, a sixth embodiment of the present invention will be described.

[0117] In the above-described first embodiment, the line-of-sight determination apparatus 1 starts the processing for determining whether or not there is a line of sight from the installation candidate point p.sub.1 located at the end portion of the building B2. Then, the line-of-sight determination apparatus 1 performs the determination of whether or not there is a line of sight in order starting from the installation candidate point p.sub.n that is closer to the installation candidate point p.sub.1 while excluding installation candidate points p.sub.n included in the determination exclusion list from the determination targets. Then, in the above-described second embodiment and third embodiment, the line-of-sight determination apparatus 1 uses a value obtained based on the beam width and the Fresnel zone width as the value of the separation distance l.sub.q, which is a reference for deciding whether or not to add, to the determination exclusion list, another installation position candidate of the wireless terminal station located in the vicinity of the installation position candidate of the wireless terminal station that has been determined as having no line of sight.

[0118] However, if the obstruction B3 is not a thin object such as a utility pole or a tree but a structure that is horizontally wide as a horizontally long building, there is a possibility that it may be continuously determined that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.n even if a value obtained based on the beam width or the Fresnel zone width is used as the value of the separation distance l.sub.q.

[0119] FIG. 6 is a schematic view showing the line-of-sight determination performed by the line-of-sight determination apparatus 1 according to the sixth embodiment of the present invention. In the present embodiment, as shown in FIG. 6, if the determination of whether or not there is a line of sight is performed for a plurality of installation candidate points p.sub.n (n=1, 2, . . . , N) of a certain building B2 (e.g., a wall surface or the like thereof), for example, the line-of-sight determination apparatus 1 performs the determination in the following order.

[0120] Similarly to the above-described first embodiment, the line-of-sight determination apparatus 1 in the present embodiment first determines whether or not there is a line of sight between the wireless base station BS1 and the installation candidate point p.sub.1 on the leftmost end in the building B2. As shown in FIG. 6, there is an obstruction B3 between the wireless base station BS1 and the installation candidate point p.sub.1. Accordingly, the line-of-sight determination apparatus 1 determines that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1.

[0121] If it has been determined that there is no line of sight between the wireless base station BS1 and the installation candidate point p.sub.1, the line-of-sight determination apparatus 1 assumes that there is no line of sight between the wireless base station BS1 and other installation candidate points p.sub.n (that is, the installation candidate point p.sub.2 to the installation candidate point p.sub.m) that are present at positions at which the distance from the installation candidate point p.sub.1 is within the separation distance l.sub.q, similarly to the above-described first embodiment.

[0122] Then, the line-of-sight determination apparatus 1 in the present embodiment does not select p.sub.m+1 as the next installation candidate point p.sub.n that is a target to be subjected to the determination of whether or not there is a line of sight as in the above-described first embodiment, but selects the installation candidate point p.sub.N located at the opposite end (third second position), which is the position farthest from the installation candidate point p.sub.1 that has been determined as having no line of sight.

[0123] Note that the subsequent operations of the line-of-sight determination apparatus 1 will be described in detail below with reference to the flowchart.

[0124] Operations of Line-of-Sight Determination Apparatus

[0125] Hereinafter, an example of operations of the line-of-sight determination apparatus 1 will be described.

[0126] FIG. 7 is a flowchart showing operations of the line-of-sight determination apparatus 1 according to the sixth embodiment of the present invention.

[0127] The operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 7 are started when the point cloud data acquisition unit 11 acquires the point cloud data and stores the acquired point cloud data in the storage unit 16, and thereafter the installation candidate point selection unit 12 selects an installation position candidate of the wireless base station (position of the wireless base station BS1) and a building or the like (building B2), which are to be targets to be subjected to the determination of whether or not there is a line of sight. The point cloud data in this context is point cloud data including a plurality of installation position candidates of the wireless base station (positions of the wireless base station BS1) that are present within the range of the service provision area, and installation position candidates of a plurality of wireless terminal stations (each installation candidate point p.sub.n in each building B2) in a plurality of buildings (e.g., on a wall surface), similarly to the above-described first embodiment.

[0128] Note that here, as shown in FIG. 6, it is assumed that N installation candidate points p.sub.n (in order from p.sub.1 to p.sub.N) are aligned in a horizontal row on the building B2. Also, it is assumed that the installation candidate point p.sub.1 is located at one end portion (e.g., the left end in FIG. 6) of the building B2. Also, it is assumed that the installation candidate point p.sub.N is located at the other end portion (e.g., the right end in FIG. 6) of the building B2, which is the farthest from the position of the installation candidate point p.sub.1.

[0129] First, the installation candidate point selection unit 12 of the line-of-sight determination apparatus 1 substitutes 1 for n, which is a variable that identifies the installation candidate point p.sub.n (n=1) (step S601). Note that the value of the variable is temporarily stored in, for example, the storage unit 16 or the like. Next, the line-of-sight determination unit 13 determines whether or not there is a line of sight between the position of the wireless base station BS1 and the a.sub.n-th installation candidate point p.sub.an that satisfies the following equation (9) (step S602).

[00004]$\begin{array}{cc}\left[\mathrm{Math}.9\right]& \\ a_n=\{\begin{array}{cc}\frac{n}{2}+\frac{1}{2}& \left(\mathrm{if}n\mathrm{is}\mathrm{odd}\right)\\ N-\frac{n}{2}+1& \left(\mathrm{if}n\mathrm{is}\mathrm{even}\right)\end{array}& \left(9\right)\end{array}$

[0130] If it has been determined by the line-of-sight determination unit 13 that there is a line of sight between the position of the wireless base station BS1 and the a.sub.n-th installation candidate point p.sub.an (step S602, Yes), the determination result output unit 15 outputs information indicating that the wireless terminal station can be installed at the installation candidate point p.sub.an (step S603), and the operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 7 end. That is, a determination result is output which indicates that there is a line of sight between the position of the selected wireless base station BS1 and the building B2.

[0131] On the other hand, if it has been determined by the line-of-sight determination unit 13 that there is no line of sight between the position of the wireless base station BS1 and the installation candidate point p.sub.1 (step S602, No), the installation candidate point selection unit 12 checks whether or not n=N is satisfied (step S604). If n=N is not satisfied (i.e., if n=N is satisfied) (step S604, No), the installation candidate point selection unit 12 adds 1 to the value of n (n←n+1) (step S605). Then, the line-of-sight determination unit 13 repeats the operations of step S602 and onward once again.

[0132] On the other hand, if n=N is satisfied (step S604, Yes), it is determined that there is no line of sight between the position of the wireless base station BS1 and all of the installation candidate points p.sub.n of the building B2. In this case, the determination result output unit 15 outputs information indicating that there is no position where the wireless terminal station can be installed in the building B2 that is a target to be subjected to the determination of whether or not there is a line of sight (step S606), and the operations of the line-of-sight determination apparatus 1 shown in the flowchart of FIG. 7 end. That is, a determination result is output which indicates that there is no line of sight between the position of the selected wireless base station BS1 and the building B2.

[0133] Note that in order to simplify the description, the flowchart shown in FIG. 7 omits description of a configuration in which information indicating other installation candidate points p.sub.n located in the vicinity of the installation candidate point p.sub.n that has been determined as having no line of sight is added to the determination exclusion list, and the other installation candidate points p.sub.n are excluded from the targets to be subjected to the determination of whether or not there is a line of sight. However, it is of course possible to apply the configuration in this embodiment as well, similarly to the above-described embodiments.

[0134] Also, in the present embodiment, as indicated by the above equation (9), if the installation candidate point p.sub.n has been determined as having no line of sight even once, another installation candidate point p.sub.n located on the opposite side of (at a position farther away from) the installation candidate point p.sub.n on the building B2 is selected as the next target to be subjected to the determination of whether or not there is a line of sight. However, the present invention is not limited to such a configuration, and for example, a configuration is also possible in which the line-of-sight determination apparatus 1 starts the determination of whether or not there is a line of sight from one side of the wall surface of the building B2, and at a timing when it is repeatedly determined at predetermined number of times that there is no line of sight between the installation position candidate of the wireless terminal station and the installation position candidate of the wireless base station, performs switching such that the determination of whether or not there is a line of sight is performed from the other side (opposite side) this time.

[0135] As described above, the line-of-sight determination apparatus 1 according to each embodiment of the present invention described above uses point cloud data to determine whether or not there is a line of sight between installation position candidates of two opposing wireless stations. In determining whether or not there is a line of sight, if it is determined that there is no line of sight in a certain installation position candidate, there is a high likelihood that it will be determined that there is no line of sight also for another installation position candidate located in the vicinity of the installation position candidate. For this reason, when an installation position candidate that is the next target to be subjected to the determination of whether or not there is a line of sight is selected, the line-of-sight determination apparatus 1 selects from other installation position candidates excluding the installation position candidates located within a predetermined distance (e.g., the separation distance or separation angle) from the installation position candidate that has been determined as having no line of sight.

[0136] By providing such a configuration, the line-of-sight determination apparatus 1 in each embodiment of the present invention described above can further suppress the probability of selecting an installation position candidate that will be determined as having no line of sight. As a result, the line-of-sight determination apparatus 1 can improve the efficiency of determining of whether or not there is a line of sight between the installation position candidates of the two opposing wireless stations.

[0137] The line-of-sight determination apparatus 1 according to the above-described embodiment may also be realized by a computer. In this case, a program for realizing this function may be recorded on a computer-readable recording medium, and the program recorded on the recording medium may be read by the computer system and executed. Note that it is assumed that the term “computer system” as used herein includes an OS and hardware of peripheral devices. Also, “computer-readable recording medium” refers to a portable medium such as a flexible disk, a magneto-optical disk, a ROM, or a CD-ROM, or a recording device such as a hard disk built in a computer system. Furthermore, a “computer-readable recording medium” may also include a recording medium in which a program is held dynamically for a short amount of time, such as a communication line in the case of transmitting a program via a network such as the Internet or a communication line such as a telephone line, and a recording medium in which a program is held for a certain period of time, such as a volatile memory inside a computer system that serves as a server or a client in that case. Also, the above-described program may be for realizing part of the above-described functions, and the above-described functions may be further realized in combination with a program already recorded in the computer system, and may be realized using a programmable logic device such as an FPGA (Field Programmable Gate Array).

[0138] Although an embodiment of the present invention has been described above in detail with reference to the drawings, the specific configuration is not limited to this embodiment, and designs and the like that do not depart from the gist of the present invention are also encompassed therein.

REFERENCE SIGNS LIST

[0139] 1 Line-of-sight determination apparatus [0140] 11 Point cloud data acquisition unit [0141] 12 Installation candidate point selection unit [0142] 13 Determination unit [0143] 14 Determination exclusion list update unit [0144] 15 Determination result output unit [0145] 16 Storage unit